Kademlia rendait tout pair joignable en quelques sauts grâce au routage par distance XOR

Les systèmes pair-à-pair décentralisés n'ont pas d'index permettant de savoir qui détient un fichier. Inonder le réseau coûte trop cher ; un traqueur central va à l'encontre du but recherché.

Kademlia, datant de 2002, définit la distance comme le XOR bit à bit d'identifiants de 160 bits. Comme le XOR est son propre inverse et symétrique, la table de routage d'un nœud répartit les autres identifiants selon le nombre de bits de tête qui diffèrent, en conservant environ un contact par compartiment.

Pour trouver un pair, un nœud interroge le nœud connu le plus proche de la cible, et chaque réponse apporte un nœud plus proche, si bien que la distance de recherche est divisée par deux à chaque tour — environ log n sauts. Le système s'auto-répare parce que les pairs apprennent et propagent des informations en répondant.

Appelez le XOR une distance ; chaque pair est proche de quelqu'un

La distance XOR est symétrique et un nœud est proche d'un contact à chaque niveau de bit.

Les tables de routage restent minuscules tandis que la portée est mondiale, si bien qu'aucun nœud ne connaît tout le monde.

Chaque saut divise la distance par deux, ce qui donne une recherche en O(log n) sans annuaire.

Les recherches et les insertions enseignent aux nœuds des pairs, si bien que le réseau se répare lui-même.

Dans un réseau sans annuaire, choisissez une métrique et laissez chaque nœud conserver un contact par compartiment de distance. Chaque nœud peut alors joindre n'importe quel autre par plus proche voisin connu, sans avoir besoin d'une liste globale.

Kademlia est devenu le protocole de recherche de la DHT de BitTorrent, d'Ethereum et de nombreux réseaux de partage de fichiers. C'est la réponse standard au routage sans coordinateur dans un grand système pair-à-pair.