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

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

今回は「リーダー選挙問題を解く自己安定アルゴリズム」についてです。
プロセスにそれぞれIDが割振られており、その値は不変とします。
また、プロセスは誰をリーダーと認めるか、
「leader」という変数にIDの値を格納するとします。
今回、リーダー選挙をするにあたって、
IDの値が最大のプロセスをリーダーとして認定するものとします。

すべてのプロセスは常に遷移可能とします。
P1とP2が通信し、P1の「leader」の値が「2」に更新されます。

今度はP0とP1が通信し、
P0はP1の「leader」の値と自分の「leader」の値を比較することによって、
自分の「leader」の値を「2」に更新します。

こうすることによって、
P2が無事にリーダーに選出されました。

一見これで解決したかのように見えますが、
ここで、故障が発生した場合どうなるでしょうか。

P1の「leader」の値が「3」になってしまいました。

P0はP1の「leader」の値を参照してしまい、
同様に「3」として値を更新してしまいます。

P2もP1の値を参照してしまい、
最終的には存在しないプロセスのID「3」を参照してしまいます。
こうなると、誰も選ばれなくなってしまうので、
このアルゴリズムは不適切です。

今回はここまでです。ありがとうございました。