AChord 3

えらい長くなってきました・・orz

各ノードはSuccessorリスト,Predecessorリストを最新のものに保つために定期的にチェックを行います。
そこでネットワークにすでにノードAとCがいて、その間に新たにノードBが参加する場合を考えます。
リストの個数はわかりやすく1個としておきましょう。
参加する前の状況としてはAのPredecessorにはCが登録され、CのSuccessorにはAが登録されています。
図としてはこんな感じでしょうか
　

Ａ→←Ｃ        Ｂ(蚊帳の外)

　
AChordではネットワークの参加にはfind_successorの反復バージョンを使いますから
いずれAに対してBがfind_successor(B)を呼び出すことになります。
　
さて、Aはこのときいくつかの作業を行わなければなりません。
まず本当にBがAとCの間に入るのかをIPからチェックします。
これが妥当だとすればAのPredecessorはCからBに変更しなければなりません。
という訳でBのAに対するfind_successor(B)の呼び出しによって
AのPredecessorはCからBに変更されます。
　

Ａ←Ｃ

　→Ｂ

　
もちろんBのSuccessorにはAが登録されることになります。
同時にBは「Aの今までのPredecessorを教えてもらう」ことで、ここまでの時点で
AのPredecessor:B
BのSuccessor:A
BのPredecessor：C
という処理を行うことができます。
　

＿＿＿＿＿＿ 

↓　　　　｜

Ａ→←Ｂ→Ｃ

　
残りの問題はCのSucessorがいまだにAだということです。
　
各ノードは定期なチェックによりリストを更新しますから
当然CはAに対してCのSuccessorがAかどうか、逆に言えば、
「AのPredecessorがCかどうか教えてもらう」必要があります。
　
ここでちょっと一息いれましょう。
少し前にBがAに「Aの今までのPredecessorを教えてもらう」という部分がありました。
ここではCがAに「AのPredecessorがCかどうか教えてもらう」という流れになっています。
どちらもAのPredecessorを知りたがってる部分で匿名性に関係してきます。
AChordの本質はなるべくIPを教えないというところからきていますから
この部分に当然制限が掛かってきます。
　
その制限というのは、AがPredecessorについて尋ねられた場合、
その相手が「現在のPredecessor」であれば必ず完全な答えを返します。
もし相手が「今までのPredecessor」であった場合には1度のみ完全な答えを返します。
この1度というのが重要です。
もちろん、現在でも今まででもPredecessorではないノードについてはエラーを返します。

　
AはBの登場によって自分のPredecessorがCよりBのほうが最適であることを知ります。
そこで「今までのPredecessor」としてCを覚えておき、「現在のPredecessor」としてBを採用します。
以後、AはBからのPredecessorに対する質問には完全に答えることになりますので
今までのPredecessorとしてCがいたことを伝えることができます。
そしてCからAへのPredecessorの確認時には、CはAの「今までのPredecessor」ですから
今回だけ完全な答えとして、BがPredecessorになったことを伝えるようにします。
そして、「今までのPredecessor」として覚えていたCの存在を忘れるようにします。
　　　
これでCは自分のSuccessorがBになったということを知ることができ、リストを更新することになりますが
それ以降はCにとってのSuccessorはBになるのでAのPredecessorについて確認することはできません。
たとえばAとBの間にまた新しいノードが参加してもCは知ることはできないし
知る必要もないということになります。
　
なかなかわかりにくいですが、Successorリスト,Predecessorリストについての制限をまとめると
　
CのSuccessorがAである場合に、CがAのPredecessorについての確認ができるのは
AとCの間に新たにノードBが参加して、CがAのPredecessorにアクセスすることで
Aが「今までのPredecessor」であるCの存在を忘れてしまうまでの間
ということになります。
　
最後の関門「フィンガーテーブルの更新」についてはまた後日ということで。