分散式系統靠一個 leader 來降低同步成本、減少訊息往返，並在廣播中提供全序。這一頁講的是獨立於共識的經典選舉算法——Bully、Ring、Invitation 這些骨架與取捨。真實系統多半把選舉摺進共識協議（如 Raft），但理解這些原型，才看得懂「光靠選舉為什麼保證不了唯一 leader」。
🧠 Intuition
TIP
一句話：這些算法都在回答「舊 leader 沒了，誰接班？」大多用 rank（排名） 決勝——活著的最高 rank 當選。難的不是選出來，而是選得穩（別把還健康的 leader 換掉）又唯一（別選出兩個）。
- 為什麼要 leader：由單一程序驅動協調，比點對點互相同步省訊息，還能在廣播中實現全序。程序通常是對等的，任何節點都能當 leader，直到當機為止。
- 兩個目標：liveness（大多數時間有 leader，選舉最終會結束）與 safety（任何時刻最多一個 leader）。這章討論的算法多半只顧 liveness，會違反 safety。
- 和分散式鎖不同：選舉偏好穩定的 leader、且所有人都要知道 leader 是誰；鎖則相反——不能偏好特定程序（否則 starvation），也不需要別人知道誰持有。
- 選舉即共識：能對「leader 身份」達成共識，就能對任何事達成共識；要真正避免 split brain，得靠叢集多數票。
⚖️ Tradeoffs
Bully Algorithm — 最高 rank 者霸凌上位
- 發現無 leader 或前任無回應時，程序向所有更高 rank 者發 Election；沒人回應就自任 leader，並通知所有更低 rank 者。
- 又稱 monarchial election：最高 rank 的「繼承人」在前任消失後登基。
- 風險：不穩定的高 rank 節點會讓系統卡在永久重選——它自薦、當機、再贏、再當機。可用 host quality metrics 納入選舉來緩解。
- 網路分區時各子集各選各的 leader，違反 safety（split brain）。
Next-In-Line Failover — 用備選清單省一輪選舉
- Bully 的改良：當選 leader 事先公布一份 failover 節點清單。
- 偵測到故障時，直接聯繫清單中 rank 最高的備選；若它存活就直接接班，跳過完整選舉。
- 若偵測者自己就是清單最高者，可立即通知其他人。
- 效果：只要下一順位存活，重選步驟大幅減少——本質是拿「預先協調」換「更快 failover」。
Candidate/Ordinary — 分角色降訊息量
- 把節點切成 Candidate（有資格當 leader）與 Ordinary（只發起選舉、通知結果），縮小競爭範圍。
- Ordinary 偵測到故障後只聯繫 Candidate，選出最高 rank 的存活者。
- 為避免多人同時開選，引入 tiebreaker δ：高優先權節點 δ 較低（較早發起）、低優先權較晚，且 δ 通常大於一次 round-trip。
- 取捨：用「延遲錯開」換「不撞車」，代價是最壞情況下選舉起步較慢。
Invitation Algorithm — 用合併取代競爭
- 不比排名，改用邀請：每個程序起初都是自己單人群組的 leader，互相邀請加入。
- 兩個 leader 相遇就合併群組，由較大群組的 leader 勝出——只需通知較小群組的成員，省訊息。
- 明確允許多個 leader 同時存在（每群組一個），靠合併而非重選來收斂。
- 取捨：免去從頭選舉的開銷，但同樣可能長期並存多個 leader。
Ring Algorithm — 沿環傳一圈取 max
- 節點排成環、各知前驅後繼。偵測到故障就沿環轉發 Election，繞不到的節點跳過。
- 訊息每經一站就把自己 ID 加入存活集合；繞回發起者後，選集合中 rank 最高者，再發一輪散布結果。
- 空間優化：因 max 有交換律，可只傳「目前已知最高 ID」而非整個集合。
- 環被分區時各段各選各的 leader，同樣不滿足 safety。
穩定性與 split-brain — 選舉救不了唯一性
- 穩定選舉要結合故障偵測（回合制 + timeout），保證 leader 只要不當機且可達就不被換掉——別把健康的 leader 選掉。
- 本章所有算法都易出 split brain：兩個 leader 在獨立子網並存卻互不知。要避免，必須拿到叢集多數票。
- 實務中的共識協議把選舉摺進協議並容忍暫時多 leader：Multi-Paxos 靠收第二個 quorum 收斂，Raft 靠發現自己 term 過期而退位。
- 允許暫時多 leader 是效能優化（複製可先進行），safety 靠偵測與解決衝突補回——這正是共識比裸選舉多做的事。
🔑 Takeaways
- 經典選舉算法多用 rank 決勝，且大多只保證 liveness、會在網路分區下違反 safety。
- Bully 的兩個改良各有取向：Next-In-Line 用預先備選清單省一輪，Candidate/Ordinary 用角色劃分加 δ 錯開降訊息與撞車。
- Invitation 與 Ring 走不同路（合併群組、環上取 max），但都可能產生多個 leader。
- 光靠選舉不保證唯一 leader：真正排除 split-brain 要靠多數票 / fencing——所以真實系統把選舉摺進共識協議，而非單用這些算法。
No notes yet — jot your takeaways or Q&A here.