Questions: Distributed Hash Tables and DHT

Question 1

In a DHT, why can't nodes simply route lookup requests directly to the responsible node, bypassing intermediate hops?

• A. Direct routing is impossible because the hash function is not invertible — you cannot compute the node address from the key
• B. Direct routing would require every node to maintain a complete membership list (O(n) state), which becomes impractical as the system grows to millions of nodes
• C. Direct routing would violate the consistency guarantees required for uniform distribution on the hash ring
• D. The network topology prevents nodes from communicating with non-adjacent nodes on the ring

Answer: (B)

The O(n) state problem is the core scalability barrier. With millions of nodes, a complete membership list is prohibitively large to store and keep synchronized — every join and leave event would require updating every node. DHTs like Chord and Kademlia solve this by maintaining only O(log n) routing state per node, accepting O(log n) hops as the cost. This is fundamentally the same tradeoff as binary search vs. linear scan: spending a little more time (hops) to avoid maintaining a huge index (full membership list).

Question 2

A new node joins a Chord DHT by picking a random ID on the ring. After the join is complete, which node transfers keys to the new node?

• A. The successor of the new node transfers all its keys so the new node can replicate them for fault tolerance
• B. The predecessor of the new node transfers the keys in the range that now falls under the new node's responsibility
• C. Keys are recomputed using a new hash function and redistributed across all nodes to maintain uniform load
• D. Keys remain with their current nodes until the next periodic rebalancing cycle

Answer: (B)

In Chord, each node is responsible for the keys between its predecessor's ID and its own ID on the ring. When a new node inserts itself, it takes over responsibility for a contiguous range of keys that was previously handled by its successor. The successor transfers those keys to the new node. This is the key virtue of consistent hashing: only the new node's immediate successor is affected — O(keys/n) keys move, rather than redistributing all keys as you would in a naive hash table resize.

Question 3

In Kademlia, every lookup query both retrieves the target key and refreshes the querying node's routing table with new information about nearby nodes.

• T. True
• F. False

Answer: True

This is one of Kademlia's architectural advantages. Each iterative lookup contacts nodes close to the target and receives responses that include those nodes' known neighbors. This naturally populates the querying node's k-buckets with fresh, recently-seen node addresses — routing table maintenance is a byproduct of normal operations, not a separate background process. As a result, Kademlia routing tables stay current without dedicated maintenance overhead, which is important in the high-churn peer-to-peer environments where Kademlia is deployed.

Question 4

DHTs eliminate the need for data replication because consistent hashing guarantees that nearly every key is generally accessible on its responsible node.

• T. True
• F. False

Answer: False

Consistent hashing provides key assignment, not fault tolerance. If the node responsible for a key fails, that key becomes temporarily or permanently unavailable unless copies exist elsewhere. Nodes in real systems fail frequently — hard drives die, machines reboot, network partitions occur. Production DHTs (Chord, Kademlia, Amazon Dynamo) replicate each key to k successor nodes precisely to handle failures. When a node fails, its successors already hold the replicas and can serve requests. Consistent hashing minimizes redistribution on membership changes, but data availability under failure requires explicit replication.

Question 5

Explain why the Chord finger table produces O(log n) lookup time, and why this is a better solution than either maintaining a full membership list or routing only to adjacent nodes.

Model answer: Chord's finger table contains pointers to O(log n) nodes spaced at exponentially increasing distances around the ring (1/2, 1/4, 1/8 of the ring away, etc.). When forwarding a query, the node routes to the closest finger that precedes the target key, cutting the remaining ring distance roughly in half with each hop — like binary search. This yields O(log n) hops to reach any key. A full membership list achieves O(1) hops but requires O(n) storage per node and O(n) update messages per join/leave. Routing only to adjacent ring neighbors requires O(n) hops (walking around the ring). Finger tables hit the sweet spot: O(log n) state enables O(log n) hops — both costs grow logarithmically, keeping the system scalable for millions of nodes.

The key insight is that Chord applies binary-search logic to routing: each hop eliminates half the remaining candidate space, just as binary search eliminates half the remaining elements. This is not coincidental — the finger table is designed so that entries cover exponentially larger ranges, ensuring the halving property at every step. The tradeoff analysis (O(n) state for O(1) hops, vs. O(log n) state for O(log n) hops, vs. O(1) state for O(n) hops) is the fundamental design space of distributed routing, and Chord's choice sits at the efficient frontier.