Skip graph

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)
    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, 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.[3] 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)}$.[2] Therefore, for a fixed value of p, the search operation is expected to take O(log n) time using O(log n) messages.[2]

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.[2] 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 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 u for 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) 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.[2]

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

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) 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.

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.[2] 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.[2] While other distributed data structures may be able to achieve higher levels of resiliency they tend to be much more complex.

Adversarial failure is difficult to simulate in a large network as it becomes difficult to find worst case failure patterns.[2] 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 \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.[2]