Skip graphs

By James Aspnes, Gauri Shah. ACM-SIAM Symposium on Discrete Algorithms, 2003

776 citations recorded by the source corpus.

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 resources are stored in separate nodes that may fail at any time. They are designed for use in searching peer-to-peer systems, and by providing the ability to perform queries based on key ordering, they improve on existing search tools that provide only hash table functionality. 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, simple and straightforward algorithms can be used to construct a skip graph, insert new nodes into it, search it, and detect and repair errors within it introduced due to node failures.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/2ebe1ffec53e63c2799cba961503f0a6abafccd3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

MAAN: A Multi-Attribute Addressable Network for Grid Information Services (2003, neutral): “Skip Graphs [2] and SkipNet [7] are two skip-list based structured P2P systems.”
Survey of research towards robust peer-to-peer networks: Search methods (2006, methodology): “They proposed two Skip Graphs, one to index the data itself and the other to track load at each node in the system.”
Simple Efficient Load-Balancing Algorithms for Peer-to-Peer Systems (2004, methodology): “An ef.cient range search data structure was recently given by Aspnes and Shah [3].”
BATON: A Balanced Tree Structure for Peer-to-Peer Networks (2005, neutral): “SkipList based systems such as SkipNet [6] and SkipGraph [2] can support range queries but they do not guarantee data locality and load balancing in the whole system.”
The rainbow skip graph: a fault-tolerant constant-degree distributed data structure (2006, methodology): “It is a non-trivial adaptation of the SkipNet/skip-graph structures of Harvey et al. and Aspnes and Shah, so as to provide fault-tolerance as these structures do, but to do so using constant-sized nodes, as in the family tree structure of Zatloukal and Harvey.”