分散合意アルゴリズム
中心的な管理者が存在しない分散システムにおいて、「現在どのノードの情報が正しいか」「次にどのデータを全体の真実として合意するか」を決定することは、論理的に極めて困難な問題です。分散合意の数学的限界と、それを解決するための代表的な協調アルゴリズムを解説します。
1. 分散合意の論理的限界：FLP不可能性定理
ネットワーク遅延やマシンの停止（クラッシュ）が発生する非同期の分散ネットワークにおいて、「すべての正常なノードが、限られたステップ数の中で必ず同じ値に合意する」という問題を完璧に解くことは可能でしょうか。
1985年にフィッシャー、リンチ、パターソンによって証明されたFLP不可能性定理（FLP Impossibility Result）は、次の冷酷な事実を証明しました。
この定理は、あらゆる分散システムが「合意の確実性」か「合意プロセスの終了保証」のどちらかを一定水準で妥協しなければならないことを意味しています。
2. 代表的な合意アルゴリズム：Raft（ラフト）
FLP不可能性による論理限界はありますが、実用のシステムを動かすためには「ほぼ確実に合意できるアルゴリズム」が必要です。古くは Paxos が用いられていましたが、極めて難解だったため、近年では理解しやすさを重視して設計されたRaft（ラフト）アルゴリズムが広く採用されています。
Raftは、システム全体の決定を下す「リーダー」を常に1台選出し、合意形成を以下の3つのサブ問題に分割して統治します。
- リーダー選挙（Leader Election）：
リーダー（現在データを受け付けるサーバー）が突然死した場合、残された他のノード（フォロワー）がハートビートのタイムアウトを検知し、自律的に立候補して過半数（クォーラム）の賛成票を集めたノードが新たなリーダーに選出されます。 - ログの同期（Log Replication）：
クライアントからの更新命令はすべてリーダーに送られます。リーダーはそれを自身のログに記録すると同時に、全フォロワーに複製要求を送信します。 - コミットの確定：
過半数のフォロワーから複製完了の肯定応答が得られた時点で、リーダーはそのログを「コミット（確定）」とし、クライアントに応答を返します。この過半数ルールにより、一部のノードがダウンしていても全体の合意を維持できます。
3. 分散システムの一貫性（CAP）シミュレータ
以下のシミュレータでは、ロードバランサと3台のサーバーノードが構築されています。 ノードの停止（稼働/停止ボタン）や、Node Cの「ネットワーク分断（通信遮断）」を切り替えながら、CPモード（一貫性重視）とAPモード（可用性重視）で、データの書き込みや読み出しがどのように処理され、ログに記録されるかを観察してみましょう。
分散システムの一貫性（CAP）シミュレータ
ロードバランサと3台のサーバーノードからなるシステムで、ノード障害やネットワーク分断が発生した際の挙動の違いをシミュレートし、CAP定理のトレードオフを視覚的に学習します。
世界中で何百万人もが同時にアクセスする巨大ECサイトでは、データベースが世界各地のデータセンターに分散されています。このとき、ユーザーが商品を「買い物かご（カート）」に入れる操作は、裏側のデータベースにどのように反映されるべきでしょうか。
- CPモード（一貫性優先）を選んだ場合: 日本のユーザーが商品をカートに入れ、同時にアメリカのバックアップデータセンターへの同期がネットワーク遅延等で一時遮断されたとします。このときCP優先システムは、両者のデータの一貫性を確認できないため、カートへの追加操作を失敗（エラー）とします。これは「買いたいのに買えない（可用性の低下）」ため、サービスとしては売上の機会損失になります。
- APモード（可用性優先）を選んだ場合: 同期が取れなくても、システムは即座に「カートへの追加成功」を応答します（可用性維持）。ただし、別のブラウザやアプリから見た際、一瞬カートが空に見えるなどの「一時的な不整合」が許容されます。ネットワークが復旧すると、結果一貫性の仕組みによってデータが同期されます。
多くの巨大ECサイト（AmazonのDynamoアーキテクチャなど）は、一貫性を一時的に犠牲にしても「カートへの追加（売上の機会）」を決して妨げないAP/結果一貫性モデルを意識的に選択しています。分散システムの設計におけるCAP/PACELCの選択は、ビジネス上のトレードオフと直結しているのです。