論文メモ 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としてほかのrunと区別される。高々1つの障害のあるプロセスがあり、ほかの正常なプロセスには全てのメッセージがいずれ届くなら、このようなrunは許容可能とよばれる。

以上の設定にもとづいて、常に含意できることを言いかえる。次の2条件をみたす含意アルゴリズム$P$をpartial correctであるという。

initial configurationから到達できるconfigurationには高々1つのdecision valueしか存在しない。
$0$と$1$どちらもdecision valueになりえるinitial configurationから到達可能なconfigurationが存在する。

partial correctであり、すべての許容可能なrunがdeciding runであれば、$P$はtotally correctであるという。 FLPの帰結のいうところは、totally correctな$P$は存在しないことである。

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

補題1. configuration $C$からスケジュール$\sigma_1, \sigma_2$でそれぞれ$C_1, C_2$に遷移できる。ここで、$\sigma_1$と$\sigma_2$のステップに含まれるプロセスの集合が互いに素であれば、$\sigma_2$を$C_1$に、$\sigma_1$を$C_2$に適用でき、両者は最終的に同じ状態$C_3$に到達する。
補題2. configuration $C$から到達可能なconfigurationのdecision valueが$0$と$1$どちらもありえるなら、$C$はbivalentといい、$P$にはbivalentなinitial configurationがある。
補題3. $C$をbivalentなconfiguration, $e=(p, m)$を$C$に適用可能なイベント、$\mathcal{F}$を$e$を適用せずに$C$から到達可能なconfigurationの集合、$\mathcal{D}$を

$$ \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でないことががわかる。

論文をこちらからダウンロードできます。