Kademlia hizo que cualquier par fuera alcanzable en pocos saltos mediante el enrutamiento por la distancia XOR

Los sistemas peer-to-peer descentralizados no tienen un índice donde consultar quién posee un archivo. Inundar la red es demasiado costoso; un rastreador central anula el propósito.

Kademlia, de 2002, define la distancia como la XOR bit a bit de identificadores de 160 bits. Como la XOR es su propia inversa y es simétrica, la tabla de enrutamiento de un nodo divide los demás identificadores según cuántos bits iniciales difieren, manteniendo aproximadamente un contacto por cubo.

Para encontrar un par, un nodo consulta al nodo conocido más cercano al objetivo, y cada respuesta aporta un nodo que está más cerca, de modo que la distancia de búsqueda se reduce a la mitad en cada ronda: unos log n saltos. El sistema se autorrepara porque los pares aprenden y difunden información a medida que responden.

Llamemos distancia a la XOR; cada par está cerca de alguien

La distancia XOR es simétrica y un nodo está cerca de algún contacto en cada nivel de bits.

Las tablas de enrutamiento se mantienen diminutas mientras el alcance es global, así que ningún nodo conoce a todos.

Cada salto reduce a la mitad la distancia, lo que da una búsqueda O(log n) sin directorio.

Las consultas y las inserciones enseñan a los nodos sobre sus pares, así que la red se cura a sí misma.

En una red sin directorio, elige una métrica y deja que cada nodo mantenga un contacto por cubo de distancia. Cada nodo puede entonces alcanzar a cualquier otro mediante el vecino conocido más cercano, sin necesidad de una lista global.

Kademlia se convirtió en el protocolo de búsqueda de la DHT de BitTorrent, de Ethereum y de muchas redes de intercambio de archivos. Es la respuesta estándar al enrutamiento sin coordinador en un sistema peer-to-peer grande.