Kademlia tornou qualquer par alcançável em poucos saltos ao rotear pela distância XOR

Sistemas ponto a ponto descentralizados não têm um índice para consultar quem detém um arquivo. Inundar a rede é caro demais; um rastreador central anula o propósito.

O Kademlia, de 2002, define a distância como o XOR bit a bit de IDs de 160 bits. Como o XOR é sua própria inversa e é simétrico, a tabela de roteamento de um nó divide os outros IDs conforme quantos bits iniciais diferem, mantendo cerca de um contato por bucket.

Para encontrar um par, um nó consulta o nó conhecido mais próximo do alvo, e cada resposta traz um nó mais próximo, de modo que a distância de busca cai pela metade a cada rodada — cerca de log n saltos. O sistema se autorregenera porque os pares aprendem e divulgam informações ao responder.

Chame o XOR de distância; cada par está próximo de alguém

A distância XOR é simétrica e um nó está próximo de algum contato em cada nível de bits.

As tabelas de roteamento permanecem minúsculas enquanto o alcance é global, então nenhum nó conhece todos.

Cada salto reduz a distância pela metade, proporcionando busca em O(log n) sem diretório.

Consultas e inserções ensinam os nós sobre os pares, então a rede se autorregenera.

Em uma rede sem diretório, escolha uma métrica e deixe cada nó manter um contato por bucket de distância. Cada nó pode então alcançar qualquer outro pelo vizinho conhecido mais próximo, sem precisar de uma lista global.

O Kademlia tornou-se o protocolo de busca da DHT do BitTorrent, do Ethereum e de muitas redes de compartilhamento de arquivos. É a resposta padrão para roteamento sem coordenador em um sistema ponto a ponto de grande porte.