Distributed Data Structures for Peer-to-peer Systems
Gauri Shah
Abstract
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 because 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 network 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 is an abstract model of a distributed hash table, which is used as an overlay network by many contemporary peer-to-peer systems. This data structure provides inherent load balancing, and a delivery time which 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 system. 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 range or approximate queries. We give simple and straightforward algorithms to search and insert a new resource into a skip graph in logarithmic time. We also give a repair mechanism that can be combined with the fault-tolerance properties to give a strong foundation for a highly resilient system.
Bibtex:
@phdthesis{Shah2003,
title="Distributed Data Structures for Peer-to-peer Systems",
author="Gauri Shah",
school="Yale University",
month=may, year="2003",
address={New Haven, CT, USA},
}