Skip Graphs

James Aspnes, Gauri Shah

Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2003, pp. 384-393.
Submitted to Journal of Algorithms.

Abstract

Skip graphs are a novel distributed data structure, based on skip lists, that provide the full functionality of a balanced tree in a distributed system where elements are stored in separate nodes that may fail at any time. They are designed for use in searching peer-to-peer networks, and improve on existing search tools that provide only hash table functionality by adding the ability to perform queries based on key ordering. Unlike skip lists or other tree data structures, skip graphs are highly resilient, tolerating a large fraction of failed nodes without losing connectivity. In addition, we provide simple and straightforward algorithms for constructing, inserting new elements into, and searching a skip graph in logarithmic time, as well as a mechanism for detecting and repairing errors in the data structure introduced by node failures.


Bibtex:
@inproceedings{AspnesS2003,
title="Skip Graphs",
author="James Aspnes and Gauri Shah",
booktitle="Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms",
pages="384--393",
month={12--14~} #jan,
year="2003",
address={Baltimore, MD, USA},
}