リーダー選出（Bully・Ring）

🎓 レベル：標準　|　重要度：B（重要）

📎 前提：合意問題とFLP不可能性　|　関連：Raft・ゴシップ・反エントロピー・故障検出（SWIM）

要点（BLUF）

リーダー選出は「故障後、生き残りから唯一の調整役を1人選ぶ」調整プリミティブ。レプリケーションのプライマリ・2PCのコーディネータ・ジョブの単一実行などに必須。
古典アルゴリズム2つ：Bully（最大IDの生存ノードが勝つ）とRing（リング状にトークンを回し最大IDを集約）。どちらも一意な全順序IDを使い、選ばれるノードを一意化して安全性を得る。
ただし素朴な選出はスプリットブレイン（分断で各側がリーダーを立てる）に弱い。**過半数を要求する合意ベース選出（Raft, Raft）**がこれを防ぐ。

問題設定 ── 1人だけ選びたい

レプリケーション方式（同期／非同期・リーダー／リーダーレス）のプライマリが落ちたら、残りから新プライマリを1人選ぶ。条件は「全員が同じ1人に同意し（合意性）、それは生存ノードである」。合意問題（合意問題とFLP不可能性）の特殊形です。

アルゴリズム ── Bully（いじめっ子）

各ノードは一意なID。より大きいIDが偉いというルールで、最大の生存IDがリーダーになります。

sequenceDiagram
    participant N2 as ノード2
    participant N3 as ノード3
    participant N4 as ノード4
    Note over N2: リーダー不在を検知
    N2->>N3: ELECTION
    N2->>N4: ELECTION
    N3-->>N2: OK(私が引き継ぐ)
    N4-->>N2: OK(私が引き継ぐ)
    Note over N4: 自分より上はいない -> リーダー確定
    N4->>N2: COORDINATOR(私がリーダー)
    N4->>N3: COORDINATOR

リーダー不在を検知したノードは、自分より大きいID全員に ELECTION を送る。
OK が1つでも返れば自分は降りる（より大きい者に任せる）。
OK が1つも返らなければ自分が最大＝リーダー確定、全員に COORDINATOR を通知。

アルゴリズム ── Ring（リング）

ノードを論理リング状に並べ、ELECTIONメッセージに自分のIDを足しながら隣へ回す。一周して戻ると、メッセージ内の最大IDがリーダー。全員に同じ最大IDが伝わるので合意できます。Bullyより送信メッセージが規則的（O(N)）で、トポロジが安定した環境向き。

具体例 ── 最大の生存IDに収束（実機）

ラボ 05-05_bully_election.py。5ノード（ID=1..5）で最大の5がダウン、ID=2が選出を開始：

== Bully リーダー選出 ==
生存ノード: [1, 2, 3, 4]  (ID=5 はダウン)
  node 2 -> ELECTION to [3, 4]
  node 4 -> ELECTION to (なし)
  node 4 がリーダー確定 -> COORDINATOR を全生存ノードへ

確定したリーダー: 4  (期待: 生存ノードの最大ID=4)
総送信メッセージ数: 5
安全性: 最大IDは一意 -> リーダーは1人だけ確定

ID=5 復帰後に再選挙 -> リーダー: 5  (期待: 5。最大IDが'いじめて'勝つ=Bully)

ID=2が開始しても、上位の4に引き継がれ、生存最大ID=4がリーダーに収束。ID=5が復帰すると再選挙で5が4を「いじめて」リーダーを奪う——これがBully（いじめっ子）の名の由来です。

正しさの観点 ── 安全性と、その限界

安全性（一意性）：IDは全順序で一意なので「最大」は1つに定まる。全員が通信できればリーダーは1人に収束。
活性：生存ノードがあれば有限ステップで最大IDがリーダーになる。
限界＝スプリットブレイン：ネットワーク分断が起きると、各側で「自分の見える範囲の最大」が別々にリーダーを名乗る。過半数の概念が無いため二重リーダーを防げない。

flowchart LR
    subgraph 左側
    A["1,2,3 -> 最大3がリーダー"]
    end
    subgraph 右側
    B["4 -> 最大4がリーダー"]
    end
    A -.->|"分断で互いに見えない"| B

他手法との比較 ── 素朴な選出 vs 合意ベース

観点	Bully / Ring	Raft の選出（Raft）
当選条件	最大ID	過半数の票
スプリットブレイン	起きうる	起きない（少数派は当選不可）
用途	分断が無い前提・教育的	本番の強一貫システム

過半数を要求すると、分断の少数派側は決してリーダーになれない。これがBully/Ringとの決定的な差で、本番では合意ベースが標準です。Bully/Ringは「選出の直観」を掴む土台として価値があります。

なぜ分散だと難しいか（直観）

「1人選ぶ」は、全員が同じ相手を選び、かつ二重に選ばないことが要る。故障検知が不確実（ゴシップ・反エントロピー・故障検出（SWIM））なので「リーダーが落ちた」と誤検知すると不要な選挙が起き、分断時には二重リーダーになる。過半数という重しが無いと安全に1人へ絞れない、というのが教訓です。

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

「Bullyならスプリットブレインしない」→ する。過半数を要求しない選出は分断で二重リーダー。
「IDが大きい＝高性能」→ IDは単なるタイブレーク。性能で選びたいなら別の優先度関数を全順序化する。
「リーダーが落ちたらすぐ選挙」→ 誤検知での頻繁な再選挙はフラッピングを招く。適切なタイムアウトとフェンシング（旧リーダーの締め出し）が要る。
「選出できれば一貫性も保証」→ 選出は入口。確定したデータの保全は合意・ログ複製（Raft）が担う。

対応ラボ

distributed-systems-study/labs/05-05_bully_election.py（生存最大ID=4への収束と、ID=5復帰後のプリエンプションを確認済み）。