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

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

今回は、「通信計算量の少ないリーダー選挙アルゴリズム」についてまとめました。

前回同様、パラメータが増えています。
今回は「phase」という概念が増えます。

立候補したプロセスは、自身のstatusを「candidate」にした後、
phaseを+1した後、左右のプロセスに送信します。

今回は、一度に説明するとややこしいので一旦片方ずつ説明します。
前回と同様に「waiting」状態のプロセスにメッセージが到着します。

右側のプロセスにメッセージが到着し、
右側のプロセスは自分の状態を「notleader」にし、
メッセージを隣のプロセスに送信します。

これを繰り返し、メッセージが1周します。

ここまでの分を便宜上一旦置いておいて、
止まっていた分のメッセージについて説明します。

同様に左側からもメッセージが流れますが、
プロセスは既に「notleader」状態のため、
そのままメッセージは流れ続けます。

何やかんやでメッセージは1周し、立候補していたプロセスがリーダーになります。

<何がおいしいのか>
すべてのプロセスがリーダーに立候補していたとします。

左右のプロセスに自分のIDを送信し、
それを受信したプロセスは自分がリーダーになれないことに気付きます。

そのまま更にID情報は流れていき、
最終的には自分のIDが1周したプロセスがリーダーになります。

このように、立候補していたプロセスが減るのが早いというメリットがあります。

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