---
title: Paxos
url: https://doc.liz6.com/ja/distributed-systems/02-consensus-protocols/02-Paxos
locale: ja
area: distributed-systems
tags:
- distributed-systems
- consensus-protocols
date: 2026-06-30
modified: 2026-07-16
description: コンセンサス問題に対する最初の産業レベルの解決策であり、RaftやZABなどの後続プロトコルの理論的根源。Basic Paxosのprepare/promise/acceptという3フェーズのメッセージ交換は一見単純だが、単一の決定から連続するログ（Multi-Paxos）への移行に至るまで、各ステップで陥りやすい落とし穴が存在する――これがRaftが誕生した直接的な動機でもある。
---

# Paxos

> コンセンサス問題に対する最初の産業レベルの解決策であり、RaftやZABなどの後続プロトコルの理論的根源。Basic Paxosのprepare/promise/acceptという3フェーズのメッセージ交換は一見単純だが、単一の決定から連続するログ（Multi-Paxos）への移行に至るまで、各ステップで陥りやすい落とし穴が存在する――これがRaftが誕生した直接的な動機でもある。

Paxos (Leslie Lamport, 1989/1998) は、コンセンサス問題に対する最初の産業レベルの解決策であり、VR、ZAB、Raftなどの後続のコンセンサスプロトコルの理論的根源です。しかし、Lamportの元の記述はギリシャ議会の比喩を用いて書かれており、「The Part-Time Parliament」というタイトルからもわかるように、難解で理解しにくいものでした。Raftの設計動機は、「Paxosを一般的なエンジニアが理解できるようにすること」にあります。

## Basic Paxos

Paxosは**単一のコンセンサス**を解決します。複数のノードが**1つの値**について合意する方法を定義します。

### ロール

- **Proposer**: 提案を発行する（クライアントは通常、Proposerとして機能する）
- **Acceptor**: 投票を行い、acceptedな値を保存する（通常、N=2f+1個のノードで構成され、f個の障害に耐える）
- **Learner**: Acceptorsから最終的に決定された値を学習する

実際の運用では、各ノードは通常、これら3つの役割を同時に担います。

### 2フェーズプロトコル

**フェーズ1: Prepare/Promise**

```
Proposer:
  proposal number Nを選択する（以前使用したどの番号よりも大きく、かつグローバルに一意でなければならない）
  Prepare(N)をすべてのAcceptorへ送信する（過半数以上の到達が必要）

Acceptor:
  Prepare(N)を受信した場合:
    if N > 自分がこれまで見たどのPrepare番号よりも大きい:
      約束: number < N の提案はこれ以上acceptしない
      Promise(N, 以前にacceptedされた値: {N_highest, V})を返信する
    else:
      無視する（または拒否を返信する）
```

**フェーズ2: Accept/Accepted**

```
Proposer:
  過半数のPromise返信を待つ
  過半数を取得した場合:
    → Acceptを送信する準備をする
    値を選択する:
      if どのPromiseにもacceptedな値が含まれている場合:
        N_highest に対応する V を選択する（つまり、番号が最大のaccepted値） ← 重要！
      else:
        自分が望む任意の値を選択する
    Accept(N, V)をすべてのAcceptorへ送信する

Acceptor:
  Accept(N, V)を受信した場合:
    if N >= このacceptorが約束した最小のN（つまり、Nより大きいPrepareを約束していない場合）:
      accept: (N, V) を保存する
      Accepted(N)を返信する
    else:
      拒否する
```

### なぜ2フェーズなのか

フェーズ1の役割は**学習**です。ProposerはPrepare/Promiseを通じて、「すでに値が部分的にacceptされているかどうか」を知ります。もし値が存在する場合、Proposerは自分の値ではなく、その値**でなければなりません**。これにより、異なるProposerの提案が互いに上書きされるのを防ぎます。

反例：フェーズ1をスキップすると、2つのProposerが同時に異なる値を提案し、それぞれが過半数のacceptを取得する可能性があります。しかし、その過半数集合が重なり合わない場合、2つの値がともに「ロック」され、システムは永遠に収束しなくなります。

### なぜNは増分しなければならないのか

Proposer Aが N=1 で V1 を提案したが、まだ過半数のacceptを取得していないとする。その間、Proposer Bが N=2 で V2 を提案したとする。2ラウンド目のフェーズ1 Prepare(2) により、Acceptorsは N<2 の提案を受け付けないことを約束するため、Aの Accept(1,V1) は拒否される。

これにより、**最終的に1つの値のみが過半数によってacceptされる**ことが保証される。

## Multi-Paxos

Basic Paxosは単一のコンセンサスを解決する。複数回の連続するコンセンサス（例えば、レプリケートログの各エントリ）は、Multi-Paxosとして扱われる。

### 最適化：安定したリーダーの選出

各エントリに対して完全なPrepare + Acceptの2フェーズを行うと、エントリあたり2 RTT（往復時間）かかる。Multi-Paxosでは、安定したリーダーを選出することで、そのリーダーはフェーズ1をスキップできる。なぜなら、リーダーである限り、他のProposerが競合しないからである。

```
Leaderが最初に選出されたとき: フェーズ1 Prepare/Promise（リーダーの身分と、最も高いacceptedなNを確定）
その後、すべてのエントリ: 直接フェーズ2 Accept → エントリあたり1 RTT
新しいProposerがリーダーになりたい場合: フェーズ1 Prepareを送信し、過半数を取得 → 新しいリーダーになる
```

## Paxos vs Raft

Paxosは中核的なコンセンサスメカニズムを定義しているが、以下は定義していない：
- リーダー選出アルゴリズム（「区別されたProposerを1人選ぶ」と述べているのみ）
- ログ圧縮/スナップショットのメカニズム
- メンバーシップ変更プロトコル

このため、各Paxos実装（Google Chubby、Amazon DynamoDB、Microsoft Azure Storageなど）は、これらの部分を独自に再発明せざるを得ず、実装の複雑さがRaftよりも高くなってしまう。

## 参考

- **論文**: "The Part-Time Parliament" (Lamport, 1998)
- **論文**: "Paxos Made Simple" (Lamport, 2001) — より読みやすいバージョン
- **論文**: "Paxos Made Live — An Engineering Perspective" (Google Chubbyチーム, 2007)

*キーワード: Paxos, Basic Paxos, Multi-Paxos, Prepare/Promise, Accept/Accepted, proposal number, distinguished proposer*