James Aspnes and Gauri Shah. Distributed data structures for P2P systems. Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless and Peer-to-Peer Networks, Jie Wu, editor, CRC Press, 2005, pages 685–700.
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.
@incollection(AspnesS2005,
title="Distributed data structures for {P2P} systems",
author="James Aspnes and Gauri Shah",
booktitle="Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless and Peer-to-Peer Networks",
editor="Jie Wu",
publisher="CRC press",
month=aug,
pages={685--700},
year=2005
)