有关Kademlia理论的学术论文与作者介绍

美国纽约大学的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 ^[1]

演示用幻灯片：
Kademlia: A peer-to-peer information system (Demo) ^[2]

《Kademlia协议原理简介》 – 论文的中文翻译（by：MMX）：
Kademlia协议原理简介 ^[3]

作者资料

David Mazières：

http://www.scs.stanford.edu/~dm/ ^[4]

Petar Maymounkov：

http://pdos.csail.mit.edu/~petar/ ^[5]

其他

目前公开使用 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