Peer-to-Peer and Distributed Hash Tables

In 1999 a college freshman called Shawn Fanning released Napster, and within a year tens of millions of people were trading music files with each other. There was no giant server farm holding the songs — the songs lived on the users' own machines. Each laptop that downloaded a track immediately became a place others could download it from. The more people joined, the more capacity the system had. This was the mainstream world's first taste of an idea that quietly powers BitTorrent, IPFS and every blockchain today: the peer-to-peer (P2P) network, where there is no "the server" — every node is a server and a client at once.

The client–server model you already know draws a hard line: clients ask, the server answers, and the server is the sole keeper of the data. It is simple and it works — until the server is the bottleneck, the single point of failure, and the bill. P2P erases that line. This page is about why that erasure is powerful, the one hard problem it creates — how do you find who has what, with no central index? — and the elegant data structure, the Distributed Hash Table, that answers it in roughly \log_2 N hops across a million machines.

Client–server vs peer-to-peer

The contrast is worth drawing sharply, because it explains both what P2P buys you and what it costs.

	Client–server	Peer-to-peer
Roles	fixed: clients ask, server answers	symmetric: every node is both
Data lives	on the server	spread across the peers
Adding users	adds load, not capacity	adds capacity and load
Failure of one node	server down → everything down	one peer down → barely noticed
Who pays for bandwidth	the operator	the peers themselves
Hard part	scaling the server	coordination with no boss

The killer property is the third row. In client–server, ten thousand new users are ten thousand new demands on one machine. In P2P, each new peer arrives carrying its own upload bandwidth, disk and CPU, so the system's total capacity grows with its popularity. This is why a wildly popular BitTorrent file downloads faster when more people want it — the opposite of a website buckling under a traffic spike. P2P is self-scaling.

But erasing the central server also erases the central directory. On the web, you ask one known machine "give me this page" and it just knows. In a swarm of a million equal peers with no boss, when you want the file with a given name, who do you even ask? That is the lookup problem, and it is the whole game.

The lookup problem: two bad answers and one good one

Suppose the network holds a key k (say the hash of a file) somewhere, on one of N peers, and you want to fetch it. With no central index, how do you locate the peer that holds it? History tried three answers.

A central index (Napster). The files are P2P but a central server keeps the catalogue of who-has-what. Fast lookups — one question — but the index is a single point of failure and, famously, a single point of lawsuit. Napster was shut down by suing one machine.
Flooding an unstructured overlay (Gnutella). No index at all. To find a key you ask your neighbours, who ask their neighbours, out to some hop limit (a "time to live"). It is fully decentralised and robust, but the cost is brutal: a single search can touch a large fraction of the network — O(N) messages — and popular queries drown the links while rare items may never be found within the TTL. It does not scale.
A structured overlay: the Distributed Hash Table. Give every peer and every key a position in the same address space, by a rule everyone agrees on, so that from a key you can compute which peer should hold it and walk there deliberately in a handful of hops — no index, no flooding. This is the winning idea, and the rest of the page builds it.

Unstructured overlays (Gnutella, early Kazaa) wire peers together arbitrarily and search by broadcast: simple, resilient to churn, great for fuzzy "who has something like this" queries, terrible at scaling exact lookups. Structured overlays (Chord, Kademlia, Pastry) impose a precise geometry on the peers so that exact-key lookup becomes a short, guided walk. The DHT is the structured answer.

The Distributed Hash Table, built on a ring

A hash table on one machine maps a key to a bucket by hashing. A Distributed hash table does the same thing across thousands of machines: it maps every key to the peer responsible for it, and lets any peer find that responsible peer quickly. The cleanest concrete design is Chord (MIT, 2001), and its heart is a circle.

Take an m-bit hash function (Chord used SHA-1, so m = 160) and imagine its 2^m possible outputs laid around a ring, 0 at the top wrapping back to 2^m - 1. Now hash two different kinds of thing onto that same ring:

each peer, by hashing its IP address → a point on the ring (its node ID);
each key, by hashing the key → a point on the ring.

The assignment rule is then breathtakingly simple: a key is stored on the first peer whose ID is equal to or clockwise-after the key's position. That peer is the key's successor, written \text{successor}(k). Every key belongs to exactly one peer, every peer owns the arc of the ring leading up to it, and there is no central table saying so — you just hash and walk clockwise. This is consistent hashing, and its great virtue is what happens when peers come and go.

When a peer joins, it hashes to a spot and takes over just the slice of keys between it and its predecessor — only its immediate neighbour has to hand over a few keys; the rest of the ring is untouched. When a peer leaves (or crashes), its keys fall to its successor. Compare that to a naïve "key mod N" scheme, where changing N by one reshuffles almost every key. Consistent hashing moves only O(1/N) of the keys per join or leave — that is the property that makes a DHT survive constant membership change.

Finger tables: why lookup is O(\log N)

Storing keys at successors is only half the design. The other half is finding the successor of a key quickly from anywhere on the ring. If every peer knew only its immediate clockwise neighbour, a lookup would have to shuffle one peer at a time — up to N hops around the circle. Useless at scale.

Chord's trick is the finger table: each peer keeps m shortcuts, where finger i points to the successor of the position halfway, a quarter, an eighth … around the ring from itself — that is, the successor of (n + 2^{i}) \bmod 2^m for i = 0, 1, \dots, m-1. The fingers reach exponentially further around the circle. To look up a key, a peer forwards the query to the finger that lands closest to, without overshooting, the key's position. Each hop at least halves the remaining distance to the target — exactly like binary search — so the whole lookup finishes in:

A lookup resolves in O(\log_2 N) hops with high probability, where N is the number of peers.
Each peer stores only O(\log_2 N) finger entries — routing state grows logarithmically, not linearly, in the size of the network.

Put numbers on it: across a million peers, \log_2(10^6) \approx 20. A key anywhere in a million-machine network is found in about twenty hops, with each peer remembering only about twenty others. That is the payoff — global reach from tiny local knowledge.

Walk the ring yourself

The demo below builds a small Chord-style ring in pure logic — no network needed. It hashes some peers onto a ring of size 2^6 = 64, places keys at their successor, then does two kinds of lookup from a starting peer: a plain one-hop-at-a-time walk around the successors, and a finger-table walk that jumps in halving strides. Watch the hop counts diverge as the ring grows.

// ---- A tiny Chord ring, ring size 2^m = 64 ---- const M = 6; const RING = 1 << M; // 64 identifier slots // Our peers' IDs (in a real system these come from hashing IPs). const nodes = [1, 8, 14, 21, 32, 38, 42, 48, 51, 56].sort((a, b) => a - b); // successor(k): first node clockwise at-or-after position k (wrapping). function successor(k) { for (const n of nodes) if (n >= k) return n; return nodes[0]; // wrapped past the top -> first node } // Where does each key live? Key = its successor node. for (const key of [24, 54, 5, 39]) { console.log(`key ${key} is stored on node N${successor(key)}`); } // ---- Lookup 1: naive, one successor hop at a time ---- function naiveHops(start, key) { const target = successor(key); let cur = start, hops = 0; while (cur !== target) { const i = nodes.indexOf(cur); cur = nodes[(i + 1) % nodes.length]; // step to the next node clockwise hops++; } return hops; } // ---- Lookup 2: finger table, jumping in halving strides ---- // finger[i] of node n = successor(n + 2^i) mod RING, for i = 0..M-1. function fingers(n) { return Array.from({ length: M }, (_, i) => successor((n + (1 << i)) % RING)); } function fingerHops(start, key) { const target = successor(key); let cur = start, hops = 0; while (cur !== target) { const f = fingers(cur); // pick the finger that gets closest to the key without passing it const dist = (x) => (successor(key) - x + RING) % RING; let best = successor((cur + 1) % RING); // fall back to immediate successor for (const cand of f) if (dist(cand) < dist(best)) best = cand; cur = best; hops++; if (hops > nodes.length) break; // safety } return hops; } console.log("\nLooking up key 54 starting from node N1:"); console.log(` naive successor walk: ${naiveHops(1, 54)} hops`); console.log(` finger-table walk: ${fingerHops(1, 54)} hops`); console.log("\nLooking up key 39 starting from node N1:"); console.log(` naive successor walk: ${naiveHops(1, 39)} hops`); console.log(` finger-table walk: ${fingerHops(1, 39)} hops`); console.log(`\nWith ${nodes.length} peers, log2(N) is about ${Math.log2(nodes.length).toFixed(1)} — the finger walk stays near that.`);

The finger walk reaches the target in a couple of jumps where the naïve walk trudges around most of the ring. Scale the ring to a million peers and the gap becomes 20 hops versus 500,000 — the difference between usable and hopeless.

Where DHTs actually run

This is not a museum piece — DHTs are load-bearing infrastructure across the modern internet:

BitTorrent's "trackerless" mode uses a DHT (based on Kademlia) so peers can find each other with no central tracker at all — the swarm coordinates itself.
IPFS (the InterPlanetary File System) addresses content by its hash and uses a DHT to locate which peers hold each block, turning the web into content-addressed P2P storage.
Kademlia — the most deployed DHT design — underlies BitTorrent's DHT, IPFS, and the peer-discovery layer of Ethereum and many blockchains. It uses XOR distance instead of a ring, but the O(\log N) idea is the same.
Amazon's Dynamo and its descendants (Cassandra, Riak) borrowed consistent hashing — the ring — to spread data across storage nodes with minimal reshuffling as the cluster grows and shrinks.

It is tempting to read "no central server" as "no hard problems left." The opposite is true: erasing the server just relocates the difficulty into three chronic headaches you now own.

Churn. Peers are ordinary people's laptops and phones — they join and vanish constantly, far more than a data-centre server ever would. The DHT must continuously repair finger tables and hand off keys as membership changes, or lookups start failing. A big chunk of real DHT engineering is just coping with churn.
Free-riders. When every peer is supposed to contribute upload bandwidth, some selfishly take without giving. BitTorrent had to invent tit-for-tat "choking" to punish leechers — incentive design becomes a core part of the protocol.
Lookup latency. A DHT lookup is many hops, not the single request of client–server. O(\log N) is wonderful asymptotically, but twenty round-trips across the planet is real wall-clock time. Never picture a DHT lookup as "instant like a hash table" — it is a guided tour across the network.

You might ask: why not simply number the peers 0, 1, 2, … and store key k on peer k mod N? Because the moment one peer joins or leaves, N changes, and almost every key's k mod N now points somewhere else — the whole network would have to reshuffle its data on every membership change, which in a churning P2P swarm is constant chaos. Hashing peers onto the same fixed ring as the keys is precisely what avoids this: adding a peer disturbs only the one arc it slots into. That single design choice — consistent hashing — is why DHTs are stable enough to exist at all, and it is why the same trick shows up in load balancers and sharded databases far from any P2P context.