Distributed Data Structures for Peer-to-peer Systems

James Aspnes, Gauri Shah
In Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless and Peer-to-Peer Networks
Jie Wu, editor, CRC Press, August 2005, pp. 685-700.

Abstract

This article describes some recent distributed data structures that have been proposed to implement peer-to-peer systems for resource sharing. We first give a broad overview of Distributed Hash Tables (DHTs) which form the basic building blocks of many peer-to-peer systems, and describe some of the features of the more popular DHT implementations. We also briefly describe some of the other organized data structures that have been proposed to build peer-to-peer systems. We then focus on describing skip graphs, which overcome some limitations of DHTs such as lack of spatial locality and lack of support for range queries.

Bibtex:
@inbook{AspnesS2005,
title="Distributed Data Structures for Peer-to-peer Systems",
author="James Aspnes and Gauri Shah",
booktitle="Handbook on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks",
editor="Jie Wu",
publisher="CRC Press",
month=aug, year="2005",
pages="685--700",
}