* 表記
[image]: 必ずしも厳密では無く、直感的に理解しやすい説明に注釈しています。


* 概要
- CAN, Chord, Pastry, Tapestryの4つが起源(と言われています)
- ad hoc性とscalabilityの両立を目指す探索(lookup)手法です。
-- key => locationのmappingを行います (下記の用語参照)
-- locationはcontentを保有するノードのアドレス(e.g. IPアドレス+ポート)です。実装によっては、locationではなくcontent自体を持ちます。
- ノードとコンテンツを同一hash値の空間上で近い距離にマップするのが第一アイディアです => consistent hashing
- consistent hashingを利用し、かつ、各ノードが全体の知識を持たなくても(局所的知識のみ)、ノードが協調動作することで探索を成立させるのが、DHTと言えます。
- 現実的な観点では、以下のふたつが重要になります。
-- ノードの参加と離脱への耐性。
-- 下位トランスポートの距離(=ノード間のリンクの速度)の考慮。


一般的な用語の説明
- name: DHTはname => address解決のための探索技術のひとつです。nameは探索対象の名前。文脈によってはidやkeyと同義。idやkeyの方がより具象的。
- address: addressとlocationは文脈によっては同義。addressの方がより具象的(IPアドレスやURLなど)。
- (content)location: DHTの多くがcontentの位置の探索を主目的にしています
- lookup: content locationのための探索のこと。
- key: DHTの入力値。content locationの場合、name(content名)やcontent自体のハッシュ値などで決めます。
- value: DHTの出力値。content locationの場合、contentを持つノードのアドレス or content自体です。


誤解を招くので(ここでは)なるべく使わない用語
- keyの代わりにid or name: ユニーク性を想起させるので。
- lookupの代わりにsearch: 全文検索やkeyword検索を想起させるので。
- locationの代わりにaddress: IPアドレスを想起させるので。ただし現実的にはDHTのオーバーレイネットワークはIPネットワークの上に構築されるので、locationはIP addressになります。
- contentの代わりにresource or object or service: 多くの論文が探索対象をcontentにしているので。単なる嗜好の問題(個人的にはcontentよりresourceやserviceと呼ぶ方が好みです)。

(P2P論文で良くでる)English用語
- churn: ノードの参加と離脱。トポロジを構成するノードの安定度とも言えます。
- swamp: サーバやキャッシュが負荷のため利用不能になった状態。


ネットワーク探索技術の比較
|名称|例|問題点|
|index-server|多くのlocation/directoryサービス。Napster|単一障害点。負荷集中|
|hierarchical(tree)-directory|DNS。LDAP|不均一な負荷集中。名前空間の設計が必要|
|flooding|Gnutella。Freenet|トラフィック増大|


* DHT一般
- 次の3つの要素技術が重要です。
-- hash値の空間の「距離」の定義
-- ノードと探索対象を結び付ける技術(代表としてconsistent hashing)
-- 各ノードが全体に関する知識を持たない集合での、探索範囲の絞り方(=距離の縮め方)

- hash値の空間の「距離」の定義
-- ここでの「距離」は「長さ」の抽象化です。長さが備えるべき性質を「距離が満たすべき性質」に抽象化。もし「何か」が「距離が満たすべき性質」を満たせば、その「何か」は「距離」です。
-- 普通のDHTの場合、なんらかの図を示せば、「距離」は長さとして目に見えます。
-- [image] 目に見える空間上で、目に見える長さをイメージしながら読んでも、本質は外しません。以下、「近い」「遠い」の表現も、「距離」の定義で決まります。

- ノードと探索対象を結び付ける技術(代表としてconsistent hashing)
-- 探索対象(content)とノードの両方に、同じhash関数でhash値を割り当てます。
-- contentsとノードを結びつけたい、という問題です。この時、次の3つの性質を満たすようにしたいとします。現実的な前提として、contentの数の方がノードの数より圧倒的に多い状況を想定します。
--- ノードが増えたり減ったりしても、contentとノードの結び付きの変更は最小限にしたい。
--- contentが結びつくノードの数があまり多くないようにしたい
--- ノードごとに均等な数のcontentsが結び付くようにしたい。
-- これらを満たすために、hash値の空間上で、あるcontentは、ノードとcontentのhash値の「距離」が最小になるノードに割り当てます。
-- [image] 充分に広い空間上にノード群とcontents群を乱雑にばらまきます。それぞれのノードが近傍のcontentsの面倒を見ることをイメージしてください。
-- 以降、与えられた問題は、「contentsのkey(hash値)からvalue(location)を引く」ことですが、「空間上で、その contentと結びついたノード(ノードのhash値がcontentのhash値に近い)を探す」問題にすりかわります。

- 各ノードが全体に関する知識を持たない集合での、探索範囲の絞り方(=距離の縮め方)
-- ノードとcontentのhash値の空間の全体知識を(どこかに)持っていれば、探索はO(1)です。一般にこれはDHTとは呼びません(P2Pとも呼ばないでしょう)。

- 前提
-- 各ノードは全体知識を持たないとします。この前提で、各ノードが対称的に協調動作して探索を(効率的に)行います。
-- 必ずしも全てのDHTが探索要求を転送(forwarding)するわけでは無いですが、ここでは探索要求をノード間で転送すると仮定します。
--- 結局、やりたいことは、contentのkey(e.g. content名のhash値)からvalueを索く探索要求を、可能な限り速く狙ったノードに投げることです。consistent hashingの定義から、狙うノードは、そのhash値がcontentのkeyに近いノードです。
-- 各ノードが持つ他ノードに関する知識は限定された知識なので、「距離」が近いノードの知識は多く、「距離」が遠いノードの知識は少ないのが普通です。
--- [image] ノード群が乱雑にばらまかれた空間では、「距離」が遠いノードはそもそも総数が多いので、結果的に疎な知識しか持てません。

- 動作
-- 近い「距離」のノードに関しては密な知識を持っているので、近い「距離」への探索は、より精緻に良さそうなノードへ探索を投げられます。
-- 遠い「距離」のノードに関しては疎な知識しか持たないので、遠い「距離」への探索は、あまり精緻に良さそうなノードへ探索を投げることができません。しか し、受けたノードは、最初のノードよりは探索対象に近づいているので、次に探索を投げるノードは、少し精緻になります。
-- 探索を投げるごとに探索範囲は狭くなります。探索範囲が1/nずつ狭まっていけば、探索時間はO(log)になります。

- 技術的には、近い所は良く知っていて、遠い所も少し知っている状態を「どう作るかと、どう維持するか」がポイントです。



問題領域の観点
- 「全体に関する知識を持たない」状況下で、いかに効率的に探索を行うかが問題領域。

- この問題を解くためのソリューションとして、
-- 各ノードは対称的に動作
-- 各ノードは協調的に動作
というP2Pの性質が有効に動作します。

- 「全体に関する知識を持てない or 保守できない」、という問題領域にP2Pの適用を考慮すると良いでしょう。


-------------------------------------------------------
* 論文links

- http://en.wikipedia.org/wiki/Distributed_hash_table
- http://www.etse.urv.es/~cpairot/dhts.html
- http://www.infoanarchy.org/wiki/index.php/Distributed_Hash_Table
- http://iptps04.cs.ucsd.edu/
- http://www.ingrid.org/~sato/ref.html
- http://www.spa.is.uec.ac.jp/~kinuko/survey/
- http://www.msc.cs.gunma-u.ac.jp/~aya/RP.html
- http://dir.yahoo.com/computers_and_internet/internet/peer_to_peer_file_sharing/
- http://www.project-iris.net/irisbib/
-------------------------------------------------------


-------------------------------------------------------
* 各論

Chord [MIT]
- http://www.pdos.lcs.mit.edu/chord/papers/paper-ton.pdf
- http://www.pdos.lcs.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf (上より詳しい)
- http://www.pdos.lcs.mit.edu/chord/
- 距離の定義: ある意味、DHTの中で最も単純。単なる整数の距離(0と最後の数字がwrapした空間)。
- 論文で「service => locationのlookup」の概念を明示。
- 論文でTapestry、Pastry、CANに言及。Tapestryに対する利点はシンプルなことと、ノードの加入、離脱への強さ。Pastryとの 優劣比較は無い。CANは保持する状態はネットワークサイズNに依存しないが、lookupコストのN依存は大きい。
- m-bit(160bitのSHA1)。
- successor(次のノード)に順々に問い合わせても一応探索は完了(O(N))。
- fingerテーブルで探索をO(logN)化。2のk乗ずつ離れたノードへの経路表。
- successorノードのリストを持つ。リストの長さはlogNが良いらしい。key-valueのレプリカにも利用される(アプリ依存)。
- finger-tableは多少狂っても動くが、successor-listが狂うと探索が成立しなくなる。ノードの参加、離脱でsuccessor-listを更新する作業をstabilizationと呼ぶ。定期的に更新する。
- ノード参加:
-- successor、predecessorを探索。両ノードへ通知。
-- fingerテーブルを構築(隣接ノードのfingerテーブルをもらい、それを参照することで、パフォーマンスを上げる。例えば、finger[i]と finger[i+1]の間にノードが無いことが分かれば、finger[i+1]の探索が不要になる。このチューニングでfingerテーブルの新規構 築のコストはO(m*logN)からO(logN)になるらしい))
-- 他ノードのfingerテーブルの更新: for i=1 to mの(n-2^(i-1))のpredecessorノードを探索(そのノードをxとする)。ノードxに自ノードがfinger[i]の候補であることを 通知。ノードxは新ノードが既存finger[i]より小さければfinger[i]を更新。ノードxはpredecessorノードに新ノードのことを 通知。逆時計周りに通知が連鎖して、それぞれのノードがfinger[i]を更新する。通知の連鎖は、既存finger[i]の方が新ノードより小さい所 で停止)。色々チューニングすることでO(logN)になるらしい。
-- key-valueの移動(successorから移動)。
- ノード離脱(stabilize()で対応):
- stabilize(): successorノードにpredecessorを問い合わせる(返答ノードをxとする)。ノードxが自ノードとsuccessorノードの間のノード なら、未知の新しいノードが自ノードとsuccessorの間に現われたことを意味するので、successorノードをxにする。ノードxが自ノードよ り小さい場合、successorノードが自ノードを知らないことを意味するので、自ノードの存在を通知する。長いインターバルでfingerテーブルの 更新を行う。普通にfind_successor()を呼ぶだけ。
- 実装方法に、iterative(反復) or recursive(再帰)の2種類(DNSと似た区分け)。
-- iterativeはDNSサーバ風な応答モデル。queryの応答で次にqueryを出すべき応答を受ける。
-- recursiveはGnutella風なpropagation(forwarding)モデル。
- TCPで実装。iterativeモデル。APIも定義。
- 実験的には、lookupコストは(1/2)*logN
- http://nms.lcs.mit.edu/papers/podc2002.pdf

Coral
- http://www.project-iris.net/irisbib/papers/coral:iptps03/paper.pdf [Sloppy Hashing and self-organizing clusters]
- 現実路線(publicサービスのWebキャッシュとして稼働中)
- Chordベース
- DSHT: distributed sloppy hash table (論文の冒頭でDHTにダメ出し)
- Two principal goals: avoid hot spots and to find nearby data without querying distant nodes.

CFS(Cooperation File System)
- Chord location protocolを使った分散ファイルシステム(ファイルをブロック化して、DHTで探索)
- アドレス探索ではなく、ファイルブロック自体をhash tableが持つ
- based on SFS
- http://www.pdos.lcs.mit.edu/papers/cfs:sosp01/cfs_sosp.pdf


CAN (Content-Addresable Network) [UCB? AT&T?]
- http://www.ovmj.org/GNUnet/papers/can.pdf
- http://berkeley.intel-research.net/sylvia/ [sylviaは現在、intel]
- d次元座標空間(wrap)。d個のhash関数を用意して、座標空間上の点を決定。
- 距離の定義:
- 優位性: 知るべきノードの数が(order的には)ノード数に依存しない(dにのみ依存) => ノード追加時に影響のあるノード数も同様。
- ノードは定期的に隣接ノードの存在をチェック?
- content holderが定期的にkeyの存在を確認する必要がある?
- 論文でplaxtonアルゴリズム、OceanStoreに言及。consistent-hashingへの言及は無い。付録でplaxtonアルゴリズムはノードが頻繁に参加、離脱する状況で使えないと主張。
- 用語: zone: 知っている一部のノードのこと
- 用語: reality: 複数の独立した座標空間を用意することで、それぞれに複製を持つ改善ができる。それぞれの座標空間のこと。
- IPレベルのRTTをルーティング決定時に参照する改善案。
-- landmarkと呼ぶあるpredefinedなノード群を決めておき、それとのRTTをjoin前に計測して、joinする座標のヒントにする。
- 珍しく最初のノード発見(bootstrap)にも少し言及。DNSを利用。
- http://citeseer.nj.nec.com/ratnasamy01scalable.html


Pastry [MS]
- http://research.microsoft.com/~antr/Pastry/
- http://research.microsoft.com/~antr/PAST/pastry.pdf (オリジナル論文)
- 128bitのノードID
- アルゴリズムは任意の整数bを選択して、2^bを1-digitと扱い、n-digitのprefixが一致した経路表を持つ。b=1だと、事実上、 Chordと同じになる。推奨値はb=4。この場合、nodeidを16進数で表現して(1-digit)、n-digitのprefix一致を見る。以 下、b=4を想定。
- routing tableは、2^b(b=4で16)を底としたlogN(Nは全体のノードの最大数の行数)、2^b-1(b=4で15)の列数のテーブル。l行目は、 自ノードとl-digitのprefixが一致したノード(最大で2^b-1個)。lが小さい行(テーブルの上位)は、少ないノードで大きな空間をカバー している。つまり疎な探索を意味する。逆に少ないノードで大きな範囲をカバーしているので、routing tableは詰まっている可能性が高い。lが大きい行(テーブルの下位)は反対に密な探索を意味し、routing tableは空いている可能性が高い。
- leaf setは、nodeidが近いノードを保持しておく(一定数を保持)。Chordのsuccessor、predecessorのようなもの。
- neighborhood setは、IP的に近いノードを保持(論文ではIPでの近さとは言っていない。抽象的にproximity metricと呼んでいる。現実的には、IP的な近さ。以下、IP的な近さに話を限定)。
- routing tableの要素は、nodeid的に同じ条件のノードがある場合、よりIP的に近いノードを使う。ルーティングホップ(nodeidの空間の距離を縮め るホップ)のそれぞれでIP的に近いホップを使うからと言って、全体でIP的に近いパスを通るのか、という疑問がでる。nodeid空間の探索が密になっ ていく(DHT的に収束に近付く)と、各ホップのIP的な近さの期待値は上がっていくので、それぞれのホップでIP的に近いノードを選ぶのは意味がある、 と言っているみたい。でも、逆に、それぞれのホップでIP的に近いノードを選んでも全体にはあまり寄与しない、とも言えるような(?)。まあ、実験的に は、IP的に近いノードを選ぶことには意味がありそう。
- neighborhood setは、結局、routing tableにIP的に近いノードを選ぶ時に使われるだけ?
- ノードの参加。node-Xが参加する場合:
-- ブートストラップノードをnode-Aと呼ぶ(ブートストラップの取得方法はアプリ依存)。
-- node-Xはnode-Aに"key=node-X'id"のjoin-queryを投げる。Pastry上をA->B->C- >...->Zとルーティングしたとする。node-Xは、node-Bからnode-Zまでのノード群から、それぞれのルーティングテーブ ルを受け取る。node-Xとnode-Bのprefixがn-digit一致している場合、node-Bのn行目をnode-Xはルーティングテーブル のn行目に使う。逆に、node-Xは、node-Bからnode-Zに自ノードの存在を知らせる。それぞれのノードはルーティングテーブルにnode- Xを挿入する(しなくても良い)。
-- node-Xのleaf setは、node-Zのsetを使う。
-- node-Xのneighborhood setは、Aからもらう(ブートストラップはIP的に近いという前提)。
- ノードの離脱:
-- routing table内のl行目(l-digitのprefixが一致)のd要素(l+1-digitの値がd)のノードが死んでいる場合、l行目の他のノードに問 い合わせる(そのノードのl行目のd要素のノードが所望のノード)。見つからない場合、l+1行目のノードに問い合わせる。
-- leaf setとneighborhood setに関しては、それらのセットの中のノードに問い合わせる。定義上、自ノードに都合の良いleaf setは、leafノードのleaf setから選べば良いので。
- 隣接(nodeid的な隣接)kノードにレプリカを持つ(冗長化のため)。
- シミュレーションは、実装Java、True64 UNIX(MSなのに)、10万ノードで実施。
- 論文で、Tapestryに言及。基本的に似ているが、locality(IP的な近さ)の考慮の方法とレプリカに違いがあると主張。あまり本質では無いような気がする。
- IPレベルでPastryネットワークが分断する可能性がある。この場合、Pastryのレベルだけで復旧(分断したネットワークの発見)することはできない。論文ではIPマルチキャストでの復旧を提案している。


PAST
- Pastryを使ったファイル共有
- Contentそのものをhash tableがもつ(Coralの論文で言及)
- http://www.cs.rice.edu/~druschel/publications/PAST-hotos.pdf

SCRIBE
- Pastryを使ったpublish/subscribeシステム


Bamboo
- Pastryベースの実装(独自拡張有り)
- http://bamboo-dht.org/
- Java

OpenDHT
- Bambooの公開ノード(on http://www.planet-lab.org/)
- http://opendht.org/

FreePasty
- http://freepastry.rice.edu/FreePastry/
- Java


Plaxton(人の名前)
- Accessing Nearby Copies of Replicated Objects
http://cs.brown.edu/courses/cs296-2/papers/plaxton.ps
key-value探索。モデルのみ? ノードの離脱等は考慮していない(Tapestryは考慮)
neighbor maps: ***8 => **98 => *598 => 4598 (IPのCIDRのroutingに似ている?)

Tapestry [UCB]
- Plaxtonの論文をrefer(Plaxton tree lookup)
- location and routingの概念 (address from location-independent names)
- prefix/suffix address routing
- [*]論文に他システム(CAN、Chord、Pastry)との比較が載っている(と言うことは後発?)
- http://www.cs.berkeley.edu/~ravenben/tapestry/
- http://www.cs.berkeley.edu/~ravenben/publications/CSD-01-1141.pdf

OceanStore [UCB]
- Tapestryを利用した分散ストレージシステム
- Tapestry with attenuated Bloom filters
- Byzantine agreement protocol(信頼できないノードがいる分散システムで、合意を得るプロトコル)でconflictの解決
- Contentそのものをhash tableがもつ(Coralの論文で言及)
- http://oceanstore.cs.berkeley.edu/


P-grid
- prefix baseルーティング
- http://www.p-grid.org/


kademlia
- http://pompone.cs.ucsb.edu/~msa/reading/maymounkov_kademlia.pdf
- http://www.cs.rice.edu/Conferences/IPTPS02/109.pdf (binary-treeでの説明が欠けている)
- XORでノード間の「距離」を決める => binary-tree(2分木)で考えるのが分かりやすい。
- k-bucket: のリスト(「自ノードからの距離」が[ 2^i , 2^(i+1) )のノード)。リスト内のエントリの最大数は定数k(例 k=20)。
-- 2分木で考えると、距離1のノードは1個しかないのでk-bucketにあればそれで終わり。距離が大きくなると候補ノード数は幾何級数的に増加するがk 個しか保持しない。結局、遠いノードへの探索ほど疎な探索になる。=> 疎な部分へ探索が絞りこまれることで、探索範囲は1/nで減少 => O(log)
- 160bitの場合。最大で160個のk-buckets。
- request/replyのメッセージは、送信ノードのノードIDを含む。
- 他ノードからrequest or replyを受けると、そのノードをk-bucketにappendする。
-- k-bucketのノードは古い順に並べる(新しく見つけたノードは最後尾)。
-- k-bucketが一杯の場合、先頭(一番古いノード)の生存確認を行う。死んでいたらそのノードを外し、新しいノードを最後尾に追加する。生きていた ら、そのノードを最後尾に移動して、k-bucketへの新規追加はしない。=> ずっと生きているノードはいつまでもk-bucketから外れない(Gnutellaの観測から、長く生存するノードは今後も生存する確率が高いので)。 DoS攻撃への耐性が強い(k-bucketを新しいノードで簡単にflushできない)。
- lookupはiterate(Chord参照)に行う。並行、非同期にlookupを行う。
- STORE対象のノードは、k-bucket内のノードから始めて探索範囲を絞りこみ、最終的にk個のノードに絞る(このkは開始時のkとは関係無い)。絞った(収束した)k個のノードにkey-valueをSTOREする。
- ノード参加の動作: 自分のノードIDのlookup(FIND_NODE)。FIND_NODEのreplyはk個のノードリスト。収束するまでFIND_NODEを繰り返 す。=> これでk-bucketsが埋まる(同時に、相手ノードに存在を知らせる機能も兼ねる)。
- ノードの参加、離脱への対応のために、1時間ごとにkey-valueをre-publish。
- アプリ依存の動作: コンテンツホルダーは、24時間ごとにre-publish(24時間でre-publishされないkeyは消える)。
- ノードが参加した場合、既存ノードで、新ノードに最も近いと判断したノードはkey-valueペアをSTOREする。
- (実装の工夫)lookupが成功すると、valueを返さなかったがIDが近いノードにstoreする。
- UDPでの実装が前提(に見える)。
- 論文で少しpastry、tapestryに似ていると言及。


GNUnet
- http://www.ovmj.org/GNUnet/
- kademliaベース

eDonkey (successor of Overnet)
- kademliaベース
- http://www.edonkey2000.com/
- eMuleは分岐


Dipsea
- 2004/Aug 色々な組み合わせ? (Dipsea is a modular architecture for Distributed Hash Tables.)
- http://www-db.stanford.edu/~manku/phd/index.html

Project-IRIS
- NSFからfunded
- http://www.project-iris.net/index.html

JXTA SRDI(Shared Resource Distributed Index)
- http://www-6.ibm.com/jp/developerworks/java/040514/j_j-jxta2.html
- http://www-6.ibm.com/jp/developerworks/java/040514/side-jxta2.html
- http://platform.jxta.org/java/workinprogress/srdi.html
- http://www.jxta.org/project/www/docs/jxta-dht.pdf

GISP
- JXTA base DHT
- obsoleted by SRDI?
- http://gisp.jxta.org/
- cf. http://di.jxta.org/


articles
- Chord/CAN/Pastry[図入り説明]: http://www.project-iris.net/irisbib/papers/dht:cacm03/paper.pdf
- Decentralized Meta-Data Strategies(1G/2G/3G) http://www.neurogrid.net/Decentralized_Meta-Data_Strategies-neat.html


* DHT前夜

consistent hashing
- http://cs.brown.edu/courses/cs296-2/papers/consistent.pdf
-- consistent hashingとrandom treeで、Webキャッシュを効率化する論文
-- consistent hashingの数学的根拠を示している。
-- Plaxton treeをrefer (ページ毎に異なるツリー。単一のツリーだとrootに負荷が集中するため)
--- buckets(DHT的にはノードと思えばよい)用のhash-function: rb(b)
--- item(DHT的にはkeyと思えばよい)用のhash-function: ri(i)
--- |rb(b) - ri(i)|が最小、となるbを選択 => 距離の定義次第。自然数の距離だとすると、Chordのような円をイメージして、ri(i)に近いrb(b)を選択。
--- k * log(C)のbucketの複製が必要(kは定数。Cは全キャッシュの空間(DHT的にはhash値の最大bit数と思えばよい?)


Web Caching with Consistent Hashing
- http://www8.org/w8-papers/2a-webserver/caching/paper2.html
- directory-based location schemeとbroadcast-based location schemeを明確に比較対象として挙げている。
- Chordに近いが、hashのlookupはdirectoryベース(DNS)。


DDH(Distributed Dynamic Hashing)
- http://db.cs.berkeley.edu/papers/S2K-94-50.pdf
- 分散DBの系列(recordからkeyを生成して、バケツ(サーバ)にばらまく)
- binary radix treeベース。(level,bucket-number)
-- (0,0)から始めて、levelを増やしてbucketを分割していく。
-- レコードのkey値に対し、level=Nの時、下位N bitsがbucket-numberになる。
-- e.g. レコードのkey値が010....1011の時、level=1の時、BN=1。level=2or3の時、BN=3(=11)。level=4の時、BN=11(=1011)
- bucket-numberからサーバへのmapping(location)はあまり考慮されていない雰囲気。
- DHTとの相違: 各サーバ(node)は全体の知識(どのサーバがどのキーをカバーしているか)を有する。


* 日本語の情報
- Kademlia http://www.shudo.net/article/Kademlia-20040727/
- Chord/CAN http://homepage3.nifty.com/toremoro/p2p/p2p.html
- Chord/Tapestry http://www.wide.ad.jp/project/document/reports/pdf2002/part17.htm
- Chort/Consistent hashing http://www.mlab.t.u-tokyo.ac.jp/~oka/pdf/d1-rinkou2.pdf
- 今後に期待 http://www.mlab.t.u-tokyo.ac.jp/~oka/index.html
- Tapestry http://www.mlab.t.u-tokyo.ac.jp/publications/2002/nakauchi-in02_2.pdf
- Pastry/リンク http://mars.elcom.nitech.ac.jp/~habayuu/dh/
- 雑誌記事(Chord/Kademlia) http://dev.ariel-networks.com/modules/xfsection/article.php?articleid=29


* 未整理:
RevConnect - http://www.revconnect.com/
Koorde
The Circle
NEOnet | neonetwork.com
Brocade
Viceroy
DDS http://www.usenix.org/events/osdi2000/full_papers/gribble/gribble_html/node4.html

Handling Churn in a DHT
http://www.usenix.org/events/usenix04/tech/general/rhea/rhea_html/index.html