[P2P]スモールワールドを応用したDHT：Symphony

P2P勉強会でDHT（分散ハッシュテーブル）について講演した際、DHTにスモールワールドを応用したら面白そう、と言ったら既にそういう論文があるということを教わった。その代表例がSymphony。

スモールワールドといえば、全世界のランダムに選んだ人間同士が6人の知り合いを介すれば実は繋がっているということを説明した事で有名で、現在とても盛んに研究されている分野だ。経済物理学や社会学にも応用されているとのこと。

Symphony：Distributed Hashing In A Small World(2003) Gurmeet Singh Manku,Mayank Bawa,Prabhakar Raghavan

論文
プレゼン資料

特徴：
・ハッシュ空間は1次元。Chordのようにリング型。
・隣接ノードについてはリンクが必要。他のリンクについてはランダムに決める。
ただし、その確率分布は基本的に自分のノードからの距離（ハッシュ的な）に反比例。つまり、距離が近いほどリンク先（元）になる確率は高くなる。
・ルーティングはリンクされているノードのうち、そのハッシュについて（時計回りで）近い方へルーティング。
・ホップ数はリンク数を2k+2とすると、O（[log(N)]²/k)　残念ながらChordよりは効率悪そう。
・リンク数が少なくてよい。ChordなどはO(log(N))だが、リンクが数10あれば充分のようだ。
・ルーティングテーブルが少ないのと、仕組みが簡単なので実装は他のDHTよりも容易そう。誰か実装やってみない？またノードの負担も少ないだろう。。

とても面白い論文なので是非チェックしてね！
※明日はMixiのオフ会でこの話題を講演する予定です。
http://mixi.jp/view_event.pl?id=545107