Key Question

How does Kademlia find a node or value in O(log n) steps without knowing all nodes?

Deep Dive

Node Lookup: Iterative Deepening

Kademlia’s lookup is an iterative, parallelized crawl toward the target.

lookup(target_id):
  1. Pick α closest nodes from local k-buckets (default α=3)
  2. Send parallel FIND_NODE requests to all α
  3. Each response returns k closest nodes to target from that peer
  4. Merge results, pick the α closest unqueried nodes
  5. Repeat until no closer nodes are found
  6. Return the k closest nodes to target

Example: N=1000 nodes, looking up key = 0xdeadbeef

  Hop 1: Query 3 nodes, each returns ~20 close nodes
  Hop 2: Query closest unknown nodes from those ~60
  Hop 3: Getting warmer...
  ...
  Hop ~10: Found the k closest — done!

  log₂(1000) ≈ 10 hops. Each hop cuts distance roughly in half.

Lookup visualization (each arrow = FIND_NODE request):

  ┌──┐     ┌──┐     ┌──┐
  │Q1│────→│N1│────→│N4│
  └──┘     └──┘     └──┘
    │        │        │
    │   ┌──┐ │   ┌──┐ │
    └──→│N2│ └──→│N5│ │
        └──┘     └──┘ │
    │        │         │
    │   ┌──┐ │   ┌──┐ │
    └──→│N3│ └──→│N6│ │
        └──┘     └──┘ │
                      │
                 ┌────┘
                 ▼
              ┌──┐
              │T │  ← target node (or k closest)
              └──┘

The α Parameter

• α=1: sequential — one hop at a time. Low bandwidth, high latency.
• α=3 (default): three parallel queries. 3x bandwidth, but ~3x faster in practice.
• α=∞: flood — degenerate into Gnutella.

The sweet spot is α=3. It gives redundancy against slow/dead nodes without wasting bandwidth.

Storage Protocol

PUT(key, value):
  1. Find the k closest nodes to key (via lookup)
  2. Send STORE(key, value) to all k
  3. Each receiver stores locally (usually in memory DB)

GET(key):
  1. Find the k closest nodes to key (via lookup)
  2. Send FIND_VALUE to all k
  3. If a node has the value → returns it immediately
  4. Otherwise acts like FIND_NODE (returns close nodes)
  5. Iterate until value found or can't get closer

Republishing

Nodes republish their key-value pairs every hour. This handles churn: if a node that stored your value goes offline, the new closest node will get it on the next republish.

Check Your Understanding

1. If a Kademlia network has 10,000 nodes, roughly how many hops should a lookup take?
2. What advantage does α=3 give over α=1 during a lookup?
3. Why does PUT store on k closest nodes instead of just the single closest node?

The “So What?”

The iterative, parallelized lookup is what makes Kademlia practical. It handles churn naturally — if a node goes silent, the parallel queries route around it. The same mechanism works for both node discovery and value retrieval, making the protocol trivially simple to implement.

✏️ Exercises

Exercises: DHTs & Kademlia

Exercise 1

In Kademlia with 8-bit IDs, what is the XOR distance between node IDs 11001010 and 11011010?

Exercise 2

Why does Kademlia use parallel queries (α > 1) instead of sequential queries (α = 1)? What’s the trade-off?

Exercise 3

What problem does S/Kademlia’s disjoint path routing solve, and how does it protect against an attacker who controls ~30% of the network?

Exercise 4 (Challenge)

In a Kademlia network with N = 100,000 nodes and k = 20, assume each node has a fully populated routing table. How many distinct nodes can a single node know about (maximum)? How many hops should a lookup take in the worst case?

  11001010
⊕ 11011010
──────────
  00010000  = 16