Skip Graph: Decentralized Ordered Search for Peer-to-Peer Networks

From Skip Lists to Skip Graphs

A classic skip list is a single-machine data structure: one process holds a sorted linked list of elements, and it randomly promotes some elements to higher 'express lane' levels, so a search can skip past large chunks of the list instead of walking one node at a time. The height of each element's tower is chosen randomly, typically by flipping a coin and stopping at the first tail, which gives an expected logarithmic number of levels overall and an expected logarithmic search cost. A skip graph asks a harder question: what if there is no single machine holding the list at all, and instead every element is a separate computer somewhere on a network, each responsible only for itself? There is no central builder that decides the tower heights or wires up the levels. Instead, every node independently generates its own random membership vector, a string of random digits (often bits), completely on its own, with no coordination or communication needed to produce it. That single piece of local randomness ends up determining the node's entire role in the emergent global structure. Two nodes that happen to share a long common prefix in their membership vectors will end up linked together at many levels; two nodes with completely different vectors will only ever meet at level zero. Because the process is symmetric and local, skip graphs inherit the skip list's logarithmic search and insertion guarantees while removing the requirement that any one party sees the whole picture. This is the conceptual leap that makes skip graphs a genuinely distributed structure rather than just a networked implementation of a sequential one: the topology is an emergent property of many independent random choices, not the output of a central planning step, which is exactly what a system with thousands of untrusted, unreliable, constantly changing peers needs.

Levels, Membership Vectors, and the Search Path

The structure of a skip graph is defined entirely by how membership vectors partition the nodes into overlapping linked lists. At level 0, every single node in the network belongs to one big doubly linked list, sorted by key, exactly like the bottom rung of a skip list. This guarantees that, worst case, you can always find any key by walking level 0 alone, just slowly. At level i for i greater than zero, a node only belongs to the linked list containing other nodes whose membership vector shares the same first i digits as its own, and within that list nodes are still sorted by key. So a node with membership vector starting '010...' appears in the level-1 list with all other nodes starting '0', and in the level-2 list only with nodes starting '01', and so on, until eventually it is likely alone or with very few peers at its personal maximum level. Since membership vectors are random and roughly half of all nodes share any given first digit, the level-1 lists are about half the size of level 0, level-2 lists about a quarter, and so on, an exponential thinning that mirrors the exponential tower-height distribution in a plain skip list. A search for a target key starts at the highest level of the querying node, where neighbor lists are short but each hop covers a lot of key-space distance, and moves toward the target, dropping down a level whenever the current level's neighbors would overshoot or run out. This produces the same expected O(log n) hop count as a skip list search, because at each level roughly half the remaining candidates are eliminated, but every single hop in a skip graph is also a real network message between two independent, physically separate machines, not a pointer dereference in local memory.

Why Order Beats Hashing for Range Queries

The most consequential design decision separating a skip graph from a classic distributed hash table (DHT) is what happens to the key before it is placed into the network. A DHT such as Chord or Kademlia runs every key through a hash function before deciding where it lives, which is brilliant for load balancing: hashing spreads keys uniformly across the identifier space so no single node becomes a hotspot, and it makes exact-match lookups fast and predictable. But hashing is a one-way scrambling operation, and scrambling destroys the very thing that made the original keys meaningful for many applications, their relative order. Once key 42 and key 43 have been hashed, their hash values could land anywhere in the identifier space, adjacent or a world apart, with no relationship to the fact that 42 and 43 were neighbors in the original ordering. That means a DHT can efficiently answer 'where is the node responsible for this exact key' but cannot efficiently answer 'give me every key between 42 and 100' without essentially checking every node. A skip graph never hashes the key; nodes are ordered and linked by their actual, real key values at every level. This is precisely why the structure supports genuine range queries and ordered traversal: a query can start anywhere in the network, use the multi-level linked lists to jump to the neighborhood of a target range, and then walk level 0 in sorted order to enumerate every matching key, work proportional to the number of results found plus a logarithmic search cost to get there, rather than a full network scan. This property matters enormously for applications like distributed databases, sensor networks reporting continuous measurements, or file systems that need prefix and range lookups, exactly the workloads where an exact-match-only DHT falls short.

Graceful Handling of Churn

Real peer-to-peer networks are not static; machines join, crash, go offline, and rejoin constantly, a phenomenon researchers call churn. A good distributed data structure has to keep working, and keep its performance guarantees, while this constant flux happens underneath it. Skip graphs handle churn gracefully for a structural reason: because each node's position in the hierarchy is determined purely by its own locally generated, independent membership vector, a node joining or leaving only affects the small set of neighbors it shares list membership with at each level, never the global structure and never any centrally maintained index. When a new node arrives, it generates a membership vector, uses an existing node as an entry point, performs a logarithmic-hop search to find its correct sorted position at level 0, and then works upward, splicing itself into each level's linked list wherever its vector prefix matches, an expected O(log n) amount of work touching only a small, localized set of existing nodes. Departures are handled symmetrically: neighbors detect a node is gone, typically through periodic liveness checks or failed hops during a search, and repair their own linked-list pointers to route around the gap, again a local, bounded amount of repair work rather than a global rebuild. Compare this to structures that depend on a globally agreed, centrally computed layout, where a single change can require re-deriving large portions of the structure. Because skip graphs distribute the randomness generation itself, there is also graceful degradation under load: even if repair lags slightly behind a burst of churn, searches degrade smoothly toward the reliable level-0 list rather than failing outright, since the redundancy of overlapping levels means multiple independent paths usually still exist toward any given key.

Where Skip Graphs Are Used in Practice

Skip graphs were introduced by James Aspnes and Gauri Shah in the early 2000s as an answer to a specific gap in the then-fast-growing DHT literature: nobody had a fully decentralized structure that kept both logarithmic search costs and the ability to do range and ordered queries. That combination made skip graphs attractive for distributed database indexing, where applications routinely need 'between' queries, not just exact lookups, and for resource discovery systems where clients search for services matching a range of criteria such as available memory or bandwidth. They have influenced designs for structured overlay networks, distributed file systems that need directory-style prefix search, and peer-to-peer publish-subscribe systems where subscribers register interest in ranges of topics or values. A related and influential relative, SkipNet, pursued similar goals with an emphasis on content locality and administrative control, showing that the core idea, layering multiple randomized linked lists keyed by shared prefixes of independently generated identifiers, is a flexible template rather than a single rigid protocol. It is worth being honest about the tradeoffs too: maintaining multiple levels per node costs more state and more maintenance messages than some DHTs, and skip graphs typically assume a reasonably cooperative network rather than an actively adversarial one, unlike some DHT variants hardened against malicious routing. Still, for any system where preserving key order and answering range queries matters as much as raw lookup speed, the skip graph remains one of the cleanest illustrations of how local, independent randomness at every participant can add up to a coherent, efficient, genuinely leaderless global structure.

Frequently asked questions

Try it live

Everything above runs in your browser — open Skip Graph: Decentralized Ordered Search for Peer-to-Peer Networks and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.