Kademlia: A Peer-to-Peer Information System Based on the XOR Metric

Maymounkov, Mazieres

distributed hashtable dht network storage content addressable networking

@article{maymounkov:p2p-2002,
  title={{Kademlia}: A Peer-to-Peer Information System
         Based on the {XOR} Metric},
  author={Maymounkov, P. and Mazi\`{e}res, D.},
  journal={Peer-to-Peer Systems},
  pages={53--65},
  year={2002},
  publisher={Springer-Verlag}
}

Another example, Kademlia~\cite{maymounkov:p2p-2002}, takes the same basic approach of assigning nodes and content identifiers within the same space, and then mapping content to the closest nodes. However, the distance between any two Kademlia identifiers is taken as the exclusive-or of the identifiers, rather than distance within a standard numeric ordering. Kademlia nodes maintain a set of lists, each associated with a distance from the node, as their routing tables. In locating the controlling node for an identifier, a node uses those lists to look up and contact the $k$ nodes closest to that identifier (the distance metric is unidirectional). Those nodes in turn relay the closest nodes they know of, which the original query node then contacts, and so on recursively until the controlling node is found. This effectively carries out a binary search over the keyspace, again providing $O(\log n)$ guarantees. Kademlia nodes are seeded into the network by being pointed at another node discovered out of band; the relatively large routing lists are then populated by sniffing identifiers from all traffic, including responders to the node's queries, external queries, and data store events.