Chordアルゴリズムの解説ページです。
掲載コンテンツへのリンク先を変更する可能性があるので、ブックマークやリンクは、このページにお願いします。
Chordとは
Chordは、DHT（Distributed Hash Table）と呼ばれる種類のPeer-to-Peerアルゴリズムです。
特に、構造化オーバレイ（Structured Overlay Network）と呼ばれるルーティング手法に特徴があります。
解説スライドでは、そもそもDHTとは何なのかという初歩的なことから、successorやpredecessor、finger tableと呼ばれるChordの有名な経路表の解説や、多くの解説ではあまり触れられることがないけれどもきわめて重要である、ネットワークの構築方法（join・stabilize）についても詳細に解説しています。
スライドのページ数は多いですが、１ページ当たり平均数秒で読めるはずなので、思うほど時間はかからないと思います。
特に、ちょっとP2Pアルゴリズムに興味を持った人や、これからP2PやDHT・構造化オーバレイを扱う研究を始めようとしている研究室所属したての学生におすすめです。それと、ついつい「論文読んで」と言って済ませてしまう上級生の方、どうぞ後輩指導にご活用ください。
Chord解説スライド (Original, Japanese)
目次：
00. Chordとは ...p.5
01. 基礎：そもそもDHTとは ...p.7
02. Chordの基礎 ...p.28
03. Chordの経路表（1.SuccessorOnly） ...p.51
04. Chordの経路表（2.Successor+FingerTable） ...p.89
05. Chordの経路表（3.SuccessorList+FingerTable） ...p.131
06. Predecessor ...p.179
07. Join操作 ...p.188
08. Stabilize操作 ...p.209
09. まとめ ...p.307
10. Virtual Node ...p.316
Explanation about Chord (English)
Contents:
00. About Chord ...p.5
01. What's DHT ...p.7
02. The Basics of Chord ...p.28
03. Chord's Routing Table (1.Successor-only) ...p.51
04. Chord's Routing Table (2.Successor+FingerTable) ...p.89
05. Chord's Routing Table (3.SuccessorList+FingerTable) ...p.130
06. Predecessor ...p.179
07. Join Operation ...p.188
08. Stabilize Operation ...p.209
09. Conclusion ...p.305
10. Virtual Node ...p.314
参考資料
Chordの論文
SIGCOMM論文
最も有名な論文です。解説スライドで気になったところは、この論文でチェックしてみてください。
Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan, "Chord: A scalable peer-to-peer lookup service for Internet applications". in Proc. ACM SIGCOMM 2001.
ジャーナル版
IEEE/ACM Transactions on Networkingに掲載された論文です。
Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, Hari Balakrishnan, "Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications". in IEEE/ACM Transactions on Networking.
MIT Tech Report版
最も詳細です。リンク先、一番下のリンクから、.psファイルです。
Ion Stoica, Robert Morris, David Liben-Nowell, David Karger, M. Frans Kaashoek, Frank Dabek and Hari Balakrishnan,
"Chord: A scalable peer-to-peer lookup service for Internet applications".
Tech. Report TR-819, MIT LCS, 2001.