Chord is a distributed hash table (DHT) protocol: every peer and every key is hashed
onto the same circular identifier space (here, an 8-bit ring of 256 slots). A key is
"owned" by its successor — the first node whose identifier is equal
to or follows the key clockwise around the ring. Naively, finding that node could take
n hops by walking node-to-node. Chord avoids that with a
finger table: each node keeps shortcut pointers to the successors of
n + 2⁰, n + 2¹, n + 2², …, letting every hop roughly halve the remaining
distance around the ring.
O(log n) hops on average to reach the key's responsible node.
Chord was introduced by Stoica, Morris, Karger, Kaashoek and Balakrishnan at MIT in
2001. Its logarithmic-hop guarantee, achieved with only O(log n) routing
state per node, made it foundational to later peer-to-peer systems and BitTorrent's
distributed tracker.
A 3D ring of peer nodes hashed into a shared identifier space, showing how a Chord distributed hash table routes a key lookup through finger-table shortcuts in only a handful of hops.
Each node's finger table holds shortcut pointers roughly doubling in reach; forwarding a lookup to the closest preceding finger at each step lets Chord resolve any key in O(log n) hops instead of walking the ring node by node.
Set the ring size and the key to look up, then run a lookup and watch the glowing packet hop across finger-table shortcuts to the node responsible for that key. Toggle finger arcs to see the shortcuts being used at each hop.
Chord's O(log n) hop guarantee with only O(log n) routing state per node — introduced by Stoica et al. at MIT in 2001 — became a foundational building block for later peer-to-peer and distributed storage systems.