DHT: Inside Kademlia, Chord, and Pastry

The home page introduced the concept of DHTs. Here we go a level deeper: the actual structure of routing tables, Kademlia's lookup procedure, how it compares with Chord and Pastry, how DHTs cope with churn (nodes constantly joining and leaving), real-world deployments and attack resistance, and finally the technical limits and practical gaps between theory and reality.

Routing tables: designing the "shortcut list"

The heart of a DHT is the small routing table each node keeps. Chord maintains a finger table (the nodes responsible for positions 2^k ahead; m entries, where m is the hash bit-length), while Kademlia keeps k-buckets that collect nodes per distance range. Both share the same principle: keep coarse knowledge of distant nodes and fine-grained knowledge of nearby ones, so that every hop at least halves the distance to the target. Table size stays O(log n), so even in a million-node network each node manages only a sliver of knowledge.

In Kademlia, a 160-bit node ID space (the original paper used SHA-1) calls for up to 160 buckets, where bucket i holds up to k nodes (k = 20 in the original paper) whose distance from self falls between 2^i and 2^(i+1)-1. Node IDs come from a hash function, so nodes are spread uniformly across the ID space rather than clustering around self; buckets are split to keep routing precise in the vicinity of self, leaving far buckets coarse and nearby ones fine-grained. When a full bucket discovers a new node, Kademlia pings the least-recently-seen node in that bucket: if it answers, the incumbent stays and the newcomer is discarded, and only a silent node is evicted. This survival-checked, incumbent-first replacement policy naturally encodes the rule of thumb that long-lived nodes tend to keep surviving.

Kademlia lookups: XOR distance and α-parallel search

Kademlia defines the "distance" between nodes as the XOR of their IDs. This metric is symmetric (A-to-B equals B-to-A), has properties resembling a triangle inequality, and meshes beautifully with the bucket structure. A node looking up a key queries the α closest nodes it knows (typically 3) in parallel, learns about even closer nodes from the replies, and repeats. Since distance strictly shrinks each step, lookups converge in O(log n) steps.

1. Pick the α nodes closest to the target key from your own k-buckets and send FIND_NODE (or FIND_VALUE, for a value lookup) to all of them in parallel.
2. Merge the "even closer nodes" returned in the replies into your known closest-nodes list.
3. Pick the α closest nodes you have not yet queried and repeat the round.
4. Once the closest k nodes stop changing between rounds, stop the search, since it has converged.
5. For FIND_VALUE, stop as soon as any node along the way is found holding the value.

For a network of n nodes, the hop count stays O(log n). Even at a scale of a million nodes, the distance space shrinks by roughly half on every hop, so the target is reached within a handful of round trips. A larger α increases traffic per round but makes lookups less sensitive to unresponsive (timed-out) nodes, so implementations tune α as a latency-versus-bandwidth trade-off.

Comparison with Chord: ring structure versus XOR distance

Chord, the other classic DHT design, places nodes and keys on a single ring (a circle from 0 to 2^m-1) and defines the owner of a key as "the nearest node whose ID is greater than or equal to the key" (its successor). The finger table points to positions 2^0, 2^1, ..., 2^(m-1) ahead of self, so lookups always proceed as a sequence of one-directional hops shrinking clockwise around the ring. Here is how it compares with Kademlia.

Kademlia tends to win in production not only because parallel lookups cut latency, but because it needs no explicit maintenance protocol (the equivalent of Chord's stabilize/fix_fingers); ordinary query traffic itself keeps the table fresh.

Pastry: prefix routing with proximity awareness

A design frequently cited alongside Kademlia and Chord in the DHT literature is Pastry, proposed by Rowstron and Druschel (2001, Microsoft Research / Rice University). Where Chord and Kademlia route by numeric "distance," Pastry inherits from earlier overlay work (Plaxton trees and Tapestry) and routes by prefix match on node IDs: how many leading digits a node shares with the target.

Node IDs are typically 128 bits, treated as a string of hex digits (b = 4 bits each). The routing table is a grid: rows correspond to shared-prefix length, columns to the 16 possible next hex digits. An entry in row r points to a node that shares the first r digits with self but diverges at digit r+1. Alongside this table, each node keeps a leaf set (the numerically closest nodes on either side by ID, essentially Chord's successor list) and a neighborhood set chosen for physical network proximity.

Routing itself is simple: a node forwards a message to a routing-table entry that shares at least one more prefix digit with the target than itself; if none exists, it forwards to whichever leaf-set member is numerically closest to the key. Since the shared prefix grows by at least one digit per hop, the hop count is O(log₁₆ n), a smaller constant factor than Chord or Kademlia's O(log₂ n).

Pastry's defining feature is proximity-aware routing-table construction. When multiple candidate nodes share the same prefix for a given table slot, Pastry picks whichever has the lowest measured round-trip time, rather than one determined purely by ID arithmetic. This keeps not just the hop count low but the physical distance per hop low too; the original paper reports simulations where the ratio of actual latency to direct-link latency (the Relative Delay Penalty) stays close to a small constant. This is a deliberate contrast with Chord and Kademlia, whose path selection is driven purely by computation over the ID space.

Research systems built on Pastry include PAST, a large-scale persistent storage utility using replication and caching; SCRIBE, a publish/subscribe multicast system built on trees formed by reversing Pastry's routing paths; and Squirrel, a web-caching design. The Java-based FreePastry was the reference implementation widely used in this line of research.

What matters most here is the contrast: Pastry, alongside Chord, CAN, and Tapestry, still shows up constantly as a standard point of comparison in distributed-systems courses and DHT papers, yet it has essentially no large-scale production deployment comparable to BitTorrent's Mainline DHT, IPFS, or discv5. Its ideas, prefix routing and proximity-aware table construction, influenced later work, but Pastry itself is the archetype of a DHT that is widely cited in research while never seeing real-world adoption, a very different fate from the path Kademlia took.

The battle against churn: bucket refresh and republishing

The reality of P2P is churn: nodes cycling in and out on timescales of minutes to hours. Measurement studies show heavy-tailed session-time distributions: many short-lived nodes mixed with a few long-lived ones. Kademlia's routing-table maintenance leans on this same session-length signal (see "Routing tables" above). Periodic value republishing and bucket refreshes likewise guard against knowledge rot under churn.

• Bucket refresh: in the original Kademlia paper, any bucket that has not been queried for a set interval (around an hour) triggers a lookup on a random ID within that bucket's distance range, actively keeping the table fresh.
• Value republishing: stored values carry an expiration (24 hours in the original paper), and before it lapses the node holding a value re-runs FIND_NODE to confirm the current set of responsible nodes and redistributes the value, preventing data loss as responsible nodes turn over.
• What k = 20 actually means: a larger k adds redundancy per bucket, tolerating simultaneous departures of several nodes, at the cost of more maintenance traffic. BitTorrent's Mainline DHT (BEP 5) uses k = 8, smaller than the original paper's default; in practice, k is tuned to the expected network size, churn rate, and use case.

Real-world deployments

Kademlia-family DHTs are not just an academic proposal; they underpin several large-scale P2P systems in production.

Even systems that all call themselves "Kademlia" differ in ID length, k, α, and message formats. When designing or implementing a DHT, don't simply reuse the original paper's defaults; revisit the parameters based on expected node count, churn rate, and acceptable latency.

Attack resistance: Sybil, Eclipse, and S/Kademlia

Because open DHTs let anyone join as a node, they are structurally vulnerable to Sybil attacks (one party faking a large number of node IDs) and to Eclipse attacks, where a target node's neighborhood is surrounded by malicious nodes. Since Kademlia's routing table is a purely mechanical function of distance, an attacker who can mint enough IDs close to a target key can dominate the query paths leading to it.

• S/Kademlia (Baumgart & Mies, 2007) is the classic countermeasure: it ties node ID generation to a crypto puzzle (a costly hash computation), raising the cost of minting large numbers of IDs.
• S/Kademlia also proposes disjoint-path lookups: instead of a single path, the search advances along d independent paths in parallel, so the correct result still converges by majority even if some paths pass through malicious nodes.
• Because anyone can observe DHT traffic, there is also a privacy consideration: the source IP address of a lookup query can reveal something about a node's usage patterns.

A common misconception: some assume "a DHT is a distributed database that can store arbitrary data," but real Kademlia-family DHTs are optimized to store relatively small values per key (peer info, pointers to metadata, and the like), not bulk data itself. Another misconception is that "using a DHT makes you anonymous"; DHT traffic itself exposes IP addresses, so achieving anonymity requires additional design, along the lines discussed in NAT traversal and attacks and defenses.

Technical limits and practicality: the gap between theory and reality

Every design covered so far comes with a clean O(log n) guarantee on paper, but running or designing a real DHT surfaces several constraints that the theoretical model does not capture.

• Long-tailed lookup times: the O(log n) hop bound assumes the routing table is populated entirely with live nodes. In practice, nodes go offline abruptly with no explicit leave message, so a routing table always carries some fraction of dead entries. Queries to those entries wait out a timeout before falling back to the next candidate, so while the average hop count stays close to theory, the distribution of lookup times has a non-trivial long tail.
• The reachability wall: DHT protocols implicitly assume any node can be contacted directly, but a substantial share of real internet hosts sit behind NAT or firewalls and cannot be reached from outside. Measurement studies of the BitTorrent Mainline DHT report that a non-negligible fraction of observed nodes are unreachable; most implementations cope by classifying Kademlia nodes as "good" (responsive), "questionable," or "bad" (unresponsive), and only recommending reachability-confirmed nodes to others.
• Limited query expressiveness: a DHT fundamentally supports exact-key lookup (get) and nothing more, with no range queries, full-text search, sorting, or joins. Layering these on top requires extra structures such as prefix hash trees, or ultimately falling back to a centralized index server.
• Weak consistency guarantees: most DHT implementations offer no transactions or linearizability. Under heavy churn, concurrent puts and gets can race, and replicas can briefly diverge. This is why DHTs are suited to small, infrequently-changing data where staleness is cheap (peer info, pointers to metadata) and not designed as an authoritative store of true state.

Given these limits, production systems treat a DHT not as the single source of truth but as a supporting discovery layer. IPFS uses its DHT to find provider records (who holds a piece of content), not to store the content itself; Ethereum's discv5 handles node discovery alone, leaving consensus to an entirely separate protocol layer discussed in distributed consensus. A DHT is a mature, reliable answer to the narrow question "given a key, who is responsible for it." Expect more from it, such as coordination or consistent state, and the gap between theory and reality catches up with you.