| Peer-to-peer systems are distributed systems of heterogeneous machines with no central authority, that are used for efficient management and location of shared resources. Such systems have become very popular for Internet applications in a short period of time be cause they provide inherent scalability by distributing the load of maintaining the system across all the participants. At the same time, they present new challenges in designing distributed data structures that can provide the desired functionality such as data availability, dynamic system maintenance, and support for complex queries using untrusted and unreliable components.; We present two complementary distributed data structures that can be used to implement efficient peer-to-peer systems. The first data structure used as an overlay network by many contemporary peer-to-peer systems. This data structure provides inherent load balancing, and the number of routing hops for a search is logarithmic in the number of resources in the system. We study greedy routing in this model, and prove lower bounds and upper bounds on routing in the presence of failures in the network. We present some heuristics for constructing the network and give experimental results on the performance in practice.; We also present a novel distributed data structure called a skip graph, which is a trie of skip lists that share lower layers. A skip graph provides most of the functionality of a distributed hash table. In addition, it supports spatial locality and complex searches such as near matches to a key, keys within a specified range, or approximate queries. We give simple and straightforward algorithms to search and insert a new resource in a skip graph. We also give a repair mechanism that can be combined with the fault-tolerance properties to give a strong foundation for a highly resilient network. |
