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.
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.
Add node, remove node, generate membership vector, set search start node, set target key, run search trace, run range query, toggle level visibility, simulate random churn burst, reset network.
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.
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.
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.
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.
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.