eMule Fans 電騾愛好者

美國紐約大學的Petar Maymounkov和David Mazières在2002年發表了一篇論文《Kademlia: A peer to peer information system based on the XOR metric》

Kademlia 是個 Petar Maymounkov 與 David Mazières 所設計的點對點（P2P）重疊網路，以達成非集中式的點對點（P2P）電腦網路。它規制了網路的結構及規範了節點間的通訊和交換信息的方式。Kademlia 節點間使用傳輸通訊協定UDP（請見OSI模型）溝通。Kademlia 節點藉以實作分散式雜湊表 (DHT,distributed hash table) 以儲存資料。透過既有的區域網／廣域網（LAN／WAN）（如同Internet），一個新的虛擬網路或是重疊網路被建立起來。每個網路節點都是以一組數字（「節點 ID」）來識別。這組數字不但做為識別之用，Kademlia 演演算法還會用來做其他用途。

一個想要加入網路的節點需要先通過啟動。在這個階段，這個節點需要知道另一個已經在 Kademlia 網路內的節點之 IP 位址（透過另一個使用者或儲存的列表取得）。如果啟動中的節點還不是網路的一部分，它便會計算一個尚未指定給其他節點的隨機 ID 編號。這個 ID 會一直使用到離開網路為止。

Kademlia 演演算法是基於兩節點間的「距離」來計算。這個距離是以兩節點的 ID 進行異或運算，並將結果四捨五入至整數。

這個「距離」跟實際的地理環境無關，而是標明 ID 範圍內的距離。因此一個德國的節點和一個澳洲的節點就有可能被稱為「鄰居」或「芳鄰」。

Kademlia 內的信息都儲存在稱為「數值」的東西內，每個數值都連接著一個「金鑰」。

當搜索某個金鑰時，演演算法會透過幾個步驟探整個網路一圈，每個步驟都會更接近要搜索的金鑰，直到被連線的節點傳回數值，或找不到更近的節點。網路的大小僅會稍微影響到進行搜索時接觸到的節點數目：假如目前網路的使用者突然增為兩倍，那使用者節點大概只需要在搜索時多查詢一個節點，而不是兩倍的節點量。

非集中式的結構提供了更大的優勢，並很明顯地增加了對拒絕服務阻斷攻擊的抵抗。即使一整系列的節點被壅塞，也不會對網路可用度造成太多影響，最後網路會透過繞過這些「洞」而自我修復。

Kademlia 被用來進行文件分享。透過進行 Kademlia 關鍵字搜索，任何人可以在文件分享網路中尋找資料以下載東西。由於沒有任何中央伺服器儲存文件列表的索引，因此這項工作是平均的由所有的客戶端擔當：擁有要分享的文件枝節點，會先處理文件的內容，並從內容計算出一組數字（雜湊），這組數字將會在文件分享網路中辨識這個文件。雜湊與節點 ID 的長度必須相同。接著會搜索幾個 ID 與雜湊相近、且節點內有儲存著自己 IP 位址的節點。搜索的客戶端會使用 Kademlia 來搜索網路上節點ID離自己最近距離的節點來取得文件雜湊，然後會取得在該節點上的聯絡列表。 當節點聯入和聯出時，這份存儲在網路上的聯絡列表也將保持不變。因為內嵌的冗餘存儲演算法，聯繫列表將複製在多個點上。

文件雜湊通常都是由其它地方的特製Internet鍵結來取得，或者被包含在來自其它來源中的索引檔中。

對文件名稱的搜索是基於關鍵字來實現的。文件名稱被分成幾個組成文件名稱的單字。 每個關鍵字都會被雜湊，並和相對的文件名稱與文件雜湊利用和文件雜湊一樣的方式儲存到網路上。一個搜索者會選擇其中的一個關鍵字，聯繫上和關鍵字雜湊最相近的節點ID，然後取得含有關鍵字的文件名稱列。既然在文件名稱列中的每個文件名稱都附有自己的湊雜，那麼被選的文件就可以由一般的方式取得。

資料下載

Petar Maymounkov and David Mazières. Kademlia: A peer-to-peer information system based on the XOR metric. In Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS ’02), pages 53-65, March 2002. paper.：

論文：
Kademlia: A peer-to-peer information system

演示用幻燈片：
Kademlia: A peer-to-peer information system (Demo)

《Kademlia協議原理簡介》 – 論文的中文翻譯（by：MMX）：
Kademlia協議原理簡介

作者資料

David Mazières：

David Mazières

Petar Maymounkov：

Petar Maymounkov

其他

目前公開使用 Kademlia 演算法的網路，函數庫與客戶端程序（彼此並不兼容）：

• Overnet network:
  Overnet (integrated in eDonkey (no longer available) and MLDonkey). With KadC a C library for handling its Kademlia is available.
• Kad Network:
  eMule v0.40+, MLDonkey v2.5-28+. Lphant v.3.50 beta 2+ and aMule v2.1.0+.
• RevConnect:
  – v0.403+.
• BitTorrent Mainline DHT:
  BitTorrent v4.1.0+, µTorrent v1.2+, BitSpirit v3.0+, BitComet v0.59+, KTorrent, Azureus 3.0+ (via a Plugin), Transmission 1.70+ , BitFlu.pl, and many libtorrent-based: They all share a DHT based on an implementation of the Kademlia algorithm, for trackerless torrents.
• Azureus DHT v2.3.0.0+:
  used for decentralized BitTorrent tracking and various other features; differing from the BitTorrent Mainline DHT.
• Osiris sps (all version):
  used to manage distributed and anonymous web portal
• Mojito
  – a Java Kademlia library written for the LimeWire project. Mojito is used in LimeWire to provide DHT support for BitTorrent as well as to augment the Gnutella protocol. See the Class interface documentation for more information.
• maidsafe-dht
  – c++ implementation of Kademlia (BSD license), with NAT traversal and crypto libraries.
• Khashmir
  – Python implementation of Kademlia. Used in the mainline Bittorrent, with some modifications.
• Plan-x
  – Java implementation.
• SharkyPy
  – another python implementation of a Kademlia Distributed Hash Table. LGPL licenced.
• Entangled
  – Python implementation of Kademlia, also providing a distributed tuple space. LGPL licenced
• RetroShare
  – Kademlia implementation for secure Peer-to-Peer messaging and File Sharing