Rabin's algorithm for Byzantine Generals Problem - toyofuku/flp GitHub Wiki

Rabin's algorithm for Byzantine Generals Problem. Notes by Sanjeev Arora, Fall 1995 (updated Fall 2005)

https://www.cs.princeton.edu/courses/archive/fall05/cos521/byzantin.pdf

ビザンチン将軍問題(Byzantine Generals Probrem): n = 3t + 1 台のプロセッサのうち少なくとも 2t + 1 台は正しく動作する。 (残りのt台は気まぐれにおかしな動作をする、あるいは障害がある) 初期状態でプロセッサiはビットb_i ∈ {0,1}を保持。 メッセージを交換しあってあるビット b_final に合意形成するのがゴール。 良いプロセッサの b_i がすべて同じなら、b_finalが求める同一値ビット。 そうでなければ、すべての正しいプロセッサが(b_finalが何であるか？)同意している限りにおいて、b_finalの値が何であるべきかに関して厳しい要求はない。

ビザンチン合意問題と呼ばれる。poly(n)のステップで決定論的アルゴリズムで解ける。障害プロセッサの数が n/3 を超えるとき、そのような分散アルゴリズムは存在しないことが知られている。

Rabinの考えた簡単なランダム化アルゴリズムを解説する。 このアルゴリズムは、各ステップごとにトスされるグローバルなランダムコイン(random coin)を想定する。コインの結果はすべてのプロセッサから見える。

プロセッサは票(vote)と呼ばれるビットを常時維持する。プロセッサiの票の初期値はb_i。 各ラウンドの開始時点で各プロセッサは票の値を他のすべてのプロセッサに送信する。 各プロセッサは、受信した（自分の票も含む）3t+1の票を調べる。

• 票の値で多い方をmajとする。
• この値の票数をtallyとする。 majとtallyの値はプロセッサ間でまちまちになる。なぜなら障害/悪意のあるプロセッサが票の値と異なる値を別のプロセスに送信して、事態を混乱させることができるから。

各プロセッサは各ステップごとに以下のアルゴリズムに従う。

tallyの値をもとに以下のステップに従う:

1. tally >= 2t+1 の場合、 vote = majに設定。
2. tally <= 2t の場合、 グローバルコインのトスの結果をみる。表ならvote=1、裏ならvote=0に設定。

証明

良いプロセッサはすべて同じ初期値をもつなら、1ラウンド目でこの値に全員が投票する。 それ以外の場合、最低でも1/2の確率で、すべてのプロセッサが同じ値に投票することを示す。 （この状態になった場合、それ以後はすべてのプロセッサで tally >= 2t+1 が成り立つ。すべてのプロセッサはアルゴリズムの(1)を実行し続ける。）

2つのケースが考えられる。

(i) いくつかのプロセッサで tally >= 2t+1が成立する （maj=bのbはb ∈ {0,1}。） 障害プロセッサはt個しかないので、すくなくとも t+1 個の良いプロセッサが投票の値としてbを送信しなければならない。 つまり、同じラウンドで tally >= 2t+1 と maj = 1 - b の両方を満たすプロセッサはない。 上記のアルゴリズムにある(1)か(2)のうち、 他のプロセッサが実行するのがどちらのステップであっても、 最低1/2の確率ですべて票はbに設定される。

(ii) 良いプロセッサで tally >= 2t+1 が成立しない場合。 この場合、全員がステップ(2)を実行する。確率1で票は同じ値に設定される。

練習問題。このアルゴリズムを改造して、アルゴリズムが成功したタイミングをプロセッサが検知できるようにしよう。すべての良いプロセッサが同じ値で投票したとき成功とみなす。