Skip graph

Key takeaways

Skip graph belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Skip graph to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Skip graph from memory before moving on to harder problems.

Reference excerpt

Skip graphs are a kind of distributed data structure based on skip lists. They were invented in 2003 by James Aspnes and Gauri Shah. A nearly identical data structure called SkipNet was independently invented by Nicholas Harvey, Michael Jones, Stefan Saroiu, Marvin Theimer and Alec Wolman, also in 2003. Skip graphs 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. In addition, constructing, inserting, searching, and repairing a skip graph that was disturbed by failing nodes can be done by straightforward algorithms.

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

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

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

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Skip graph

Start with the simplest possible case. Write down what Skip graph claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Skip graph before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Skip graph ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Skip graph

In research: Skip graph appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Skip graph in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Skip graph is common in secondary-school and first-year university syllabi. It links to neighbouring topics Graph data structures, so understanding it makes those chapters shorter.
In everyday life: Look for Skip graph outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Skip graph in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Skip graph means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Skip graph out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Skip graph in simple terms?

Skip graphs are a kind of distributed data structure based on skip lists. They were invented in 2003 by James Aspnes and Gauri Shah.

Why does Skip graph matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Skip graph?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Skip graph.