  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,
constructing, inserting new nodes into, searching a skip graph, and detecting
and repairing errors in the data structure introduced by node failures can be
done using simple and straightforward algorithms.
