Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols

Michael Ben-Or

https://allquantor.at/blockchainbib/pdf/ben1983another.pdf

3. コンセンサスプロトコル

この節では簡単な確率的コンセンサスプロトコルを提示する。このプロトコルでは、プロセスは「ラウンド」ごとに情報の交換を遂行する。各ラウンドごとに、もしいくつかのプロセスがvに決定したら、次のラウンドでは機能している他のプロセスはすべて同じ値vに決定する。ある上限までの確率で、プロセスが決定しない場合、動作しているプロセスはすべて次のラウンドで合意に到達する。ラウンドの番号rはメッセージに付加されるので、プロセスはメッセージごとのラウンドを区別できる。

A - コンセンサスプロトコル

プロセスP: 初期値x_P

ステップ0: rに1を設定 r := 1

ステップ1: 全プロセスにメッセージ(1,r,x_P)を送信する

ステップ2: (1,r,*)という型のメッセージを N - t 個受信するまで待機する。もしも N/2 個より多くのメッセージが同一の値vであったら、全プロセスにメッセージ(2,r,v,D)を送信する。そうでなかったら、メッセージ(2,r,?)を送信する。

ステップ3: (2,r,*)という型のメッセージを N - t 個受信するまで待機する。

(a) D-メッセージ(2,r,v,D)が1個あれば、x_Pをvに更新 x_P := v

(b) t 個より多くのメッセージがD-メッセージであれば、vを確定/最終決定 decide v

ステップ4: rをインクリメント r := r + 1、ステップ1に進む。

定理1

N > 2tとする。t-コレクトなスケジュールがあり、プロセスの初期値は任意とする。上記のプロトコルは確率1で以下を保証する:

(i) すべての正しいプロセスは最終的に同一の値vに最終的に決定する

(ii) すべての正しいプロセスが値vで開始するならば、1ラウンドですべてvに決定する

(iii) あるラウンドrにおいて、いくつかの正しいプロセスがステップg(b)でvを決定するならば、他のすべての正しいプロセスは次のラウンドでvを決定する

注: N <= 2t の場合、おそらくコンセンサスは不可能。ネットワーク分断(partition)をシミュレートできるスケジュールがありえるから。

4. ビザンチン合意

障害プロセスが完全に故障し、しかも悪意のある計画でメッセージを送信する状況を想定。次に示す完全分散プロトコルは、そうした障害が存在してもなお合意に到達可能。プロセスは受信したメッセージの送信元を決定できると想定する。そうでなければ解は不可能なので、この想定は必須。この設定では、

スケジュールはメッセージシステムを注意深く監視？し、
各プロセスがステップを実行するタイミングを決定し、
障害プロセスが何を実行するか決定する。障害プロセスが高々t個であり、すべてのメッセージは正しいプロセスに最終的には配送される（無限回のステップを実行する？）とき、スケジュールはt-コレクト(t-correct)である。

B - ビザンチンプロトコル

プロセスP: 初期値x_P

ステップ0: rに1を設定 r := 1

ステップ1: 全プロセスにメッセージ(1,r,x_P)を送信する

ステップ2: (1,r,*)という型のメッセージを N - t 個のプロセスから受信するまで待機する。もしも (N+t)/2 個より多くのメッセージが同一の値vであったら、全プロセスにメッセージ(2,r,v,D)を送信する。そうでなかったら、メッセージ(2,r,?)を送信する。

ステップ3: (2,r,*)という型のメッセージを N - t 個のプロセスから受信するまで待機する。

(a) 少なくともt+1個のメッセージが(2,r,v,D)であれば、x_Pをvに更新 x_P := v

(b) (N+t)/2より多くのメッセージがD-メッセージであれば、vを確定/最終決定 decide v