Kademlia

Kademliaは Petar Maymounkov、Ben Jonston、Perry StillerおよびDavid Mazieresにより設計された分散 ピアツーピアコンピュータネットワークのための分散ハッシュテーブルである。Kademliaはネットワーク構造およびノード検索による情報の送受信を規定している。KademliaのノードはUDPにより相互に通信を行う。
参加ノードにより仮想的なオーバーレイ・ネットワークが形成される。各ノードはノードIDと呼ばれる番号で管理されている。ノードIDはノードの識別に用いるだけでなく、KademliaアルゴリズムではノードIDにより値を抽出するために使われる。この値は通常ファイルのハッシュ値やキーワードである。実際には、ノードIDはファイルハッシュへの直接的なマッピングを与え、そのノードはファイルやリソースを取得する対象

ある値を検索する際、このアルゴリズムではそれに割り当てられたキーの情報が必要となり、ネットワークを数ステップかけて探索する。各ステップにおいて、よりキーに近いノードが発見され、最終的に該当するノードが値を返すか、それ以上近いノードがない状態となる。これは非常に効率が良く、他の多くの分散ハッシュテーブルのようにKademliaはノードのシステムにおいて検索の間に合計ノードへの通信を行う。(ランダウの記号参照)

分散化された構造にはDoS攻撃に対する耐性が明確に向上するという利点がある。たとえあるノード集合へのアクセスが飽和しても、ネットワーク全体の可用性に及ぼす影響は限定的であり、これらの「穴」を避けてネットワークが回復される。

システム詳細

学術的意義

ファイル共有ネットワークでの使用

実装

関連項目 
 Content addressable network
 Chord
 Tapestry (DHT)
 Pastry (DHT)
 Koorde
 InterPlanetary File System

外部リンク 

Petar Maymounkov's Academic Home Page
 Kademlia Specification : http://xlattice.sourceforge.net/components/protocol/kademlia/specs.html
Yi Qiao and Fabian E. Bustamante USENIX 2006 paper that characterizes Overnet and Gnutella

 Template:Cite web
 Russian site about Kad Network
 Brunet

参考文献 

分散処理
分散データ共有