« 分散ハッシュ(DHT)入門~その6 | トップページ | [Blog]10万ビュー突破! »

2005.02.06

[ネットワーキング]分散ハッシュ(DHT)と6次の繋がり

「新ネットワーク思考」という本をご存知だろうか?この本の中に「6次の繋がり」という事が書いてある。
それは、

・ある人とランダムに選んだ世界中にいるある人とは6次で結ばれている

ということである。
例えば、AさんがBさんを知っている場合には1次の繋がり、AさんがBさんを介してCさんを知りうる状況では2次の繋がり、6次となると、A⇒B⇒C⇒D⇒E⇒F⇒Gという繋がりでAがGが知りうる状態を意味する。

なんだか信じられない話だが実際そうらしい。

今回話したい事は、この6次の繋がりをどう説明するか?ということである。
「べき乗の法則」というものがこの6次の繋がりを上手く説明できるそうだ。一般にはほとんどの人が他人と知りうる人はそれなりの数なのだが、少数ながら非常にたくさんの数と知りうる人がいる。それによって、このような6次の繋がりが説明できる、とのこと。(詳しくはあまり知らないのでご容赦を。)
参考:スケールフリー性

ここで分散ハッシュ(DHT)との絡みに持って行きたい。
分散ハッシュでは、あるノードAが他のノードBと連絡できるステップ数は参加者数をNとするとO(log(N))である。
log(N)というは効率的であるが、N=50億人となると、とても平均ステップ数6で知りうる事は大変だろう。
たとえば、logの基底を10としても10^6=1,000,000である。とても50億には届かない。

すると、ここで一つ考え付く事がある。つまり、普通の分散ハッシュでは各ノードについてのルーティングテーブルの大きさがほぼ一定である。これを例えばノードの処理時間や接続時間によってルーティングテーブルの大きさを増減させると、実は検索ステップ数が少なくなるのでは?ということだ。

おそらく人間同士のコミュニケーションでは、知り合いが多い人がハブとなり、それらが絡み合う事により少ないステップ数で人間同士が結ばれるのだ。その原理をオーバーレイネットワークにも持ち込もうということになる。

こうなるとDHTのルーティングの仕方自体もかなり大幅な修正が加えられるはずだが、非常に面白い結果になるかもしれない。

ジャスト・イン・アイデアだが、取り合えずメモ。


|

« 分散ハッシュ(DHT)入門~その6 | トップページ | [Blog]10万ビュー突破! »

パソコン・インターネット」カテゴリの記事

コメント

「つながり」の定義にもよりますが,よく調べられたエルデシュ数を例に取ると,エルデシュと同世代を生きたシュレーディンガーのエルデシュ数は8だそうなので,もう少し大きな数が必要かもです.
http://www.oakland.edu/enp/erdpaths.html

あと,最小全域木の直径を小さくする方法についてですが,グラフ理論の本を探してみると何か良い結果が載っているかもしれません.

投稿: Canadian | 2005.02.08 02:04

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/18781/2823082

この記事へのトラックバック一覧です: [ネットワーキング]分散ハッシュ(DHT)と6次の繋がり:

« 分散ハッシュ(DHT)入門~その6 | トップページ | [Blog]10万ビュー突破! »