分散処理を勉強した記録～その33～

この記事は、
「分散処理システム」著：真鍋義文　森北出版株式会社
を参考にしています。

今回は「リーダー選挙問題を解く自己安定アルゴリズム」についてです。
前回のアルゴリズムの場合、
leader変数を書き換えられると誰も選出されない問題がありました。

そこで、リーダーまでの距離「distance」をパラメータに追加します。
distanceは定数なので書き換えないものとします。
上記の例だとIDが3のプロセスをリーダーとしているので、
左側のプロセスになるほど、distanceの値は大きくなります。

初期状態だと、distanceの値はそれぞれ0になります。

P2がP3の値を読み取ります。
(0 <= P2のdistance < (N-1)) && ((P2のleader < P3のleader) || (P2のleader == P3のleader && P2のdistance < P3のdistance))
の場合、leaderをP3の値にし、
distanceはP3の「distance」の値+1したものをP2の「distance」に設定します。

ここで、全体のプロセス数Nは「3」です。
P2の「leader」を「3」に、「distance」を「1」にします。

同様に、P1がP2の値を読み取ります。

すると、P1の「leader」と「distance」はそれぞれ書き換わります。

ここで、P2の「leader」の値が何らかの故障で「4」になったとします。

再度P1がP2の値を読み取ります。

P1の「leader」は「4」になりますが、
「distance」は変化しません。

P2がP1を読み取ります。

P1とP2のleaderの値は同じなので、
遷移条件を満たします。

P1のdistanceに+1したものがP2のdistanceに設定されます。
distanceがN-1より大きくなることは有り得ないので、
P2のパラメータは初期化されます。

以上で終わりです。ありがとうございました。