Skip graph

Implementation details

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 ⁠${\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 ⁠${\displaystyle m(x)}$⁠ 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 more complex range search operation.

Search

The search algorithm for skip graphs is almost identical to the search algorithm for skip lists but 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 in a list has the following fields:

key

The node's value.

neighbor[R/L][level]

An array containing pointers to the right and left neighbor in the node's doubly linked at level i.

search(searchOp, startNode, searchKey, level) <b id="mwRQ">if</b> (v.key = searchKey) <b id="mwRg">then</b> <b id="mwRw">send</b>(foundOp, v) to startNode <b id="mwSA">if</b> (v.key < searchKey) <b id="mwSQ">then</b> <b id="mwSg">while</b> level ≥ 0 <b id="mwSw">if</b> (v.neighbor[R][level].key ≤ searchKey) <b id="mwTA">then</b> <b id="mwTQ">send</b>(searchOp, startNode, searchKey, level) to v.neighbor[R][level] <b id="mwTg">break</b> <b id="mwTw">else</b> level = level - 1 <b id="mwUA">else</b> <b id="mwUQ">while</b> level ≥ 0 <b id="mwUg">if</b> ((v.neighbor[L][level]).key ≥ searchKey) <b id="mwUw">then</b> <b id="mwVA">send</b>(searchOp, startNode, searchKey, level) to v.neighbor[L][level] <b id="mwVQ">break</b> <b id="mwVg">else</b> level = level - 1 <b id="mwVw">if</b> (level < 0) <b id="mwWA">then</b> <b id="mwWQ">send</b>(notFoundOp, v) to startNode

Analysis performed by William Pugh shows that on average, a skip list and by extension a skip graph contains ${\displaystyle O\left(\frac{\log n}{\log (1/p)}\right)}$ levels for a fixed value of p. Given that at most ${\displaystyle \frac{1}{1-p}}$ nodes are searched on average per level, the total expected number of messages sent is ${\displaystyle O\left(\frac{\log n}{(1-p)\log (1-p)}\right)}$ and the expected time for the search is ${\displaystyle O\left(\frac{\log n}{(1-p)\log (1-p)}\right)}$. Therefore, for a fixed value of p, the search operation is expected to take O(log n) time using O(log n) 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 the only element in a list at the top level. Insertion at each level is performed using standard doubly linked list operations; the left neighbor's next pointer is changed to point to the new node and the right neighbor's previous pointer is changed to point to the node.

insert() search for <var style="padding-right: 1px;" about="#mwt38" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"var","href":"./Template:Var"},"params":{"1":{"wt":"s"}},"i":0}}]}' id="mwfQ">s</var> <var style="padding-right: 1px;" about="#mwt39" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"var","href":"./Template:Var"},"params":{"1":{"wt":"L"}},"i":0}}]}' id="mwfg">L</var> = 0 <b id="mwfw">while</b> true insert <var style="padding-right: 1px;" about="#mwt40" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"var","href":"./Template:Var"},"params":{"1":{"wt":"u"}},"i":0}}]}' id="mwgA">u</var> into level L from <var style="padding-right: 1px;" about="#mwt41" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"var","href":"./Template:Var"},"params":{"1":{"wt":"s"}},"i":0}}]}' id="mwgQ">s</var> Scan through level <var style="padding-right: 1px;" about="#mwt42" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"var","href":"./Template:Var"},"params":{"1":{"wt":"L"}},"i":0}}]}' id="mwgg">L</var> to find <var style="padding-right: 1px;" about="#mwt43" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"var","href":"./Template:Var"},"params":{"1":{"wt":"s'"}},"i":0}}]}' id="mwgw">s'</var> such which has membership vector matching membership vector of <var style="padding-right: 1px;" about="#mwt44" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"var","href":"./Template:Var"},"params":{"1":{"wt":"u"}},"i":0}}]}' id="mwhA">u</var> for first <var style="padding-right: 1px;" about="#mwt45" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"var","href":"./Template:Var"},"params":{"1":{"wt":"L"}},"i":0}}]}' id="mwhQ">L</var>+1 characters <b id="mwhg">if</b> no <var style="padding-right: 1px;" about="#mwt46" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"var","href":"./Template:Var"},"params":{"1":{"wt":"s'"}},"i":0}}]}' id="mwhw">s'</var> exists exit <b id="mwiA">else</b> <var style="padding-right: 1px;" about="#mwt47" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"var","href":"./Template:Var"},"params":{"1":{"wt":"s"}},"i":0}}]}' id="mwiQ">s</var> = <var style="padding-right: 1px;" about="#mwt48" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"var","href":"./Template:Var"},"params":{"1":{"wt":"s'"}},"i":0}}]}' id="mwig">s'</var> <var style="padding-right: 1px;" about="#mwt49" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"var","href":"./Template:Var"},"params":{"1":{"wt":"L"}},"i":0}}]}' id="mwiw">L</var> = <var style="padding-right: 1px;" about="#mwt50" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"var","href":"./Template:Var"},"params":{"1":{"wt":"L"}},"i":0}}]}' id="mwjA">L</var> + 1

Similar to the search, the insert operation takes expected O(log n) 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() <b id="mwrQ">for</b> L = 1 to max level, in parallel <b id="mwrg">delete</b> <i id="mwrw">u</i> from each level. <b id="mwsA">delete</b> <i id="mwsQ">u</i> from level 0

The skip graph contains an average of O(log n) levels; 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 expected O(log n) messages.

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 planned 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 than ${\displaystyle O\left(\frac{1}{\log n}\right)}$ 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 tend to be much more complex.

Adversarial failure

Adversarial failure is difficult to simulate in a large network as it becomes difficult to find worst case failure patterns. Theoretical analysis shows that the resilience depends based on the vertex expansion ratio of the graph, defined as follows. For a set of nodes A in the graph G, the expansion factor is the number of nodes not in A but adjacent to a node in A divided by the number of nodes in A. If skip graphs have a sufficiently large expansion ratio of ${\displaystyle \mathrm{\Omega }\left(\frac{1}{\log n}\right)}$ then at most ⁠${\displaystyle O(f\log n)}$⁠ nodes may be separated, even if up to f failures are specifically targeted.