Dezentrale Peer-to-Peer-Systeme haben keinen Index, in dem nachgeschlagen werden kann, wer eine Datei hält. Das Netzwerk zu fluten ist zu teuer; ein zentraler Tracker untergräbt den Sinn der Sache.
Kademlia aus dem Jahr 2002 definiert Distanz als bitweises XOR von 160-Bit-IDs. Da XOR seine eigene Umkehrung und symmetrisch ist, teilt die Routing-Tabelle eines Knotens andere IDs danach auf, wie viele führende Bits sich unterscheiden, und hält etwa einen Kontakt pro Bucket.
Um einen Peer zu finden, fragt ein Knoten den ihm bekannten Knoten, der dem Ziel am nächsten liegt, und jede Antwort liefert einen Knoten, der näher liegt, sodass sich die Suchdistanz in jeder Runde halbiert — etwa log n Hops. Das System ist selbstheilend, weil die Peers beim Antworten lernen und ihr Wissen weiterverbreiten.
Nenne XOR eine Distanz; jeder Peer ist jemandem nahe
Die XOR-Distanz ist symmetrisch, und ein Knoten ist auf jeder Bit-Ebene einem Kontakt nahe.
Die Routing-Tabellen bleiben winzig, während die Reichweite global ist, sodass kein Knoten alle kennt.
Jeder Hop halbiert die Distanz, was eine Suche in O(log n) ohne Verzeichnis ergibt.
Lookups und Einfügungen lehren die Knoten über Peers, sodass sich das Netzwerk selbst heilt.
In einem Netzwerk ohne Verzeichnis wähle eine Metrik und lasse jeden Knoten einen Kontakt pro Distanz-Bucket halten. Jeder Knoten kann dann jeden anderen über den nächstgelegenen bekannten Nachbarn erreichen, ohne eine globale Liste zu benötigen.
Kademlia wurde zum Lookup-Protokoll für BitTorrents DHT, Ethereum und viele Filesharing-Netzwerke. Es ist die Standardantwort auf Routing ohne Koordinator in einem großen Peer-to-Peer-System.
DEN BELEGEN FOLGEN
Die Quellen
- Kademlia: A peer-to-peer information system based on the XOR metric IPTPS 2002, Springer · pdos.csail.mit.edu
- Kademlia Wikipedia · en.wikipedia.org