Imony Project
FlashBox
トップページ ･ Imonyとは

分散ハッシュテーブル手法―馬とび

スレの引用

俺が新しいP2P作ろっか？
419 ：332：2005/11/07(月) 20:49:52 ID:49QjtA1D0
>Imoさん、私とあなたとの考えは根本的に違います。

hashを基に完全な一次元トーラスが完成していると仮定しての話になりますが、
(hashを基に完全な一次元トーラスを作るのは難しくない)
N個のネットワーク参加ノードに対し必要なノードリスト数はlogNです。
また、ノード構築に必要な問い合わせもlogN回で済みます。

>407
shareのハッシュ値です。とんだ間抜けなことをしてしまい申し訳ございませんでした。
download_1128362917_332_ss000.PNG 332DWECG0Hjdt 188,535 2f1e3653ec8674dc54a7a86d5f9192412b292998
download_1128362917_332_ss001.PNG 332DWECG0Hjdt 84,088 0676d96f52353d0c75a3c3529a8851c86208d510

??? ：332：2005/11/07(月) 23:08:17 ID:49QjtA1D0
んじゃ、おらも
シミュレーションはいまだ作成中です。

分散ハッシュテーブル名：馬とび
>419に書いたように完全な一次トーラスが完成しているとする。
このとき各ノードは自分のすぐ両隣のノードは必ずわかっている。
このとき、問い合わせに方向性を持たせるため、時計回りの方向に問い合わせを行うものとする。

各ノードは、自分の1個隣のノードに、あなたにとって1個隣のノードを教えてと問い合わせる。
このとき、1個隣のノードが教えてくれた1個隣のノードにとって1個隣のノードは、自分にとって2個
隣のノードである。
先ほどと同じようにして、
各ノードは、自分の2個隣のノードに、あなたにとって2個隣のノードを教えてと問い合わせる。
このとき、2個隣のノードが教えてくれた2個隣のノードにとって2個隣のノードは、自分にとって4個
隣のノードである。
さらに同じようにして
各ノードは、自分の4個隣のノードに、あなたにとって4個隣のノードを教えてと問い合わせる。
このとき、4個隣のノードが教えてくれた4個隣のノードにとって4個隣のノードは、自分にとって8個
隣のノードである。
さらに、さらに、
各ノードは、自分の8個隣のノードに、あなたにとって8個隣のノードを教えてと問い合わせる。
このとき、8個隣のノードが教えてくれた8個隣のノードにとって8個隣のノードは、自分にとって16個
隣のノードである。
・・・以下延々と続く
ここの部分は自分で紙に書いて実際にやってみるとよく分かるよ。

424 ：332：2005/11/07(月) 23:15:34 ID:49QjtA1D0
一般化すれば
各ノードは自分のＡｎ個隣のノードに、あなたにとってAn個隣のノードを教えてと問い合わせる。
このとき、An個隣のノードが教えてくれたAn個隣のノードにとってAn個隣のノードは、自分に
とってA(n+1)(=2*An)個隣のノードである。
ただし、A1 = 1　かつ　n>=1

先行論文が存在してないと願っているよ・・・

生意気かもしれませんが、馬とびにより新しいDHTを考案しようという流れはなくなると考えています。
今後は馬とびをどううまく応用するかがDHT研究の焦点になると考えています。

理由：
一次元トーラスを作ることは簡単
隣のノードの隣の・・・と問い合わせていくことも簡単
簡単なことの組み合わせにより、DHTの実装もとてつもなく簡単になります。
さらに、参加ノード数をNとすると検索量はO(logN)です。
検索量も理想値通りとなります。
あるハッシュ値を検索することと、あるハッシュ値を範囲に含むノードを見つけることは
同値ですので、ネットワークが完成しているところに新しくノードが参加しようとした場合にも
O(logn)のコストで新しいノードが参加することが出来ます。

自分が責任を持つハッシュ値の範囲は一次元トーラスの半円だったりしますが、
詳しく分かりやすい説明はシミュレータ完成時に併せて行います。

とりあえず、馬とびが他の論文で発表されていなく、かつ特許も取得されていない場合は
このレスにより公知の技術となりましたので、特許料なしでみなが自由にDHTを実装する
ことができるようになります。

公知となるかどうかが問題ですね・・・

Copyright(C) 2004/04/01-2009/01/07 FlashBox.
All rights reserved. Programed by Imo.
Designed by Imo, N-Style, siv.

Time: 5.1ms -157
管理モード