AChord 4

後日といいつつ書いてみるPart2
　
AChord3は長くてまとまりがないですね。
図を入れたら分かりやすいんですが、文章なので分かりにくいパターンになっちゃってます。
もう一回整理しないとだめかも・・
　
ってことで、一応最後のフィンガーテーブルの更新です。
この辺はSuccessorリスト,Predecessorリストの話と似ていて
実は実装によっていろいろなパターンが考えられると思います。
というわけで重要で基本的な匿名性に関係ありそうなところのみ説明する方針にします。
　
AChordではフィンガーテーブルの更新にfind_best_matchという動作を取り入れてます。
例によってこれを反復的に行います。
　
まず、find_best_matchの反復でばれちゃうノードの数ですが、１つのフィールドについて最大logNだけ接続することになりますので
フィンガーテーブルの要素がk個あればk*logNのノードにIPがばれてしまいます。
普通はlogNだけ要素を持つでしょうからlogN*logNだけばれちゃうことになりますね。
これはなんか結構ばれてるような・・気がしなくもないです。
　
詳細を見てみましょう。
今、ノードAがフィンガーテーブルのi番目の要素を更新しようとしたとします。
このとき、Aは自分のフィンガーテーブルからランダムに選んだノードBに対してfind_best_match(i)を呼び出します。
　
find_best_matchを呼び出されたノードBは、B自身およびBのフィンガーテーブルの要素の中から
Aのフィンガーテーブルのi番目にもっともふさわしいノードを探して返してきます。
B自身も返せることができるということですね。
　
find_bast_matchの名前のとおり、意味合いとしてはこれだけなのですが
これだとfind_best_matchを呼びまくればIPが全部ばれてしまうんじゃないかということになりかねませんので
AChordでは得意のIPからハッシュ値を計算する方法で対処します。
　
find_best_matchは反復的に呼び出されますから、接続されたBは
AのIPからフィンガーテーブルのi番目の理想のハッシュ値を計算できます。これは通常「Aのハッシュ値+2^i」です。
そしてBは必ずこの数を超える最小のノードを返すことにします。
これによって基本的にBはAのIPが変わらない限り同じノードを返しますから
ばれちゃうノードの数を減らせますよってことになります。
　
AはこのBの返してきたノードに対して、さらにfind_best_match(i)を反復的に呼び出します。
最終的に、いつか自分自身を返すノードが出てくることになります。
これは自分が一番i番目の要素として最適という風に言ってきてるわけですから
今までAがi番目に保持していたノードとfind_best_matchで得たノードを比べて
最適な、つまりハッシュ値の小さいほうを選択すれば出来上がりです。
　
かなり長くなりましたが、一応AChordの主要な部分はこんな感じです。
KeyLookupの方法についてはイメージしやすくて
実装もあんまりいろいろなパターンを考えられないでしょうから、思ったよりは簡単に実装できるかも？
ただ、逆にSuccessorリスト,Predecessorリスト、フィンガーテーブルの更新については
反復的な方法で、IPからハッシュ値を計算して情報を最小に抑えるという基本さえ守ればよくて
いろいろな処理手順が考えられますから、実装もいろいろになりそうです。
まぁ難しそうですけどね