論文メモ Impossibility of Distributed Consensus with One Faulty Process

December 18, 2020

プロセスが1つでもクラッシュしうる場合には常に含意を保証できる完全な非同期アルゴリズムは存在しないことを示した。 この定理はFLP帰結とよばれている。 FLPは、著者Fischer, Lynch, Patersonの頭文字に由来する。 ここでの完全は、プロセスの処理速度やメッセージの配信遅延に仮定をおかず、同期クロックがないためにタイムアウトを使えず、ほかのプロセスが別のプロセスの障害を検知できないことを意味する。 いいかえると、含意アルゴリズムを実装するには上のいずれかを仮定しなければないことを示した。

証明には、背理法をつかう。 \(N(\ge 2)\)個のプロセスが\(0\)か\(1\)いずれかに含意する問題で、1つのプロセスに障害があっても含意アルゴリズム\(P\)が常に含意形成できると仮定する。

各プロセス\(p\)は、決定的にふるまい、\(b, 0, 1\)いずれかをとりえる1ビットの入力、出力レジスタをもつ。 出力レジスタの初期値は\(b\)であり、一度だけ\(0\)か\(1\)を書き込める。 出力レジスタが書き込まれた後の状態をdecision stateとよぶ。

プロセス\(p\)に送られたメッセージ\(m\)は、\(p\)に届くまでの間、メッセージバッファにイベント\((p, m)\)として保存される。 各ステップでは、バッファ内のイベントを選び、メッセージを配信する。 配信の成否は非決定的で、メッセージ\(m\)が\(p\)に届いたら\((p, m)\)をバッファから削除され、届かない場合はバッファの状態は変わらない。

\(N\)個のプロセスとメッセージバッファの状態はあわせてconfigurationとよぶ。 特に、全プロセスが初期状態でメッセージバッファが空の状態をinitial configurationとよぶ。 また、Configuration \(C\)に適用可能なイベント系列\(\sigma\)をスケジュールといい、実際に実行されたスケジュールをrunという。 decision stateにあるプロセスの存在するrunはdeciding runとして区別される。 障害のために受信可能なメッセージ数が有限のプロセスが高々1つ存在しても、ほかのプロセスには全てのメッセージがいずれ届くなら、このようなrunは許容可能と呼ばれる。

常に含意できることを、以上の状況にあわせて言いかえる。 Initial configurationから到達できるConfigurationには高々1つのdecision valueしか存在しない。 \(0\)と\(1\)どちらもdecision valueになりえるinitial configurationから到達可能なConfigurationが存在する。 この2つの条件を満たす含意アルゴリズム\(P\)をpartical correctであるという。 partial correctであり、すべての許容可能なrunがdeciding runであれば、\(P\)はtotally correctであるという。 FLPの帰結のいうところは、totally correctな\(P\)は存在しないことである。

以上の状況では、次の3つの補題が成立する。

$$ \mathcal{D}=e(\mathcal{F})=\{e(E)\mid E \in \mathcal{F}\text{かつ}e\text{は}E\text{に適用可能}\} $$ とすると\(\mathcal{D}\)はbivalentなconfigurationを含む。

ここで、\(C_0\)をbivalentなinitial configurationとする。 \(C_0\)は補題2より存在する。 \(C\)をbivalentなconfiguration、\(m\)を\(C\)のメッセージバッファにある最も早く\(p\)に送られるメッセージとする。 補題3より\((p, m)\)を最後に適用するイベントとして\(C\)から到達可能でbivalentな\(C'\)が存在する。 このとき、常にbivalentなconfigurationが無限に続くスケジュールになるため、runが許容可能であることと矛盾があらわれ、\(P\)がtotally correctでないことががわかる。