この項目では、アルゴリズムについて説明しています。その他の用法については「コード」をご覧ください。

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

Chordでは、コンテンツのハッシュ値を求める関数にSHA-1を採用するのが一般的である。ネットワークに参加するノードは、SHA-1のハッシュ値の値域 0 ≤ N o d e I D ≤ 2 160 − 1 {\displaystyle 0\leq NodeID\leq 2^{160}-1} を満たす一意な N o d e I D {\displaystyle NodeID} が割り当てられる。

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

ネットワークで情報を共有する際には、共有したい情報のハッシュ値を x {\displaystyle x} として N o d e I D = n e x t ( x ) {\displaystyle NodeID=next(x)} を満たす N o d e I D {\displaystyle NodeID} を持つノードが、実際に情報を保持しているノードの位置を示すIPアドレス等の情報を保持する。

また、ネットワークに参加するノードは、自身の N o d e I D {\displaystyle NodeID} を M y N o d e I D {\displaystyle MyNodeID} とした場合、

n e x t ( Z ) {\displaystyle next(Z)} ,ただし Z = M y N o d e I D + 2 i m o d 2 160 ( 0 ≤ i < 160 ) {\displaystyle Z=MyNodeID+2^{i}mod2^{160}(0\leq i<160)}

の N o d e I D {\displaystyle NodeID} をもつノードのIPアドレスをルーティングテーブルとして保持する。

共有されている情報を検索する際には、検索したい情報のハッシュ値を y {\displaystyle y} としたとき、 N o d e I D {\displaystyle NodeID} として n e x t ( y ) {\displaystyle next(y)} が割り当てられているノードを各ノードのルーティングテーブルを利用して検索することになる。
参考文献

Ion Stoica; Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan (2001). “Chord: A scalable peer-to-peer lookup service for internet applications”. ACM SIGCOMM Computer Communication Review (New York, NY, USA: ACM Press) 31 (4): 149 - 160. doi:10.1145/964723.383071. 

外部リンク

⇒Chord project Chord を使ってP2Pネットワークを構築するプロジェクト

.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox{font-size:90%}.mw-parser-output .asbox-note{font-size:90%}.mw-parser-output .asbox .navbar{position:absolute;top:-0.90em;right:1em;display:none}

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。
.mw-parser-output .hlist ul,.mw-parser-output .hlist ol{padding-left:0}.mw-parser-output .hlist li,.mw-parser-output .hlist dd,.mw-parser-output .hlist dt{margin-right:0;display:inline-block;white-space:nowrap}.mw-parser-output .hlist dt:after,.mw-parser-output .hlist dd:after,.mw-parser-output .hlist li:after{white-space:normal}.mw-parser-output .hlist li:after,.mw-parser-output .hlist dd:after{content:" ・\a0 ";font-weight:bold}.mw-parser-output .hlist dt:after{content:": "}.mw-parser-output .hlist-pipe dd:after,.mw-parser-output .hlist-pipe li:after{content:" |\a0 ";font-weight:normal}.mw-parser-output .hlist-hyphen dd:after,.mw-parser-output .hlist-hyphen li:after{content:" -\a0 ";font-weight:normal}.mw-parser-output .hlist-comma dd:after,.mw-parser-output .hlist-comma li:after{content:"、";font-weight:normal}.mw-parser-output .hlist-slash dd:after,.mw-parser-output .hlist-slash li:after{content:" /\a0 ";font-weight:normal}.mw-parser-output .hlist dd:last-child:after,.mw-parser-output .hlist dt:last-child:after,.mw-parser-output .hlist li:last-child:after{content:none}.mw-parser-output .hlist dd dd:first-child:before,.mw-parser-output .hlist dd dt:first-child:before,.mw-parser-output .hlist dd li:first-child:before,.mw-parser-output .hlist dt dd:first-child:before,.mw-parser-output .hlist dt dt:first-child:before,.mw-parser-output .hlist dt li:first-child:before,.mw-parser-output .hlist li dd:first-child:before,.mw-parser-output .hlist li dt:first-child:before,.mw-parser-output .hlist li li:first-child:before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child:after,.mw-parser-output .hlist dd dt:last-child:after,.mw-parser-output .hlist dd li:last-child:after,.mw-parser-output .hlist dt dd:last-child:after,.mw-parser-output .hlist dt dt:last-child:after,.mw-parser-output .hlist dt li:last-child:after,.mw-parser-output .hlist li dd:last-child:after,.mw-parser-output .hlist li dt:last-child:after,.mw-parser-output .hlist li li:last-child:after{content:")\a0 ";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li:before{content:" "counter(listitem)" ";white-space:nowrap}.mw-parser-output .hlist dd ol>li:first-child:before,.mw-parser-output .hlist dt ol>li:first-child:before,.mw-parser-output .hlist li ol>li:first-child:before{content:" ("counter(listitem)" "}.mw-parser-output .navbar{display:inline;font-size:75%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}.mw-parser-output .infobox .navbar{font-size:88%}.mw-parser-output .navbox .navbar{display:block;font-size:88%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}

表示

編集