KademliaはXOR距離に基づくルーティングにより、任意のピアへ少ないホップ数で到達可能にした

分散型のピアツーピアシステムには、誰がファイルを保持しているかを調べるインデックスが存在しない。ネットワーク全体へのフラッディングはコストが高すぎ、中央トラッカーはそもそも趣旨に反する。

2002年に登場したKademliaは、距離を160ビットIDのビット単位XORとして定義する。XORはそれ自身の逆演算であり対称であるため、ノードのルーティングテーブルは先頭ビットが何ビット異なるかによって他のIDを分割し、バケットごとにおよそ1件の連絡先を保持する。

ピアを見つけるには、ノードが対象に最も近い既知のノードに問い合わせ、各応答がより近いノードをもたらすため、探索距離はラウンドごとに半減する — およそlog nホップである。ピアは応答する際に学習しゴシップするため、このシステムは自己修復的である。

XORを距離と呼べば、各ピアは誰かに近い

XOR距離は対称であり、ノードは各ビットレベルでいずれかの連絡先に近い。

ルーティングテーブルは小さなままである一方で到達範囲はグローバルであり、どのノードも全員を知ることはない。

各ホップが距離を半減させるため、ディレクトリなしでO(log n)の探索が可能になる。

ルックアップと挿入はノードにピアについて教えるため、ネットワークは自己修復する。

ディレクトリのないネットワークでは、計量を選び、各ノードが距離バケットごとに1件の連絡先を保持するようにする。そうすれば各ノードは既知の最近傍を通じて任意の他のノードに到達でき、グローバルなリストを必要としない。

KademliaはBitTorrentのDHT、Ethereum、そして多くのファイル共有ネットワークのルックアッププロトコルとなった。大規模なピアツーピアシステムにおいてコーディネータなしでルーティングするための標準的な答えである。