Finding Nearby Objects in Peer-to-Peer Networks
Kirsten W. Hildrum · 2004
A peer-to-peer object location system is an evolving set of computers cooperating to store objects. A reasonable system should easily adapt when computers join or leave the network (self-organization), reliably find objects (completeness), and ensure that no computer works too hard (load balance). Searches in this network should find nearby copies of objects when possible: a searcher in Berkeley looking for an object on the Berkeley subnetwork should find the object without ever sending a message outside of Berkeley. In this thesis, we describe the first techniques to maintain these properties. Our performance depends on an upper bound on the growth rate of the network, which can be high in some cases. We further build an adaptive scheme that depends only on a local version of the growth rate. As a result, the bad areas of the network do not force high resource usage everywhere. We also describe techniques to make peer-to-peer systems tolerant to faults. 1