３、リーダー選挙問題

　分散アルゴリズムでは、情報を１つの特別なプロセスに集めることで問題を解くことができる。しかし、そのような特別なプロセスを事前に決定してしまうと問題があることを説明した。したがって、そのような特別なプロセスを１つ作り出す問題、リーダー選挙問題を考える。ただし、各プロセスは、通信路でリング状に接続されているとする。

　まず、以下のアルゴリズムを考える。ただし、各プロセスは、変数 L を持ち 0 で初期化されている。この変数 L は、アルゴリズム終了時に 1 であるプロセスがリーダーであるということを示している。

アルゴリズム1
[待機状態]
 (1) メッセージを受信していれば、(3) へ行く。そうでなければ、(1) にとどまる。
[始動状態]
 (2) 自分のプロセッサ番号を送信し (3) へ行く。
 (3) メッセージ M を受信していれば、受信レジスタをクリアする。
     M が自分のプロセッサ番号  であるなら、L<-1とし、さらに 1 を送信し終了する。
     M が 1 なら単に終了する。それ以外なら M を送信し (3) へ行く。

このアルゴリズム1は、始動プロセスが自分のプロセッサ番号を、リング状に一周させ自分をリーダーにする。ただし、始動プロセス P1 のメッセージが一周する前に、他のプロセス P2 が P1 のメッセージを受け取る前に始動状態になった場合、明らかに P1,P2 のメッセージ両方とも一周するため、二つとも L=1 となる。（図を使って直感的に説明する）

（記事が消えたぁぁああああorz,書き直す）
図を見る。リーダーが決まるのは、M1 が一周して戻ってきたときである。待機状態であるプロセスが M1 を受け取ったとき (3) へ移行する。しかし、待機状態であるプロセス P2 が M1 を受け取る前に始動プロセスになり M2 を送ると M2 を止める仕組みがないため一周する。したがって、P1,P2 がリーダーになってしまう。

　以上から、複数の始動プロセスがあったときにメッセージを止める仕組みが必要となることが分かる。簡単に修正すると、送られてきたプロセス番号が自分のプロセス番号より小さいときに止めるようにする。具体的に

アルゴリズム2
[待機状態]
 (1) メッセージを受信していれば、(3) へ行く。そうでなければ、(1) にとどまる。
[始動状態]
 (2) 自分のプロセッサ番号を送信し (3) へ行く。
 (3) メッセージ M を受信していれば、受信レジスタをクリアする。
     M が自分のプロセッサ番号  であるなら、L<-1とし、さらに 1 を送信し終了する。
     M が 1 なら単に終了する。
     if( M < 自分のプロセス番号 )
         then (3) へ
         else M を送信し (3) へ行く。

とする。このようにすることで、複数の始動プロセスがあっても、最も大きいプロセス番号のみが一周する。

　このアルゴリズム２では、リングにそってプロセス番号が降順に並んでいるとき、n+(n-1)+…+1のメッセージ数が必要となる。つまり、O(n^2)のメッセージ数となる。