[DHT]DHTとホップ数の関係[その2]～Chordの平均ホップ数を考えよう

前回は直感的な方法でDHTのホップ数について推定した。今度はChordに絞ってホップ数を調べる事でより理解を深める事にしよう。

□Chordのリンク数からホップ数を推定

まず、Chordのノード参加数をN=2^xとしよう。2^ｘとは２のｘ乗を表す事とする。ここで1ノード当たりのリンク数はlog(N)＝ｘである事に注意。

平均ホップ数を計算するときに発想を転換しよう。今1ノードｘあたりのリンクがある。すると、P回ホップ数すると、ホップ可能な総ノード数LはだいたいL=x^Pとなる。x^P=Nであれば、P回ですべてのノードにアクセスできると大体考えられる事ができる。つまり、平均ホップ数P=log(N)/log(x)=log(N)/log(log(N))～O(log(N))となる。
最後の近似はやや荒っぽい。計算がlog(N)より小さく出たのはホップ時に到達するノード数の仮定が甘いからである。

□もう少し解析的にホップ数求める方法

今度は違った見方をしてみよう。この手法によるホップ数算定はこのBlogが初発表になるはずだ。

今ノード０からのリンクを考えると、総ノード数を2^xとして距離2^0、2^1・・・2^{x-1}のノードとリンクを張るはずだ。
ところで、ハッシュ空間にすべてノードが埋まっている場合、あるノードへ到達する際に次ホップする距離はホップ毎に単調減少するはずだ。（この証明は読者にお任せする。）
つまり、次ホップまでの距離をR、ホップ数をｔとするとR(t+1)＜R(t)である。
ところが、R(ｔ）として取れる数は、{2^0、2^1・・・・2^{x-1}}というlog(N)個しかない。つまり、最大ホップ数はO（log(N))より超える事がないはずである。

ここで問題なのは、O(log(N))というステップ数で本当に2^xの空間のすべてのノードに到達できるかということである。

そのために補題を作る。
補題：
2^{x-1}+1≦P＜2^x となる整数Pは、集合S{2^0、2^1、・・・2^{x-1}}の和で表される。ただし、この和において、集合Sの各元は高々1回しか現れないとする。

証明：帰納法により証明可能。

この補題により、O(log(N))のステップ数以内に、任意のノードに必ず到達できることが証明できた。
今はハッシュ空間にすべてのノードが参加していることを仮定した。ノードが部分的に参加してない場合の証明については読者にお任せする。