← 分散システム 一覧

🎓 レベル：発展　|　重要度：A（必須）

📎 前提：合意問題とFLP不可能性　|　関連：Raft・クォーラム（R+W>N）

要点（BLUF）

• Paxos（Lamport, 1998）は、クラッシュ故障下で安全に1つの値を合意する古典アルゴリズム。過半数（クォーラム）の重なりを使い、矛盾した決定を構造的に防ぐ。
• 役割は3つ：Proposer（提案）・Acceptor（投票・記憶）・Learner（結果学習）。提案には単調増加する一意な提案番号を付ける。
• 2フェーズ：Prepare（番号nで過半数に予約し、既存の受理値を回収）→ Accept（回収した値 or 自分の値を、過半数に受理させる）。安全性は無条件、活性はFLPゆえ条件付き（競合で停滞しうる）。

問題設定 ── 故障の中で1つに決める

合意問題とFLP不可能性 の合意を、クラッシュ故障下で安全に実装したい。鍵は「どの2つの過半数も必ず1つ以上のノードを共有する」という事実（クォーラム（R+W>N） の重なり）。この共有ノードが「記憶の橋渡し」をして、別々の提案が別々の値を確定するのを防ぎます。

アルゴリズム ── Prepare と Accept

sequenceDiagram
    participant PR as Proposer
    participant A1 as Acceptor1
    participant A2 as Acceptor2
    participant A3 as Acceptor3
    Note over PR,A3: フェーズ1: Prepare(n)
    PR->>A1: prepare(n)
    PR->>A2: prepare(n)
    A1-->>PR: promise(n, 既受理値あれば返す)
    A2-->>PR: promise(n, 既受理値あれば返す)
    Note over PR,A3: フェーズ2: Accept(n, v)
    PR->>A1: accept(n, v)
    PR->>A2: accept(n, v)
    A1-->>PR: accepted(n, v)
    A2-->>PR: accepted(n, v)
    Note over PR,A3: 過半数がacceptedなら v が確定

• フェーズ1（Prepare）：Proposerが番号 n で過半数に prepare。Acceptorは「n より小さい提案は今後拒否する」と約束（promise）し、既に受理した値があればそれを返す。
• フェーズ2（Accept）：promiseで集めた中に既受理値があれば、最大番号のその値を採用（無ければ自分の値）。それを accept(n, v) として過半数に受理させる。過半数が受理したら v が確定。

正しさの観点 ── なぜ矛盾しないか

安全性の核心は2つの規則の合わせ技：

1. 過半数の重なり：値 v が確定した＝過半数が v を受理した。別の提案 n’ も過半数に触れる以上、v を受理したノードに必ず当たる。
2. 値の引き継ぎ：そのノードは promise で v を報告するので、後続のProposerは自分の値でなく v を選ばざるを得ない。

この重なりが「一度確定した値は、以後どの提案も上書きできない」を保証します。提案番号 n の単調性が「どの値を引き継ぐか」を一意に決め、二重確定を防ぎます。活性は——競合するProposerが番号を上げ合うと永遠にAcceptに到達しないライブロックがありうる（FLPの現れ）。リーダーを1人に絞る（Multi-Paxos／Raft）ことで回避します。

他手法との比較 ── Paxos vs Raft

PaxosとRaftは本質的に同じ安全性原理（過半数の重なり）。違いは説明と実装のしやすさで、現場の新規実装はRaftが多数派です。

なぜ難しいか（直観）

Paxosの難しさは「なぜこれで正しいのか」が見えにくい点。prepare→acceptの各ステップは単純だが、「既受理値を最大番号で引き継ぐ」規則が安全性の全荷重を担っており、ここを飛ばすと途端に二重確定が起きる。Lamportの論文が寓話（議会）で書かれたことも難解さの一因で、その反動がRaftの「理解しやすさ」設計です。

⚠️ よくある誤解・落とし穴

• 「Paxosは合意できないことがある（FLP）から欠陥」→ 安全性は常に守る。停滞（活性）はリーダー固定で実用上回避。
• 「1回のPaxosで何個も値を決められる」→ 素のPaxosは1つの値用（single-decree）。連続した値はMulti-Paxos。
• 「過半数でなく多数決の話」→ 多数決ではなく任意の2クォーラムが交わることが本質。だから過半数（N/2+1）。
• 「promiseで既受理値を返さなくてよい」→ それを省くと確定済みの値を上書きでき、安全性が崩壊する。

対応ラボ

なし（概念回）。同じ安全性原理（過半数投票でリーダーを一意化）は Raft のラボで実証します。重なり条件は クォーラム（R+W>N） のラボへ。

関連

• 理解しやすい同等物が Raft
• 安全性を支える重なりは クォーラム（R+W>N）
• 不可能性の背景は 合意問題とFLP不可能性

← 第5章 合意 目次