Kademlia: A Peer-to-Peer Information System Based on the XOR Metric (2002)
September 13, 2025Mainline DHT, the distributed hash table used by BitTorrent, is based on Kademlia. In Kademlia, both nodes and keys are identified by 160-bit identifiers. The distance between two identifiers is defined as their bitwise XOR interpreted as an integer. To locate other nodes or values, a node repeatedly sends RPC requests to peers whose addresses it knows and that appear closer to the target according to the XOR metric.
Each node’s address is composed of an IP address, a UDP port, and its identifier. A node maintains a routing table consisting of 160 \(k\)-buckets. The \(i\)-th bucket contains contacts whose distance from the node lies in the interval \([2^i, 2^{i+1})\). Each bucket can hold up to k entries, sorted by the time last seen, with the least recently seen at the head and the most recently seen at the tail.
Every request and response carries the sender’s identifier. When a node receives a message, it updates the appropriate \(k\)-bucket. If the sender is already present, it is moved to the tail. If the sender is not present and the bucket has fewer than \(k\) entries, it is appended. If the bucket is full, the recipient pings the least recently seen node at the head of the list. If that node fails to respond, it is evicted and the new contact is inserted; if it responds, it is moved to the tail and the new contact is discarded.
The protocol defines four RPCs: PING, STORE, FIND_NODE, and FIND_VALUE.
PING checks whether a node is online.
STORE requests a node to store a ⟨key, value⟩ pair.
FIND_NODE sends an identifier and asks the recipient to return up to k contacts it knows that are closest to that identifier.
FIND_VALUE behaves like FIND_NODE but returns the stored value if the recipient has it.
The essential operation in Kademlia is the node lookup.
To find the nodes closest to a given identifier, the initiator selects up to α of the closest contacts it knows and sends them FIND_NODE requests in parallel.
As responses arrive, the initiator continues by querying new nodes that are closer to the target, again selecting up to α at a time.
If no closer nodes are discovered, the initiator queries all of the k closest nodes it has not yet contacted.
The lookup terminates once the initiator has queried and received responses from the k closest nodes it knows.
To maintain the freshness of its routing table, a node performs lookups for random identifiers. If no lookup has been performed into the range of a bucket within an hour, the node selects a random identifier in that range and executes a lookup, thereby refreshing the bucket.
When joining the network, a node must already know at least one participant. It inserts that address into the appropriate \(k\)-bucket and performs a lookup for its own identifier. This both populates its routing table and inserts its own address into the tables of other nodes. It then refreshes all buckets more distant than its closest neighbor.
To store a value, a node locates the \(k\) closest nodes to the key and issues STORE RPCs to them.
Nodes that hold values re-publish them every hour to maintain persistence, and the original publisher republishes its values every 24 hours.
To retrieve a value, a node performs a lookup using FIND_VALUE.
The search halts immediately if any node returns the value.
Once a lookup succeeds, the requester caches the value at the closest node it encountered that did not already possess it.
Replication occurs whenever a node discovers another node that is closer to a key than itself. In this case, it transfers the value to the new node without deleting its own copy. The lifetime of cached entries is set to be exponentially inversely proportional to the number of nodes between the caching node and the node whose identifier is closest to the key.