FLP不可能性の概要

http://the-paper-trail.org/blog/a-brief-tour-of-flp-impossibility/

分散システム理論における最も重要な成果のひとつは、フィッシャー、リンチ、パターソンによって1985年4月に公表されたものである。分散コンピューティングで最も影響力のある論文として評価され、ダイクストラ賞を受賞した短い論文「1つの障害プロセスを持つ分散コンセンサスの不可能性」は、非同期環境における分散プロセスの実現可能性に対する上限を定義した。

「FLPリザルト」として知られているこの特定の結果は、それまでの5〜10年間にわたり分散システムにおいて続いていた論争を解決した。コンセンサスの問題、すなわち分散ネットワークを構成するプロセッサを同一の値に一致させるというコンセンサス問題は、プロセスが同時に実行される同期設定においては解決可能であることが知られていた。特に、プロセッサが故障し、計算がそれ以上続行できない類の障害に対して、同期ソリューションは回復力があった。わかりやすく言えば、同期モデルの場合、1台のプロセッサからの応答をステップ全体が待機しているとき、もし応答がなければクラッシュしたと推定することで障害を検知できる。

この種の障害検知は、非同期設定では不可能である。1台のプロセッサが作業を完了し、応答のメッセージを送るまでに要する時間には上限がない。したがって、プロセッサがクラッシュしたのか、単に応答するのに長時間を要しているのかを区別できない。FLPの結果は、非同期設定において、1台のプロセッサだけが故障した場合は、コンセンサス問題を解決する分散アルゴリズムがないことを示している。

この記事では、証明自体の詳細を追ってみたい。非常に微妙ではあるものの、短くて重大であるからだ。はじめにコンセンサス概念を解説し、いくつかの表記と前提を説明した後、論文における主要な2つの補題を解説する。

コンセンサス

コンセンサスの問題は、分散システムの研究において基本中の基本である。分散プロセッサ間で値を一致させる技術は、多くのアプリケーションで必要とされる。たとえば、トランザクションをデータベースにコミットするかどうかを決定する問題は、多数のレプリカ間の合意アルゴリズムによって決定できる。コンセンサスとは、ある値への「投票」と考えることができる。

いくつかの論文は、敵の城を将軍たちが包囲している、将軍はそれぞれ離れた陣地にいる、これから全員で敵を攻撃するかどうかを決定する、このような文脈を問題にしている（ビザンチン将軍問題）。合意アルゴリズムが機能しなければ、おそらく一人の将軍だけが攻撃に突入するが、他の将軍は全員撤退し、最初の将軍は敵の反撃で自滅する。

コンセンサス問題には「強さ」に応じてバリエーションがある。通常、強い問題の解決策は、同時に弱い問題を解決する。強いコンセンサスの形態は次のとおり。

いくつかのプロセッサがあり、それぞれ初期値を持つ：

• 障害のないすべてのプロセスは最終的に値を決定する
• すべてのプロセスは同一の値になるように決定する
• いくつかのプロセスによる提案をもとに値が決定されなければならない

これら3つの性質は、終了性(termination)、合意性(agreement)、妥当性(validity)と呼ばれる。この3つの特性を満たすアルゴリズムは、コンセンサス問題を解決すると言える。

終了性と合意性はかなり自明だ。障害ノードからは特定の動作がなくてもかまわない点に注意しておこう。障害ノードは不完全であり例外なのだ。 妥当性はもっともらしく思えるが巧妙である。妥当性の背後にある概念は、初期値の集まりが何であれ、「反対」の値を決定するへそ曲がりを除外するのが狙いだ。このようなアルゴリズムは、終了性と合意性を満たすが、完全に無意味であり、まったく使い道がない。

FLP証明は、実際にはわずかに弱いコンセンサスの形に関係している。終了性のためには、障害のないいくつかのプロセスが決定するだけで十分である。常に自分で自分の値を決定する特別なプロセスを持つだけでは十分でない。プロセスは故障する可能性があるので、故障プロセスの代わりに別のプロセスが弱い終了性を満足させる必要があるからだ。

強いコンセンサスの解は、弱いコンセンサスの完全に良い解でもあるのは明らかなので、後者の可能性を否定することによって、FLP結果は同様に前者に対する解決策を排除する。

単純化のため、可能な値は0と1で考える。論文での主張を一般化すると、より多くの値でも成り立つ。

システムモデル

設計された実行のコンテキストと分散システムについての前提(assumptions)に関する議論がなければ、分散アルゴリズムのまともな議論にはならない。この前提はシステムモデルと呼ばれ、システムモデルの選択は、どんなアルゴリズムが適切であるかに大きな影響を与える。実際、この論文は、ある特定のクラスのシステムモデルにおける不可能な結果に全面的に関係している。

現実に即したモデルからより理論的なモデルまで、実にさまざまなシステムモデルがある。その大部分は、いくつかの基本特性が共通している。分散されたプロセッサのネットワークがあり、各プロセッサはグラフのノードに対応し、グラフのエッジは通信リンクであり、メッセージが送信される。 各プロセッサが時間の経過をどのように見ているかによってバリエーションがある。それはリンクが信頼できるか、プロセッサの故障があるか、といった違いがある。

FLP不可能性の結果は非同期モデルに基づいている。非同期モデルは、実際にはタイミングに関してある特性を示すモデルのクラスである。非同期モデルの主な特徴は、送信されたメッセージの受信、処理、応答にプロセッサが要する時間の上限がない点にある。したがって、プロセッサが故障したかどうかを知ることは不可能である。あるいは処理に長い時間がかかるとも言える。非同期モデルは弱いモデルだが、物理的にまったく非現実なわけではない。ウェブサーバではページを提供するために長い時間がかかるように見えることがある。今日ではモバイルアドホックネットワークのさらなる普及にともない、ネットワークのデバイスは、バッテリ節約のために処理中に電源を落とすことがある。後で再開したとき、何もなかったかのように継続する。これは非同期モデルに適合する遅延の具体例のひとつだ。

他のモデルは、インターネットのようなネットワークに適切だが、完全に非現実的である点を除けば、非同期モデルは非常に一般的だ。

プロセッサ間の通信リンクには信頼性があると想定されている。信頼性が低いリンクがあれば、同期モデルでもコンセンサスの解が見つからないことはよく知られていた。非同期システムにおいては信頼性の高いリンクを想定してもコンセンサスが不可能であることを証明すれば、FLPの結果はより強くなる。TCPは十分に信頼性の高いメッセージ配信を提供するので、これは現実的な想定である。

プロセッサの故障はフェイルストップモデルとみなすことができる。これは、プロセッサが故障すると正しいが動作できないことを意味する。より一般的な障害モデルになると、ビザンチン障害のように、プロセッサが実行するアルゴリズムから勝手に逸脱して故障するようなものもある。ここでも、モデルを強化することで、つまり何が可能であるかについて強い想定を設けることによって、FLPの結果はより一般化される。次のような主張である。もし与えられた問題が、悪化する事象がほんのわずかしかない非常に制限された環境で解決不可能であると証明されたら、悪化する事象がより多くなる環境でも解決不可能である。

形式的モデル

これらの特性を形式的モデルにするには、いくつかの表記法を導入する必要がある。論文の第2節では、システムモデルが注意深く定義される。N(>=2)個のプロセッサの間でのメッセージ送信によって通信が行われる。メッセージはpとmの組(p,m)で示される。pはメッセージの宛先になるプロセッサであり、mはメッセージの内容である。メッセージは、メッセージバッファと呼ばれる抽象データ構造(multiset)に格納される。複数の要素が許される集合であり、2つの操作がサポートされている。send(p,m)はメッセージ(p,m)をメッセージバッファに配置する。receive(p)は、宛先がプロセッサpのメッセージを返す（このときメッセージバッファからメッセージを削除する）が、特別な値θを返すこともある（このときは何もしない）。

受信のセマンティクスは直感的ではないが、重要な意味がある。メッセージシステムにメッセージが存在しない場合、receive(p)はθを返す。p宛のメッセージがあれば、receive(p)はランダムにいずれかの値を返すが、θを返す場合もある。

これは、メッセージが非確定的に配信され、それらが任意の順序で受信され、非同期モデルに従って任意に遅延される可能性があるという考えを捉えている。唯一の要件は、receive（p）を無限に何度も呼び出すことによって、メッセージバッファ内のすべてのメッセージが最終的に配信されることだ。これは、メッセージが任意に遅延される可能性はあるが、完全には失われていないことを意味する。これはメッセージが非決定的に配送されるという概念を捉えている。受信の順番は保証されない。これは非同期モデルで勝手に任意の遅延が生じるのと同様である。ただし唯一の要求事項として、receive(p)が無限に呼び出されると、メッセージバッファにあるすべてのメッセージは最終的にpに配送されなければならない。これはメッセージは勝手に遅延されるかもしれないが、最終的に完了することを意味する。

構成(configuration)は、すべてのプロセッサの内部状態として定義される。実行中のアルゴリズムの現在ステップ(PC)とメモリの内容、さらにメッセージバッファの内容がこれに相当する。システムはある構成から次の構成に1ステップで遷移する。プロセッサpはreceive(p)を実行し、別の内部状態に遷移する。このため、システム状態を進化させるものは、メッセージバッファからプロセッサが1つのメッセージを受信するか、nullを受信するかにしかない。そのため各ステップでは、受信メッセージ(θの可能性もある)と受信するプロセッサが定義される。論文では、この組をイベントと呼んでいる。つまり、ある構成から別の構成にイベントを介して遷移する。

受信操作は非決定的であり、ある初期状態（コンセンサスの観点からみれば、各プロセッサがもつ開始値の集合によって区別される）に対して可能な実行の候補は多数存在する。あるアルゴリズムがコンセンサスの解になることを示すには、可能なあらゆる実行に対して、妥当性、合意性、終了性を満たす必要がある。実行の集合には、プロセッサが勝手に遅延する可能性も含まれる。これは、メッセージが受信されるまでに、ある任意の回数の操作でθが受信されることでモデル化される。特定の実行は、ある構成Cから始まる可能性のあるイベントの無限シーケンスによって定義される。これをスケジュールと呼び、ステップのシーケンスを選択してスケジュールを現実化することが実行過程(run)になる。

非障害プロセスは、実行過程において無限に多数のステップを処理する（アルゴリズムがその作業を完了した後、おそらく最後にθを受信する?）。そうでなければ、プロセスは障害とみなされる。許容可能な実行過程は、たかだか1個のプロセサが障害になるケースである（障害の検知はシステムモデルの要件である）。最終的にすべてのメッセージは配送される（これは、あらゆるプロセッサは最終的に無限回受信することを選択になることを意味する）。コンセンサスの特性に対応して、いくつかのプロセスが最終的に決定に至ることを、決定的実行過程(deciding run)と呼ぶ。もしあらゆる許容可能な実行過程が決定的実行過程(deciding run)であれば、コンセンサスのプロトコルは全面的に正しい。

論文では、これらの難しい定義がされた後、正しいコンセンサスのアルゴリズムが存在しないという定理が示される。この定理の背後にある概念は、許容可能な実行過程の存在を示すことである。このとき、故障したプロセッサが1個だけで、あらゆるメッセージは最終的に配送される。これは決定的実行過程ではない。すなわち、最終的に決定するプロセッサがない。これはコンセンサスの一般的不可能性を証明するのに十分である。与えられたプロトコルが動作しなくなるような、そうした初期構成があることを示すだけで十分である。その構成から開始するのを除外できないからだ。その結果、プロセッサが決定しないので、永遠に動作するプロトコルになる。

証明

FLPの論文の基本概念は「あるプロトコルにおいて非決定であり続ける状況」を示すことにある。 これは2段階で構成され、2つの補題で示されている。補題1はある初期条件が存在することを示す。この初期条件が補題2で援用される。その後、2つの補題は一体になる。

補題1

（これは論文中の補題2である）

補題1の要点は、決定に至るまでの道筋があらかじめ定められていない初期構成があり、しかし、実際には個々のステップのシーケンスの結果として到達され、しかも障害は何も発生しない、ということにある。たとえば、2つのプロセッサがあり、それぞれの初期値が '0' と '1' である初期設定を考える。FLPが示したのは、この構成からの帰結として何が決定されるかは、プロセッサの初期値が何かということだけでなく、メッセージが受信される順序、そしてプロセッサが故障したかどうかに依存するということだ。これは、非同期システムモデルに固有の非決定性に起因する。

この方法はとてもきれいだ。背理法で考える。否定が真、つまり、すべての初期状態はあらかじめ定められた実行の道筋をもつと仮定する。すると、'0' に決定される道をもつ初期構成と '1' に決定される道をもつ初期構成が存在しなければならない。あらゆる結末が可能でなければならない、というは正当だ。それぞれの構成は、プロセッサにおける初期値の集合によって一意に決定される。2つの構成を隣り合わせにし、ある1つの値だけが異なるように連鎖(chain)を配置して、これらの値（プロセッサにおける初期値?）を並べ替えることができる。このとき、隣接する2つの構成を比べたとき、1つのプロセッサの開始値だけが異なるようにする。

この連鎖のある点において、'0'に決定する初期構成は '1'に決定する初期構成と隣接しなければならない。隣接するから、初期値は1つだけ異なっている必要がある。'0'-決定の構成をC_0、'1'-決定の構成をC_1で表す。プロセッサの初期値は、両方のpで異なる。ここで仮にpが最初から故障していたとしても、C_0からの実行過程で'0'を決定するものが存在しなければならない。そのためpはメッセージの送信も受信も一切行わない。その初期値は他のプロセッサからは観測されない。その中の1個は、最終的に'0'に決定しなければならない。

この実行過程はC_1からも作ることができる。このことはきわめて重要である。C_0とC_1の構成は、pでの値を除いてまったく同じである。pは故障しているので、これは実行過程に対して何の影響もない。C_0が選ばれるステップのシーケンスは、C_1も取ることができる。しかし、まったく同じステップのシーケンスを取ると、最終的な決定は両方の構成で同じにならなければならない。これは、コンセンサスアルゴリズムの結果がC_0とC_1の初期構成だけによってあらかじめ定まり、両方の構成は異なる決定をするという想定と矛盾する。そのため、これらの構成のどちらか（あるいは両方の可能性もあるが）は、'0'あるいは'1'を決定する決定する可能性があり、最終結果は故障とメッセージ配送のパターンに依存する。

どちらかの決定値に帰結する構成を2値(bivalent)と呼ぶことにする。 どちらか1つの値しか結果しない構成を、0の場合0-値、1の場合1-値とする。

補題2

（論文では補題3）

補題2は証明の大部分を構成する（このことは最初に論文を読んだときにはわからないかもしれない）。補題2で主張されているのは、プロトコルが2値の構成から開始され、その構成に適用可能なメッセージeが存在する場合、eが最後に適用されるメッセージのシーケンスを辿ることで到達できる構成の集合には、2値の構成が含まれるということである。

より直感的な言い方をすると、あるメッセージをどれだけでも好きなだけ遅延させると、メッセージを受信しても2値の状態で終わってしまう、そのような構成が存在するということだ。これは証明全体にとって非常に重要だ。 2値の構成から別の2値の構成に通じる道があることは保証されている（「2値」を「非決定」と読めば、その意味は明確だ）。このことは了解済みだろう。無限ループになる可能性をもたらすのに十分な時間、メッセージを遅延させることで、そのプロトコルはいつまでたっても未決定であり続ける。

補題2の証明は背理法を使う。いくつかの用語を定義しておく必要がある。2値の構成をCで示す。Cに適用できるイベントをe=(p,m)とする。eを適用せずにCから到達可能な構成の集合を集合Cとする。集合Cにeを適用した結果えられる構成の集合を集合Dとする。

Dは2値の構成を含まないと仮定すると矛盾することを証明する。

まず、集合Dが2値の構成を含む場合、0-値と1-値の両方の構成が集合Dに含まれることを示す。E_0とE_1は、i-値の構成（E_0は0-値、E_1は1-値）であり、集合Cから到達可能とする。 Cは2値なのでE_0とE_1の両方とも存在する。E_0が集合Cに含まれる場合（つまりeを受信していない）、E_0でeを受信した結果をF_0とする。この場合、F_0は集合Dに含まれる構成であり、E_0から到達可能である（つまり、eを受信した時点ではF_0より以前にE_0の構成がある）。

図2.1: 集合Dが2値構成を含まない場合、0-値と1-値の両方の構成を集合Dは含んでいなければならない

混乱しそうな定義だが、概念はいたってシンプル。E_0に至る実行過程でeを受信したかどうかに応じて集合Dに2つのF_0を固定する。F_0の前にeを受信した場合とF_0の後にeを受信した場合がある。

ここでF_0は0-値でなければならないことがわかる。F_0がE_0の前にある場合、F_0は0-値でなければならない。なぜなら、仮定により、F_0は2値にできないからであり、もしF_0が1-値だとすると、プロトコルはF_0とE_0の間で「決定を覆した」ことになる。これはi-値の定義に矛盾する。

同様にして、E_0の後にF_0が来る場合も0-値でなければならない。従って、集合Dは0-値の状態を含む。

一方、E_1に対してF_1を定義し、集合Dは1-値の構成を含むことを証明することもできる。以上より、集合Dが2値の構成を含まないとすると、集合Dは0-値の構成と1-値の構成の両方を含んでいなければならない。

この事実を使って、補題の証明の残りを組み立てる。補題1の証明で使った「チェーン」の概念と同様に、集合CにはC_0とC_1の両方の構成がなければならない。ここでC_1はC_0でメッセージe'を受信した結果である。eを適用してC_iにすると、i-値の構成が得られる。これらの構成をD_0とD_1と呼ぶことにする。

C_0とC_1は、1個のメッセージ配信で分離されているので「隣接」していると呼ぶ。ここで両者を分離するメッセージ e'=(p',m')を考える。e'の宛先の2つの候補としてp'を想定する。

図2.2: D_1より前にある2つの状態があり、それらが宛先プロセスが異なる（複数の）メッセージによって分離されている場合、D_0は2値でなければならない

1. p' != pの場合 このとき、C_0とC_1を分離するメッセージは、e以外のプロセッサが宛先である。このとき、D_0でe'が受信され、D_1に至る。メッセージの集合ごとに宛先が異なる場合、どんな順序で受信しても同じ構成に至る。なぜなら、どのプロセッサもイベントを同じ順序で受け取るからである。ただし、回数は異なる。（論文ではスケジュールの可換性と呼ばれている）。しかし、D_0は0-値であり、D_1は1-値である。従ってD_0からD_1には到達できない。これもまたプロトコルが決定を覆したことを意味する。これは矛盾である。

図2.3: Dが1値構成だけしか含まない場合であり、かつ、D_1より前にある二つのメッセージの宛先が同じホストである場合、C_0から出発する決定実行過程は存在しない

2. p' = p の場合 C_0から開始される有限の決定実行過程を考える。C_0はeを受信した結果0-値の構成になる。このときpはまったく進行しないとする（pが故障の可能性を考慮するために、この実行過程は存在しなければならない）。 この決定実行過程の最終結果として構成Aを定義する。これと同じ決定実行過程はD_0とD_1にも適用できる。その結果、E_0とE_1という2つの新しい構成が得られる。ここでスケジュールの可換性を適用すると、Aでeを受信してE_0にする（同じメッセージ集合で、配送の順序が異なる）ことも、Aでe'に続いてeを受信してE_1にすることもできる。（eとe'はどちらも受信可能であることを思い出せ。決定実行過程でpはまったく何も進行していないからである。）しかし、これはAが2値であることを意味し、Aへの実行過程は決定過程なので、矛盾である。

以上より、Dは2値の配置を含んでいなければならない。

ひとつにまとめる

証明の最後の一歩。決定に至るどんな実行過程であっても、非決定が無限に続く実行過程が構築できてしまう抜け道があることを示す。これは、ひたすら決定を行うことを避けるようにして、実行の部分過程をつなぎ合わせて（1値の構成に入るようにする？）ことで実現できる。

2値の初期構成C_0から開始してみよう（補題1の結論から C_0 の存在は明らか）。この実行過程を正当化するために、システムのプロセッサをキューに配置して、キューの順番に従ってメッセージを受信するようにする。受信が終わったプロセスはキューの末尾に移動する。このため、すべてのメッセージが最終的に配信される。

キューの先頭にあるプロセッサに届く最初のメッセージを e=(p,m)とする。メッセージはnullでありえる。次に補題2により、C_0からC_1に到達可能である（C_1は2値の構成）。このときC_1の直前で起きるイベントがeであり、メッセージが受信される。同様にして、C_1からC_2に到達可能である（C_2はもうひとつの2値の構成）。これが果てしなく続く。この実行過程は正当であるが、けして決定に至らない。そのため、このプロトコルは完全に正しいとは断定できない。

結論

ふー、お疲れさま。難しい技術的な証明をかきわけてきた。証明の核心部分は2つの補題にある。第1の補題は、コンセンサスの結果が未決定になるには、システムの初期構成がなされている必要があることを示した。ネットワークの状態を問い合わせ、大規模な参照テーブルを構築するだけのプロトコルでは不可能なのだ。なぜなら、障害あるいはメッセージの遅延によって、その計画は排除されることが保証されている。これは、障害の可能性が重要な補題である。もし障害がなければ、ネットワークの状態だけでコンセンサスを決定できただろう（もし障害がなければ、メッセージの遅延は、障害ではなく遅延であると認識できるからだ）。

補題2が示すのは、もし2値構成から開始すると、保留中のメッセージを遅らせることによって、別の2値構成に常に到達可能であるということだ。最終的にすべてのメッセージが配信されても​​、永遠に2値構成が続く可能性がある。そのため、1値の状態に到達可能であることを保証するプロトコルは存在しえない。

これは実際にはどういう意味なのか？　その無限の決定不能ループに入る可能性は、任意に小さくすることができる。それは、非決定が可能であることの1つ、それが完全に保証されることです。それでも、あなたのシステムがコンセンサスの過程で無限ループに陥ってしまい、その原因が不明なときは、この可能性を考えてみることが大切だ。また、実際には、現実のシステムは必ずしも真に非同期であるとは限らない。

この論文は、分散システム理論のコミュニティで大量の後続作業を生み出した。故障検出器は、Touregらによって導入された。正確なコンセンサスが得られるように非同期モデルをどの程度強化する必要があるのか​​を特徴づけることができる。十分に長い間実行されると、事実上、非決定の確率が0になるランダム化アルゴリズムが存在する。還元(reduction)による多くの証明が公表された。これは、ある問題がコンセンサスに等価であることを示し、したがってその不可能性を示した。学術分野で多くの成功を収めていた部分同期をはじめ、FLP問題を回避するためのさまざまなシステムモデルが提唱された。

この論文は2001年にダイクストラ賞を受賞し、分散コンピューティングにおける最も影響力のある論文と評価された。マイケル・フィッシャー、ナンシー・リンチ、マイク・パターソンの3人は健在で、この分野の著名な研究者である。特にナンシー・リンチは、分散アルゴリズムの仕事のほとんどすべてに関わっている。