情報科学屋さんを目指す人のメモ

方法・手順・解説を書き残すブログ。私と同じことを繰り返さずに済むように。

ChordアルゴリズムによるDHT入門

最終更新日:2014年1月11日(土) 01:30 | コメント(0) | 5578 views |

Chordアルゴリズムの解説ページです。

掲載コンテンツへのリンク先を変更する可能性があるので、ブックマークやリンクは、このページにお願いします。

Chordとは

Chordは、DHT(Distributed Hash Table)と呼ばれる種類のPeer-to-Peerアルゴリズムです。

特に、構造化オーバレイ(Structured Overlay Network)と呼ばれるルーティング手法に特徴があります。

解説スライドでは、そもそもDHTとは何なのかという初歩的なことから、successorやpredecessor、finger tableと呼ばれるChordの有名な経路表の解説や、多くの解説ではあまり触れられることがないけれどもきわめて重要である、ネットワークの構築方法(join・stabilize)についても詳細に解説しています

スライドのページ数は多いですが、1ページ当たり平均数秒で読めるはずなので、思うほど時間はかからないと思います。

特に、ちょっとP2Pアルゴリズムに興味を持った人や、これからP2PやDHT・構造化オーバレイを扱う研究を始めようとしている研究室所属したての学生におすすめです。それと、ついつい「論文読んで」と言って済ませてしまう上級生の方、どうぞ後輩指導にご活用ください。

Chord解説スライド (Original, Japanese)

Explanation about Chord (English)

Introduction to DHT with Chord

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.

Chordの公式ページ

関連解説

解説の更新履歴

  • 2011年02月19日:旧ブログにて公開。
  • 2012年06月11日:本ページを公開。英語版完成。従来の日本語版を加筆・修正(特にjoin・stabilizeの解説部分)。
カテゴリ: / タグ:
公開日:2012年6月11日
最終更新日:2014年1月11日
  • 著者紹介

    ブログが趣味で、 月間1,000万PV を達成しました。

    自分が困ったことをブログに書けば、次に困る人の参考になって、みんながみんな同じ苦労をせずに済む、というのが原点です。

    最近の関心は、スマホやパソコンに詳しくない人の行動や思考、 そしてそんな人を手助けする方法や枠組み。 また、それに関連するような、"身近な"セキュリティ。

    ※SNS(特にTwitter)でシェアされた記事は、内容の追加・更新を行っています。 必ず、ではありませんが、気に入った記事は積極的にシェアしてみてください。

    RSS | Facebook | Twitter | About

  • 経過日数

    開設 1949 日経過

  • 総エントリ数

     3,810  エントリ