Skip graph

Skip graphs are a kind of distributed data structure based on skip lists. They were invented in 2003 by James Aspnes and Gauri Shah. They have the full functionality of a balanced tree in a distributed system. Skip graphs are mostly used in searching peer-to-peer networks. As they provide the ability to query by key ordering, they improve over search tools based on the hash table functionality only. In contrast to skip lists and other tree data structures, they are very resilient and can tolerate a large fraction of node failures. Also, constructing, inserting, searching and repairing a skip graph that was disturbed by failing nodes can be done by straightforward algorithms. Skip graphs are a kind of distributed data structure based on skip lists. They were invented in 2003 by James Aspnes and Gauri Shah. They have the full functionality of a balanced tree in a distributed system. Skip graphs are mostly used in searching peer-to-peer networks. As they provide the ability to query by key ordering, they improve over search tools based on the hash table functionality only. In contrast to skip lists and other tree data structures, they are very resilient and can tolerate a large fraction of node failures. Also, constructing, inserting, searching and repairing a skip graph that was disturbed by failing nodes can be done by straightforward algorithms. A skip graph is a distributed data structure based on skip lists designed to resemble a balanced search tree. They are one of several methods to implement a distributed hash table, which are used to locate resources stored in different locations across a network, given the name (or key) of the resource.Skip graphs offer several benefits over other distributed hash table schemes such as Chord (peer-to-peer) and Tapestry (DHT), including addition and deletion in expected logarithmic time, logarithmic space per resource to store indexing information, no required knowledge of the number of nodes in a set and support for complex range queries. A major distinction from Chord and Tapestry is that there is no hashing of search keys of resources, which allows related resources to be near each other in the skip graph; this property makes searches for values within a given range feasible. Another strength of skip graphs is the resilience to node failure in both random and adversarial failure models. As with skip lists, nodes are arranged in increasing order in multiple levels; each node in level i is contained in level i+1 with some probability p (an adjustable parameter).Level 0 consists of one doubly linked list containing all of the nodes in the set. Lists becoming increasingly sparse at higher levels, until the list is composed of just one node. Where skip graphs differ from skip lists is that each level i≥1, will contain multiple lists; membership of a key x in a list is defined by the membership vector m ( x ) {displaystyle m(x)} . The membership vector is defined as an infinite random word over a fixed alphabet, each list in the skip graph is identified by a finite word w from the same alphabet, if that word is a prefix of m ( x ) {displaystyle m(x)} then node x is a member of the list. Skip graphs support the basic operations of search, insert and delete. Skip graphs will also support the more complex range search operation.