optional · CSS study notes
Distributed Hash Tables (DHT)
🧭
On this page — click any heading below to jump straight to it. ⬅️ Back to P-II.II. Computer Communications & Networks
OSI Layer: Application Layer (L5–L7)
Definition
A Distributed Hash Table (DHT) is a decentralised system that provides a lookup service similar to a hash table — (key, value) pairs are distributed across many nodes in a P2P network, and any node can efficiently locate the value for a given key without any central coordination or index server.
Core Property
Each node is responsible for a defined portion of the key space (typically determined by hashing both keys and node identifiers into the same numeric space). A lookup is resolved by routing the query through a sequence of nodes, each getting progressively "closer" to the key's owner — most well-known DHT designs achieve this in O(log N) hops for a network of N nodes, rather than needing a central index or flooding the whole network.
Types of DHT Algorithms (Classification)
1. Chord
- Arranges nodes and keys on a logical ring using consistent hashing; each node maintains a small routing table ("finger table") pointing to nodes at exponentially increasing distances around the ring.
- Lookup proceeds by jumping to the finger table entry closest to (but not past) the target key, converging in
O(log N)hops. - Simple, well-understood, mathematically clean design — the canonical academic reference DHT.
2. Kademlia
- Uses an XOR-based distance metric between node/key identifiers, which has the useful mathematical property of being symmetric and enabling efficient, self-correcting routing tables ("k-buckets").
- Highly resilient to churn (nodes joining/leaving) and widely deployed in practice — this is the DHT used by BitTorrent's trackerless mode and several other real-world P2P systems.
3. Pastry
- Routes based on matching address-prefixes of node identifiers (similar in spirit to how IP routing tables work with longest-prefix matching), converging on the destination node one matching digit at a time.
- Also supports flexible placement (locality-awareness) so that routing can favour physically/topologically nearby nodes.
4. CAN (Content-Addressable Network)
- Maps the key space onto a virtual multi-dimensional Cartesian coordinate space, with each node owning a zone of that space; routing moves toward the target coordinate through neighbouring zones.
- Scales well but generally has higher lookup latency (more hops) than Chord/Kademlia for the same network size, since routing progress per hop depends on the number of dimensions chosen.
Comparison Table
| DHT | Structure | Distance Metric | Lookup Complexity | Notable Use |
|---|---|---|---|---|
| Chord | Logical ring | Numeric ring distance | O(log N) | Academic reference design |
| Kademlia | Binary tree / k-buckets | XOR distance | O(log N) | BitTorrent trackerless DHT |
| Pastry | Prefix-matching tree | Prefix match length | O(log N) | Locality-aware overlay systems |
| CAN | d-dimensional coordinate space | Cartesian distance | O(d·N^(1/d)) | Content-addressable storage research |
Why DHTs Matter
- Enable decentralised peer discovery without any central tracker/server — e.g., BitTorrent's "trackerless" mode allows a torrent to keep working even if the original tracker server goes permanently offline, because peers use a Kademlia-based DHT to keep finding each other directly.
- No single point of failure, and the system scales gracefully as more nodes join, since responsibility for the key space is automatically redistributed among a growing/shrinking set of nodes.
CSS Exam Angle
- This is a technical/niche topic — a solid, concise definition, the general O(log N) lookup property, plus at least one named algorithm (Chord or Kademlia) with one real-world use case (BitTorrent) is usually sufficient to score well without over-elaborating.
- If the question specifically asks to "classify" DHT algorithms, naming all four (Chord, Kademlia, Pastry, CAN) with their one distinguishing structural idea each demonstrates strong depth.
- Connect this topic explicitly to "Peer To Peer Systems" — a DHT is the mechanism that makes structured P2P efficient without centralisation.
Example
BitTorrent's trackerless mode allows a torrent to keep working indefinitely even if the original tracker server goes offline permanently, because peers use a Kademlia-based DHT to keep finding each other directly — a widely-cited real-world DHT deployment.
Likely Questions
- What is a Distributed Hash Table? Explain its role in peer-to-peer systems.
- Classify DHT algorithms (Chord, Kademlia, Pastry, CAN) by their routing/distance mechanism.
- Why does BitTorrent's trackerless mode not require a central server to function?
- What is the typical lookup complexity of a DHT, and why does this matter for scalability?
📜 Past-Paper Questions & Structured Answers
Questions are paraphrased; answer focus is suggested guidance, not an official marking scheme.
Coverage check: no standalone DHT, Chord, Kademlia, Pastry or CAN question was located in the reviewed 2016–2026 descriptive papers or the available 2024–2026 Paper-II MCQ sheets. “Likely Questions” above are practice, not verified past-paper questions.
Related preparation: DHTs explain resource lookup in structured P2P overlays. For the 2026 one-mark P2P item, answer that peers can be clients and servers; do not add an unnecessary DHT algorithm. See Peer To Peer Systems. For 2024 overlays/CDNs (7 marks), concentrate on performance, scalability and a calculation: Content Distribution Networks.