User:RossK91/sandbox

Skip Graph
Type	Distributed Data Structure
Invented	2003
Invented by	James Aspnes, Gauri Shah
Time complexity in big O notation Operation Average Worst case Search O(log n) O(log n) Insert O(log n) O(log n) Delete O(1) O(1) Space complexity Space O(log n) O(log n)

Skip graphs are a kind of distributed data structure based on skip lists. 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 other 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 fails. Also, constructing, inserting, searching and repairing a skip graph that was disturbed by failing nodes can be done by simple and straightforward algorithms.

Description

A skip graph is a distributed data structure based on skip lists designed to resemble a balanced search tree. Skip graphs offer several benefits over other Distributed hash table schemes such as Chord (peer-to-peer) and Tapestry (DHT), these benefits include: resource search, addition and deletion in logarithmic time, logarithmic space to store neighbor information, no required knowledge of the number of nodes in a set and finally support for complex range queries. A major distinction from Chord and Tapestry is that there is no hashing of search keys of resources, this 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.

Implementation details

As with skip lists nodes are arranged acceding 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 a Doubly linked list containing all of the nodes in the set. Lists becoming increasingly sparse at each level, eventually a level is composed of singleton nodes. Where skips graphs differ from skip lists is that each level i≥1, will contain multiple lists; membership in a list is defined by the membership vector m(x). The membership vector is defined as an infinite random word over a fixed alphabet, every list in the skip graph is identified by a word w from the same alphabet, if m(x) is a prefix of that word then node x is a member of the list.

Operations

Skip graphs support the basic operations of search, insert and delete. Skip graphs will also support the complex operation range search.

Search

The search algorithm for skip graphs is almost identical to the search algorithm to skip lists however it is modified to run in a distributed system. Searches start at the top level and traverse through the structure, at each level the search traverses the list until the next node contains a greater key. When a greater key is found the search drops to the next level, continuing until the key is found or it is determined that the key is not contained in the set of nodes. If the key is not contained in the set of nodes the largest value less than the search key is returned.

Each node has local variables:

key: The nodes value. neighbor[R/L][level]: An array containing pointers to the right and left neighbor at level i.

search(searchOP, startNode, searchKey, level)
  if(v.key = searchKey) then
      send(foundOP, v) to startNode
  if(v.key < searchKey) then
     
     while level ≥ 0
         if(v.neighbor[R][level].key ≤ searchKey) then
                send(searchOp, startNode, searchKey, level) to v.neighbor[R][level]
                break
         else
                level = level -1
  else
        while level≥0
           if ((v.neighbor[L][level]).key ≥ searchKey) then
               send(searchOp, startNode, searchKey, level) to v.neighbor[L][level]
               break
           else
               level = level-1
   if (level < 0) then
       send(notFoundOp,v) to startNode

Analysis performed by William Pugh shows that on average, s skip list and by extension skip graph contains O (log n${\frac {1}{log(1/p)}}$) levels for a fixed value of p. Given that at most ${\frac {1}{1-p}}$ nodes are searched on average per level, a total of O(log n${\frac {1}{(1-p)(log(1-p))}}$) messages are sent in O(log n${\frac {1}{(1-p)(log(1-p))}}$) time. Therefore for a fixed value of p, the search operation is expected to take O(logn) time using O(logn) messages.

Insert

Insertion is done in two phases and requires that a new node u knows some introducing node v; the introducing node may be any other node currently in the skip graph. In the first phase the new node u uses the introducing node v to search for its own key; this search is expected to fail and return the node s with the largest key smaller than u. In the second phase u inserts itself in each level until it is a singleton at the top level. Insertion at each level is performed using standard doubly linked list operations; the left neighbors next pointer is changed to point to the new node and the right neighbors previous pointer is changed to point to the node.

insert()
search for s
L=0
while true
   insert u into level L from s
   Scan through level L to find s' such which has membership vector matching membership vector of ufor first L+1 characters
   if no s' exists
      exit
   else
      s = s'
      L=L+1

Similar to the search the insert operation takes expected O(log n) expected messages and O(log n) time. With a fixed value of p; the search operation in phase 1 is expected to take O(log n) time and messages. In phase 2 at each level L ≥ 0 u communicates with an average 1/p other nodes to locate s', this will require O(1/p) time and messages leading to O(1) time and messages for each step in phase 2 .

Delete

Nodes may be deleted in parallel at each level in O(1) time and O(log n) messages . When a node wishes to leave the graph it must send messages to its immediate neighbors to rearrange their next and previous pointers .

delete()
for L = 1 to max level, in parallel
  delete u from each level.
delete u from level 0

The skip graph contains an average of O(log n) level; at each level u must send 2 messages to complete a delete operation on a doubly linked list. As operations on each level may be done in parallel the delete operation may be finished using O(1) time and O(log n).

Fault Tolerance

In skip graphs fault tolerance describes the number of nodes which can be disconnected from the skip graph by failures of other nodes . Two failure models have been examined; random failures and adversarial failures. In the random failure model any node may fail independently from any other node with some probability. The adversarial model assumes node failures are planed such that the worst possible failure is achieved at each step, the entire skip graph structure is known and failures are chosen to maximize node disconnection. A drawback of skip graphs is that there is no repair mechanism, currently the only way to remove and to repair a skip graph is to build a new skip graph with surviving nodes.

Random Failure

Skip graphs are highly resistant to random failures, by maintaining information on the state of neighbors and using redundant links to avoid failed neighbors normal operations can continue even with a large number of node failures. While the number of failed nodes is less that O(${\frac {1}{logn}}$) the skip graph can continue to function normally . Simulations performed by James Aspnes show that a skip graph with 131072 nodes was able tolerate up to 60% of its nodes failing before surviving nodes were isolated . While other distributed data structures may be able to achieve higher levels of resiliency they become much more complex and specifically designed to sustain failures. Skip graphs are a much simpler data structure which compensates for the weaker guarantee on resource availability.

References

Category:Graph data structures