４、リーダー選挙問題２

　O(n^2)のメッセージ数がかかるアルゴリズムを紹介した。以下では、O(n log n) のアルゴリズムを紹介する。

基本的なアイデアを示す。双方向リング上で考える。

ばつ印は、除外プロセスとする。それ以外は、始動プロセス。隣接したプロセス同士でプロセッサ番号を比較し、自分の番号が隣接したプロセッサ番号の中で、一番大きくないときに自分を除外プロセスへ移行する。このように、隣接したプロセスと自分のプロセスを除外していく。このようにすることで、少なくとも半分のプロセスへ減らせる。

　以上は、双方向リング上で考えたが、これを短方向リング上で実現する。アルゴリズムを以下に示す。

アルゴリズム3
[待機状態]
 (1) メッセージを受信しているなら (4) へ
[始動状態]
 (2) 自分の番号を p とした時、 (p,0) を送信してから (3) へ行く。
 (3) メッセージを受信しているなら受信レジスタをクリアする。
     そのメッセージ (a,i) の i が 0 なら (a,i+1) を送信し,i が 1 なら停止する。
 (4) 全ての受信メッセージをそのまま送信する。

(4)が除外されたプロセスに該当する。

（休憩）