合意アルゴリズムの系統と派生

系統図として捉える理由

合意（コンセンサス）アルゴリズムは「Paxosは難しい」「RaftはPaxosの簡単版」といった断片的な印象で語られがちです。しかし実際には、少数の設計判断の組み合わせとして体系的に並べられます。アルゴリズムを個別に暗記するのではなく、どの前提を選び、何を捨てたかという軸で位置づけると、未知の派生（新しいブロックチェーンの合意など）も既存の座標に落とし込めます。

この記事では、まず分類の軸を定め、次にCFT系（クラッシュ故障耐性）の系統樹、最後にBFT系（ビザンチン故障耐性）の枝を、年代と分岐を明示して整理します。

分類の3軸

すべての合意アルゴリズムは、次の3つの軸で位置づけられます。

• 故障モデルが最も大きな分岐です。CFT（Crash Fault Tolerant）は、止まったノードは黙るだけで嘘はつかないと仮定します。N >= 2f+1（f個の故障に耐えるには過半数）で済みます。BFT（Byzantine Fault Tolerant）は、故障ノードが任意の偽情報を送る可能性まで含め、N >= 3f+1 を要求します。
• タイミング前提は活性の保証に効きます。安全性は前提に関わらず守るのが定石で、リーダー交代のタイムアウトなどで活性を部分同期に賭けます。
• リーダーの有無は性能特性を決めます。リーダーありは平常時に1ラウンドトリップで確定でき、現代の主流です。

CFT系の系統樹

クラッシュ故障のみを扱う実用合意は、ほぼすべてPaxosを共通祖先とする一族です。年代順に分岐を追います。

Viewstamped Replication (1988, Oki & Liskov)
        │  ※Paxosとほぼ同時期に独立発見されたSMR
Paxos (1989発表/1998出版, Lamport)  ── 単一値の合意（Single-decree）
        │
        ├─ Multi-Paxos ── コマンド列に拡張。安定リーダーで2フェーズ目を省略
        │       │
        │       ├─ Raft (2014, Ongaro & Ousterhout) ── 理解性重視で再設計
        │       └─ Zab (2008頃, ZooKeeper) ── プライマリ順序保証に特化
        │
        └─ EPaxos (2013) ── リーダーレス。依存のないコマンドは並行確定

それぞれの位置づけを整理します。

Paxosの核と「なぜ難しいか」

Single-decree Paxosは2フェーズで動きます。提案番号の単調性で安全性を担保するのが要点です。

# Paxos 基本形（1つの値を決める）
Phase 1 (Prepare):  提案者は番号 n を選び acceptor 群へ prepare(n) を送る
                    acceptor は今まで見た最大番号未満の n を拒否、以上なら
                    「これまで accept した値」を添えて約束を返す
Phase 2 (Accept):   過半数の約束を得たら、返ってきた中で最新の値（無ければ自由値）を
                    accept(n, v) として送る。過半数が accept したら v が確定

難しさの根は、誰でも提案者になれて提案が競合しうる点にあります。複数提案者が交互に番号を上げ続けると確定が進まない（ライブロック）ため、実装では事実上リーダーを1人に絞ります。これがMulti-Paxosであり、安定リーダー下ではPhase 1を一度きりにしてPhase 2だけを繰り返すことで、1往復で確定します。

RaftはMulti-Paxosの何を変えたか

Raftは新しい能力を足したのではなく、同じCFT・部分同期・リーダーありの骨格を、人が追える形に再分解しました。

Raftの「強いリーダー」原則は、ログがリーダーからフォロワへ一方向にしか流れないことを意味します。選出時に最も新しいログを持つ候補しかリーダーになれない制約（election restriction）を課すことで、確定済みエントリが失われないことを保証します。論理的にはMulti-Paxosと同じ安全性を、より検証しやすい不変条件で実現しています。

ZabとViewstamped Replicationの位置

ZabはZooKeeper専用に設計され、プライマリが発行するトランザクションの全順序ブロードキャストとクラッシュ後のリカバリを一体で扱います。Raft同様にリーダー（プライマリ）中心ですが、目的が「順序付きアトミックブロードキャスト」に寄っている点が個性です。Viewstamped Replication（VR）はPaxosとほぼ同時期にLiskovらが提案したもので、ビュー（=任期）変更によるリーダー交代という発想はRaftの直接の先祖にあたります。

BFT系の枝

ビザンチン故障——ノードが矛盾した情報を別々の相手に送るような悪意ある振る舞い——まで耐えるには、別系統が必要です。原点はPBFTです。

Byzantine Generals Problem (1982, Lamport) ── 問題の定式化
        │
PBFT (1999, Castro & Liskov) ── 部分同期で実用的なBFT・SMR
        │
        ├─ Tendermint / CometBFT (2014〜) ── ブロックごとに即時確定(finality)
        ├─ HotStuff (2018) ── 線形通信量＋リーダー回転（多くのBFTチェーンの基盤）
        └─ その他 PoSチェーンの合意層

CFT系との決定的な違いは2つです。

なぜBFTは N >= 3f+1 か

CFTでは、過半数の2つのquorumは必ず1ノード以上で重なり、その重なりが「確定済みの値」を運びます。ところがビザンチンノードは重なり部分で嘘をつけるため、過半数では足りません。f個が裏切っても、正しいノードだけで安全な多数決が成立するには、任意の2つのquorum（各サイズ 2f+1）の重なりが最低 f+1 個——すなわち正しいノードを1つ以上含む——必要です。これを満たす最小が N = 3f+1 です。

# 直観：N = 3f+1 のとき
quorum サイズ = 2f+1
2つの quorum の重なり ≧ (2f+1) + (2f+1) - N = f+1
そのうち最大 f 個が裏切り者でも、正しいノードが ≧ 1 残り、決定が運ばれる

PBFTからTendermint・HotStuffへ

PBFTは pre-prepare → prepare → commit の3フェーズで、各フェーズが全対全の照合を要し通信量が O(N^2) になります。少数ノードでは実用的ですが、参加者が増えると重くなります。

• Tendermint / CometBFT は、各ブロックを提案→pre-vote→pre-commitで処理し、確定したら覆らない即時ファイナリティを与えます。プルーフ・オブ・ステーク型チェーンの中核です。
• HotStuff は、フェーズを連鎖（パイプライン）させ、署名集約により通信量を O(N) まで下げたうえで、毎ラウンドのリーダー回転を安価にしました。多くの近代BFTチェーンがこの系譜です。

設計判断としての使い分け

系統図は、実装選択の地図でもあります。ノード同士が信頼できる閉じた環境（社内の分散DBや調整サービス）なら、CFTで十分かつ高速です。ZooKeeper（Zab）やetcd（Raft）がマイクロサービスの構成管理・リーダー選出に使われるのはこのためです。リーダーありCFTは平常時1往復で確定でき、レイテンシ予算に優しい。

一方、参加者が互いを信頼できない開かれた環境では、裏切りを前提とするBFTが要ります。コストは 3f+1 のノード数と増える通信量ですが、相互不信下で合意を成立させる対価です。なお、これらの確定順序は論理クロックが定める因果順序の上に成り立っており、合意は「全順序を1つに固定する」操作と見ることもできます。

まとめ

• 実用合意は3軸——故障モデル（CFT/BFT）・タイミング前提（同期/部分同期/非同期）・リーダー有無——で体系化できる。
• CFT系はPaxosを共通祖先とし、Multi-Paxos・Raft・Zab・Viewstamped Replicationは「安定リーダー＋過半数確定＋ビュー/任期交代」という同一骨格の方言。RaftはPaxosの再設計であって上位互換ではない。
• BFT系はPBFT（1999）が原点で、Tendermint・HotStuffへ派生。裏切りに耐えるため N >= 3f+1 と多い通信量を要する。
• 完全非同期では決定性合意は不能（FLP）なので、全系統が部分同期を前提に活性を確保する。
• 選択は環境次第。信頼できる閉域はCFTで高速に、相互不信の開域はBFTでコストを払って、と分ける。