分散ハッシュCAN(Content-Addressable Network)

P2P

N個のhash関数を用意してN次元トーラスとして管理するハッシュ値を配分
各ノードは隣接ノードへのルーティングテーブルを持つ
ルーティングテーブルから検索すべきハッシュ値に対応する最適なノードを選択することで対象のデータを検索する。
処理時間はノード数N,次元数dに対しO(N^1/d)とのこと。

分散ハッシュChord

P2P

なんて読むんだろう。。コード？

ハッシュ2^m空間を円状に並べ、ノードを対応させる。
各ノードは1つ手前のノードまでのハッシュ値を管理する。
ここであるハッシュ値xを管理するノード番号を返すNext関数を定義する。
もしルーティングテーブルが隣接するノードのみを保持するとすれば処理時間はO(N)となる。
そこでChordの場合、2^i,i=0,1,・・・,m-1ごとにルーティング情報を保持する。
正確にはノードのIDをnとすればNext(n+2^i mod 2^m)をルーティングする。
この場合の処理時間はO(log N)となる

だいたいSHA-1でm=160位を想定するらしい