The encyclopedia · Software & IT · Technical decision · 2002
Kademlia made any peer reachable in few hops by routing on the XOR distance
Maymounkov and Mazières' 2002 Kademlia treated XOR of node IDs as a distance, so a node finds any peer in O(log n) hops and gossips found nodes.
New York University
the move
Decentralised peer-to-peer systems have no index to look up who holds a file. Flooding the network is too expensive; a central tracker defeats the point.
Kademlia, from 2002, defines distance as bitwise XOR of 160-bit ids. Since XOR is its own inverse and symmetric, a node's routing table splits other ids by how many leading bits differ, holding about one contact per bucket.
To find a peer, a node queries the closest known node to the target, and each reply brings a node that is closer, so search distance halves each round — about log n hops. The system is self-healing because peers learn and gossip as they answer.
why it works
- XOR distance is symmetric and a node is close to some contact at each bit level.
- Routing tables stay tiny while reach is global, so no node knows everyone.
- Each hop halves the distance, giving O(log n) search with no directory.
- Lookups and inserts teach nodes about peers, so the network heals itself.
what transfers
In a network with no directory, pick a metric and let each node keep one contact per distance bucket. Each node can then reach any other by closest known neighbour, needing no global list.
what came after
Kademlia became the lookup protocol for BitTorrent's DHT, Ethereum and many file-sharing networks. It is the standard answer to routing without a coordinator in a large peer-to-peer system.
references
spotted an error? The archive wants to know.