Cone:Augmenting DHTs to Support Distributed Resource Discovery

Ranjita Bhagwan, George Varghese and Geoffrey M. Voelker
CS2003-0755
July 21, 2003

In this report, we suggest that both P2P Content Sharing and Computing can benefit from a unified perspective via distributed data structures with suitably chosen abstract operations. We introduce the generic approach of augmenting distributed data structures. Our approach augments a DHT and builds a prefix trie on node IDs and adds augmenting information to nodes. The augmentation can use any aggregate operator on keys (Max, Min, Sum,etc.).We apply the augmentation approach to introduce a new distributed data structure called a Cone. Cones support a variety of queries to locate resources, such as locating a resource of maximum size or a resource of at least a given size. For a DHT with N nodes and IDs of m bits, queries and updates take an expected-case O(log N) and worst-case O(m) messages.


How to view this document


The authors of these documents have submitted their reports to this technical report series for the purpose of non-commercial dissemination of scientific work. The reports are copyrighted by the authors, and their existence in electronic format does not imply that the authors have relinquished any rights. You may copy a report for scholarly, non-commercial purposes, such as research or instruction, provided that you agree to respect the author's copyright. For information concerning the use of this document for other than research or instructional purposes, contact the authors. Other information concerning this technical report series can be obtained from the Computer Science and Engineering Department at the University of California at San Diego, techreports@cs.ucsd.edu.


[ Search ]


NCSTRL
This server operates at UCSD Computer Science and Engineering.
Send email to webmaster@cs.ucsd.edu