Cone: Augmenting DHTs to Support Distributed Resource Discovery
Ranjita Bhagwan, George Varghese, Geoffrey M. Voelker · 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.Pre-2018 CSE ID: CS2003-0755