Chordのソースを表示

{{otheruses|アルゴリズム|その他|コード}}
'''Chord'''は、[[分散ハッシュテーブル]]を実現する[[アルゴリズム]]の一つ。[[ピア・ツー・ピア|P2P]][[コンピュータネットワーク|ネットワーク]]において、[[サーバ]]を用いることなく高速にコンテンツの検索、[[ルーティング]]を行う手法。

== アルゴリズム ==
Chordでは、コンテンツの[[ハッシュ関数|ハッシュ値を求める関数]]に[[SHA-1]]を採用するのが一般的である。ネットワークに参加するノードは、SHA-1のハッシュ値の[[値域]]<math>0 \le NodeID \le 2^{160}-1</math>を満たす一意な<math>NodeID</math>が割り当てられる。

ここで、<math>next(x)</math>という関数を定義する。この関数は、ハッシュ値<math>x</math>が与えられたとき、値を増加させる方向で次に存在しているノードの<math>NodeID</math>を返す。なお、<math>2^{160}-1</math>と<math>0</math>は接続されていると考える。

ネットワークで情報を共有する際には、共有したい情報のハッシュ値を<math>x</math>として<math>NodeID = next(x)</math>を満たす<math>NodeID</math>を持つノードが、実際に情報を保持しているノードの位置を示す[[IPアドレス]]等の情報を保持する。

また、ネットワークに参加するノードは、自身の<math>NodeID</math>を<math>MyNodeID</math>とした場合、

<math>next(Z)</math>,
ただし<math>Z=MyNodeID+2^{i}mod2^{160}(0 \le i < 160)</math>

の<math>NodeID</math>をもつノードのIPアドレスをルーティングテーブルとして保持する。

共有されている情報を検索する際には、検索したい情報のハッシュ値を<math>y</math>としたとき、<math>NodeID</math>として<math>next(y)</math>が割り当てられているノードを各ノードのルーティングテーブルを利用して検索することになる。

== 参考文献 ==
*{{Cite journal
|author=Ion Stoica
|coauthors=Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan
|title=Chord: A scalable peer-to-peer lookup service for internet applications
|journal=ACM SIGCOMM Computer Communication Review
|volume=31
|issue=4
|pages=149 - 160
|year=2001
|publisher=ACM Press
|location=New York, NY, USA
|doi=10.1145/964723.383071
}}

== 外部リンク ==
* [http://pdos.csail.mit.edu/chord/ Chord project] Chord を使ってP2Pネットワークを構築するプロジェクト

{{DEFAULTSORT:Chord}}
{{Computer-stub}}

[[Category:P2P]]
[[Category:アルゴリズム]]
[[Category:分散処理]]
[[Category:分散データ共有]]