Chord

Chordは、分散ハッシュテーブルを実現するアルゴリズムの一つ。P2Pネットワークにおいて、サーバを用いることなく高速にコンテンツの検索、ルーティングを行う手法。
アルゴリズム.
Chordでは、コンテンツのハッシュ値を求める関数にSHA-1を採用するのが一般的である。ネットワークに参加するノードは、SHA-1のハッシュ値の値域formula_1を満たす一意なformula_2が割り当てられる。
ここで、formula_3という関数を定義する。この関数は、ハッシュ値formula_4が与えられたとき、値を増加させる方向で次に存在しているノードのformula_2を返す。なお、formula_6とformula_7は接続されていると考える。
ネットワークで情報を共有する際には、共有したい情報のハッシュ値をformula_4としてformula_9を満たすformula_2を持つノードが、実際に情報を保持しているノードの位置を示すIPアドレス等の情報を保持する。
また、ネットワークに参加するノードは、自身のformula_2をformula_12とした場合、
formula_13,
ただしformula_14
のformula_2をもつノードのIPアドレスをルーティングテーブルとして保持する。
共有されている情報を検索する際には、検索したい情報のハッシュ値をformula_16としたとき、formula_2としてformula_18が割り当てられているノードを各ノードのルーティングテーブルを利用して検索することになる。