## 定義 FLPの不可能性(FLP Impossibility Problem)とは、Fisher・Lynch・Patersonの3人が論文[FISCHER85]で示した、分散合意アルゴリズムに関する著名な不可能性結果である(FLPは著者3人の姓の頭文字に由来する)。開始時に初期値を割り当てられた複数のプロセスが新しい値への同意を試みる合意の方式において、処理が完全に非同期であること(プロセス間に共有された時間の概念がなく、アルゴリズムがタイムアウトに基づけない)を前提とすると、以下の3特性を保証しつつ制限された時間内に合意を保証できる決定論的アルゴリズムは存在しないことを証明する。 - **同意性**: プロトコルが到達する決定は全プロセスで一致していなければならない。 - **妥当性**: 同意された値はいずれかの参加者によって提案されたものでなければならない(システムが値を自明に「思いつく」ことは許されない)。 - **終了性**: 決定状態に到達していないプロセスがなくなった場合にのみ合意は終了する。 完全に非同期な合意アルゴリズムは、単一のリモートプロセスの予告なしのクラッシュにさえ耐えられない。プロセスがアルゴリズムステップを完了するまでの時間の上限を考慮しない場合、プロセスの障害を確実に検出できず、合意に到達するための決定論的アルゴリズムは存在しない。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 8 基本事項の紹介と概要]] §8.5) ## FLPの不可能性が意味しないこと FLPの不可能性は「合意に達することは不可能だ」ということを意味しているわけではない。単に、非同期システムでは制限された時間内に合意へ到達することが常に可能とは限らないことを意味しているにすぎない。実際のシステムは少なくともある程度の同期性を示しており、この問題へのソリューションには、非同期モデルより洗練されたシステムモデル(部分同期モデルなど)が必要になる。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 8 基本事項の紹介と概要]] §8.5) ## 横断的知見 - 『詳説 データベース』第8章が唯一のソースであり、横断的知見はまだ蓄積されていない。[[分散コンセンサス]]・[[分散合意プロトコル]]が扱うRaft・Paxos等の実用アルゴリズムは、いずれもFLPの不可能性を回避するために部分同期モデルやランダム化タイムアウトを用いる設計選択をしている。この対応関係を、Raft/Paxos論文自体や関連ソースが増え次第、具体的に突き合わせる必要がある。 - **同じ書籍の第14章は、第8章が示したFLPの不可能性を回避する3つの具体的な戦略を、Paxos・Raft・PBFTという別々の実用アルゴリズムから跡づける**: [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]]冒頭は「9章では、障害検出の精度と、素早く障害を検出できることとの間にはトレードオフが存在することを議論した」「合意アルゴリズムは非同期モデルを前提とし安全性を保証するが、外部の障害検出機能は他のプロセスの活性について保証する情報を提供できる」と述べ、第9章の障害検出機能をFLP回避の一手段として明示的に位置づけ直す。さらに14章はRaftのランダム化タイムアウト(§14.4.2: 票割れをランダムなタイマーで軽減する)とPBFTの「弱い同期性(ネットワークが正常に動作することが期待される)」という前提(§14.5)を並べて示しており、(1)障害検出機能による活性情報の補強、(2)ランダム化タイムアウトによる状態空間の縮小、(3)部分同期(弱い同期性)の仮定という3つの回避戦略が、単一の書籍内で3つの異なる合意アルゴリズムに具体化される形で確認できる。同一書籍の別章は独立ソース扱いでよいという規約に従い、8章(定理そのもの)と14章(具体的回避策)を突き合わせた。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 8 基本事項の紹介と概要]] §8.5, [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] 冒頭, §14.4.2, §14.5) ## 未解決の問い - FLPの不可能性(有界時間内の決定論的合意が不可能)と、[[2人の将軍の問題]](非同期・リンク障害下での2者間合意の不可能性)は、いずれも非同期通信下での合意の限界を示すが、前者はN者・決定論的アルゴリズムの一般的な不可能性証明であり、後者は2者間の具体的な思考実験である。両者の証明の関係(FLPは2人の将軍の問題の一般化と言えるか)は本章では明示されていない。整理する価値があるか。 - [[システムモデルと安全性・活性]]が扱う安全性・活性の区別に照らすと、FLPの不可能性はどちらの性質(あるいは両方)に関する不可能性結果と言えるか。合意アルゴリズムの終了性(活性)が問題になっているとすれば、安全性は非同期モデルでも達成可能なのか。 - 14章が示す3つの回避戦略(障害検出機能・ランダム化タイムアウト・部分同期仮定)のうち、Multi-Paxosのリーダーリースはどれに分類されるべきか。リースはクロックドリフトへの依存を伴う点で部分同期仮定の一種と見えるが、14章はこれを「正確性ではなく性能のための最適化」と位置づけており、FLP回避策として捉えるべきかどうかは明示されていない。 ## 関連 - ソース: [[@2021__OReillyJapan__詳説 データベース - Chapter 8 基本事項の紹介と概要]] / [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] - 概念: [[分散コンセンサス]] / [[分散合意プロトコル]] / [[システムモデルと安全性・活性]] / [[2人の将軍の問題]] ## 出典 - Alex Petrov, *詳説 データベース*, オライリー・ジャパン, 2021, 8章, §8.5. - Alex Petrov, *詳説 データベース*, オライリー・ジャパン, 2021, 14章(冒頭, §14.4.2, §14.5: FLP回避の3戦略の具体化). - Fischer, Michael J., Nancy A. Lynch, and Michael S. Paterson. 1985. "Impossibility of Distributed Consensus with One Faulty Process." [FISCHER85](原典。本章での参照元)