合意と協調
合意と協調は、メッセージによってのみ通信する独立したプロセスが、遅延や障害にもかかわらず、共通の価値や行動について合意する方法を扱います。
PaperMindでテーマを探す近日公開Find papers & topics
Tools & resources
Learn & explore
動画近日公開
Definition
合意とは、それぞれが値を提案する一連のプロセスが、単一の共通の値について決定することであり、その決定は有効であり、すべての正しいプロセスが合意し、一部のプロセスが故障した場合でも、すべての正しいプロセスが最終的に決定するという問題です。
Scope
この分野は、合意問題とその派生（合意、アトミックブロードキャスト、妥当性、終了）、決定論的非同期合意に対するFLP不可能性の基礎的結果、PaxosやRaftなどの実用的な合意プロトコル、ビザンチン耐障害性合意、および相互排除とリーダー選出という古典的な協調問題をカバーしています。これは、耐障害性分散コンピューティングの理論的および実践的な核となるものです。
Sub-topics
Core questions
- どのようなタイミングと障害モデルの下で合意は解決可能であり、いつそれが証明上不可能となるのか？
- 実用的なプロトコルは、安全性を維持しながらFLP不可能性をどのように回避しているのか？
- クラッシュ障害とビザンチン障害に耐えるためには、どの程度のレプリケーションが必要か？
- プロセスは共有リソースへのアクセスをどのように調整し、または信頼できるリーダーをどのように選出できるのか？
Key theories
- FLP不可能性
- 完全に非同期なシステムでは、単一のプロセスがクラッシュする可能性があっても、決定論的なプロトコルは合意を保証できません。なぜなら、遅いプロセスと故障したプロセスを区別できないためです。この結果は、部分同期、ランダム化、および障害検出器の動機付けとなります。
- クォーラムベースの合意
- Paxosのようなプロトコルは、提案を受け入れるために重複する多数派（クォーラム）を要求することで合意を達成します。これにより、任意の2つの決定が正しいプロセスで交差し、ラウンドやリーダーの変更を通じて一貫性が保たれます。
- ビザンチン合意の限界
- 最大f個のプロセスが任意に振る舞う可能性がある場合に合意に達するためには、古典的な同期設定では少なくとも3f+1個のプロセスが必要であり、これはすべてのビザンチン耐障害性システムの設計を形作る厳密な限界です。
Clinical relevance
合意は信頼性の高いインフラストラクチャのバックボーンです。協調サービス、レプリケートされたデータベース、分散ロック、およびブロックチェーンはすべて、レプリカの一貫性を保つために合意プロトコルを実行しており、この分野は現代のクラウドシステムの耐久性と可用性の保証に直接的に責任を負っています。
History
1982年のビザンチン将軍問題に関する論文と1985年のFLP不可能性の結果は、合意の限界を明確にしました。ランポートのPaxos（1989年に回覧され、1998年に発表）は実用的な非同期安全プロトコルを提供し、その後のビザンチン耐障害性に関する研究とRaftは、合意を悪意のある障害に対して堅牢にし、実装者にとってアクセスしやすいものにしました。
Debates
- FLP不可能性は、合意を実際に達成不可能にするのか？
- FLPは、完全に非同期なモデルにおいて常に安全かつ活性である決定論的プロトコルを排除しますが、実用的なシステムは、最終的な同期を仮定するか、ランダム化を使用することでこれを回避し、安全性を無条件に保ち、ネットワークが適切に動作する限り活性を達成します。
Key figures
- Leslie Lamport
- Nancy Lynch
- Michael Fischer
- Michael Paterson
- Barbara Liskov
Related topics
Seminal works
- fischer1985
- lamport1998
- lamport1982byz
Frequently asked questions
- なぜ合意は分散システムにおいて最も困難な問題と見なされるのですか？
- アトミックブロードキャスト、レプリケートされたステートマシン、分散ロックなど、他の多くの協調タスクが合意に帰着するためです。また、合意自体は、非同期クラッシュ障害モデルにおいて決定論的に解決することが証明上不可能であるため、いかなる解決策も慎重なタイミングまたはランダム性の仮定を置く必要があります。
- 合意はレプリケートされたデータベースとどのように関連していますか？
- レプリケートされたデータベースは、操作の順序について合意することでレプリカの一貫性を保ちます。これはまさに一連の合意決定です。このため、分散キーバリューストアのようなシステムは、その核に合意プロトコルを組み込んでいます。