Home▸Algorithms & AI▸Skip Graph: Decentralized Ordered Search for Peer-to-Peer Networks

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

Explore how skip graphs generalize skip lists into a fully decentralized structure that supports fast ordered search and range queries across peer-to-peer networks without any central coordinator.

Algorithms & AI3DModerate60 FPS

The simulator shows how independently generated random membership vectors cause peer nodes to self-organize into overlapping, multi-level sorted linked lists, and how a search query hops from sparse high levels down to the dense level-0 list to find a target key in an expected logarithmic number of steps, all without any central coordinator computing the layout.

🔬 What It Demonstrates

🎮 How to Use

Add nodes to the network and watch each one generate its own random membership vector and automatically link into the appropriate levels alongside nodes sharing its vector prefix. Pick a starting node and a target key to trace a live search path as it drops from a high level down to level 0. Remove nodes at random to see how neighboring nodes repair their local links and how search performance degrades gracefully rather than breaking under churn. Try a range query to see the level-0 sorted list enumerate every key between two bounds.

💡 Did You Know?

Because membership vectors are generated completely independently by each node with no communication at all, two skip graphs built from the exact same set of nodes will almost never end up with the same level structure twice, yet both will still deliver the same expected logarithmic search performance, a striking example of a useful global property emerging purely from many uncoordinated local coin flips.

⚙ Under the hood

Explore how skip graphs generalize skip lists into a fully decentralized structure that supports fast ordered search and range queries across peer-to-peer networks without any central coordinator.

skip graphpeer-to-peerdistributed systemsdata structuresrange queriesmembership vectordecentralizationchurn

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install