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

Abstract
We describe a peer-to-peer distributed hash table with provable consistency and performance in a fault-prone environment. Our system routes queries and locates nodes using a novel XOR-based metric topology that simplifies the algorithm and facilitates our proof. The topology has the property that every message exchanged conveys or reinforces useful contact information. The system exploits this information to send parallel, asynchronous query messages that tolerate node failures without imposing timeout delays on users.
by Petar Maymounkov and David Mazi`eres

Artigo dos autores do Kademilia.

• A folha mais próxima é aquela que compartilha o maior prefixo
• Xor é unidirecional. Para uma determinada distância e um ponto X te, apenas um ponto a essa distância. Unidirecionalidade garante que buscas pela mesma chave convergem pelo mesmo caminho. Assim, rola de cachear coisas no meio do caminho afim de aliviar hot spots
• Um nó guarda o endereço de k nós situados a [2^i:2^i+1], 0 <= i <= 160. Ou seja, k nós de cada subárvore. Esta lista de nós é chamada k-bucket. Nós antigos ficam mais tempo no balde pois são mais prováveis de ficar.