Leader Election

A leader election algorithm is a distributed protocol run by a set of processes $P = \{p_1, \ldots, p_n\}$, each with a unique, totally-ordered identifier, that terminates with every non-crashed process agreeing on a single elected process — the coordinator or leader. The two required correctness properties are safety (no two processes ever simultaneously believe two different processes are the leader) and liveness (the algorithm eventually terminates with a leader chosen, provided the system stabilizes long enough). Leader election typically operates under the crash-stop failure model: a process either follows the protocol correctly or stops entirely (no arbitrary/Byzantine behavior). Processes communicate via asynchronous or partially synchronous message passing, and failure detection is done via timeouts: if process $p_i$ expects a reply from $p_j$ within time $T$ and none arrives, $p_i$ assumes $p_j$ has crashed. This assumption is the crux of the entire analysis — timeouts can be wrong (a slow, live process may look crashed), and the tradeoffs of the two algorithms below stem directly from how they cope with this uncertainty. Both classical algorithms studied here assume the identifier space is known and comparable (e.g., process IDs, IP addresses, or logical ranks), that the highest surviving ID should win, and that the network, while possibly slow, eventually delivers messages between live processes (this is the "partially synchronous" or "eventually reliable" assumption). Under a fully asynchronous network with no timeout guarantee at all, no deterministic algorithm can even detect crashes reliably — a boundary result that motivates why real systems (like Raft) instead use randomized timers and majority quorums rather than committing to "the highest ID always wins."

The Bully Algorithm

The Bully algorithm (Garcia-Molina, 1982) assumes every process knows the identifiers of all other processes (though not necessarily their up/down status), and that a message from a higher-ID process always "bullies" a lower one into submission. Any process can initiate an election — typically the first process to notice the current coordinator is unresponsive. The protocol uses three message types:

• ELECTION — "I am starting an election; do you outrank me?"
• OK (ANSWER) — "Yes, I outrank you; stand down, I'll take it from here."
• COORDINATOR — "I won; I am the new leader."

``` // Run independently by every process p with identifier id(p) state: status ∈ {NORMAL, WAITING_OK, WAITING_COORD} state: coordinator = current known leader (may be unknown/dead) on TIMEOUT waiting for coordinator's heartbeat, or on p detecting coordinator failure directly: start_election() function start_election(): higher = { q ∈ P : id(q) > id(p) } if higher is empty: // p has the highest id among all known processes become_coordinator() else: send ELECTION to every q in higher status = WAITING_OK set timer T1 wait for either:

• an OK message from some higher process → status = WAITING_COORD

set timer T2 (expect a COORDINATOR msg soon)

• timer T1 expires with no OK received → become_coordinator()

on receive ELECTION from q (with id(q) < id(p)): send OK to q if status != WAITING_COORD and status != WAITING_OK: start_election() // p also starts its own election on receive OK from q: status = WAITING_COORD set/reset timer T2 // cancel plan to self-declare on timer T2 expires (no COORDINATOR message arrived after an OK): start_election() // the higher process must have also failed; retry on receive COORDINATOR from q: coordinator = q status = NORMAL function become_coordinator(): coordinator = p status = NORMAL send COORDINATOR to every process in P (except p) ```

Why the cascade terminates. Any process that notices a failure sends ELECTION only to higher-ID processes. Every process that receives an ELECTION message either (a) is itself the highest surviving process, and eventually declares itself coordinator, or (b) forwards the challenge upward by starting its own election. Because IDs are finite and totally ordered, this upward cascade can happen at most $n$ times before reaching the single largest surviving ID, which has no higher process to defer to and therefore always wins by default.

The Ring Algorithm

The Ring algorithm (Chang & Roberts, 1979) assumes processes are logically arranged in a ring, each knowing only its successor (the next process in ring order, skipping crashed ones). No global knowledge of all IDs is required — this is its main structural advantage over Bully. ``` // Every process p has a successor pointer succ(p), the next live process in the ring state: participant = false // has p already forwarded an election this round? function start_election(): participant = true send ELECTION(id(p)) to succ(p) on receive ELECTION(j) from predecessor: if j > id(p): participant = true forward ELECTION(j) to succ(p) // pass the larger id onward else if j < id(p): if participant == false: participant = true forward ELECTION(id(p)) to succ(p) // replace with own (larger) id // else: already participated this round, message with a smaller id is dropped else: // j == id(p): the message has completed a full lap // p's own id survived the whole ring — p is the winner participant = false send COORDINATOR(id(p)) to succ(p) on receive COORDINATOR(k) from predecessor: coordinator = k if k != id(p): participant = false forward COORDINATOR(k) to succ(p) // propagate the announcement around // if k == id(p), the announcement has completed its lap; stop forwarding ```

Why the max wins. Each ELECTION message carries the largest ID it has seen so far, since every process compares the incoming ID to its own and forwards whichever is larger. Because the ring is finite, this "running maximum" message eventually completes a full circuit and returns to the process whose ID it carries — this can only be the single largest surviving ID in the ring, since every other ID gets overwritten en route. That process then knows it has won and floods a COORDINATOR message around the ring exactly once more to inform everyone.

Bully — message complexity. In the worst case, the process with the lowest ID detects the failure first. It sends $n-1$ ELECTION messages. Each of those processes, upon receiving one, may itself start an election, cascading up to $n-2$ more ELECTION messages, and so on. Summing the cascade gives $O(n^2)$ messages in the worst case. In the best case (the second-highest-ID process detects the failure), only $O(n)$ messages are needed: one round of ELECTION/OK plus one round of COORDINATOR announcements.

Bully — time complexity. Turnaround time is bounded by the number of cascading rounds, each bounded by one timeout period. Since the cascade has depth at most $n$ (each round strictly increases the "current candidate" ID), the election completes in $O(n)$ sequential rounds in the worst case, each costing $O(1)$ message round-trip time, so wall-clock time is $O(n \cdot T)$ for timeout $T$. In practice, because higher-ID processes usually respond quickly, real elections often finish in one or two rounds.

Bully — correctness. The key invariant is: at every point during the algorithm, the process holding the highest surviving ID never loses an election it participates in. Proof sketch: this process, by definition, has no higher-ID process to defer to. When it starts its own election (either self-initiated or triggered by receiving an ELECTION message), the `higher` set it computes is empty (restricted to live processes), so it immediately calls `become_coordinator()`. Any lower-ID process that sends it an ELECTION message receives an OK and correctly stands down. Since the algorithm guarantees this top process eventually starts (or receives) an election — it will notice the old coordinator's failure via timeout even if no one else's ELECTION reaches it in time — termination and uniqueness both follow. Multiple concurrent elections initiated by different processes are safely absorbed because a lower process always defers upon receiving an OK, and the algorithm is idempotent: redundant ELECTION messages just trigger redundant (harmless) cascades that converge to the same winner.

Ring — message complexity. If the process that detects the failure is adjacent (in ring order, just before) the highest-ID process, only $O(n)$ messages are needed for the ELECTION lap plus $O(n)$ for the COORDINATOR lap, giving $O(n)$ total. In the worst case with multiple simultaneous initiators (several processes independently notice failure and start their own ELECTION messages), up to $n$ separate election messages may circulate concurrently, each traversing up to $n$ hops, giving a worst case of $O(n^2)$ messages — though the `participant` flag suppresses many of these early (a process already participating only forwards larger IDs, and drops smaller stale ones), keeping realistic concurrent-initiation overhead well below the naive bound.

Ring — correctness. The invariant is: the maximum ID present at protocol start can never be "overwritten" as the message travels the ring. Every comparison rule (`j > id(p)` forwards $j$; `j < id(p)` and not yet participating forwards $id(p)$) guarantees the ID being forwarded only ever increases or stays the same as it circulates. Since the ring is a fixed finite cycle over live processes, a strictly-nondecreasing sequence traveling around it must, after at most $n$ hops, arrive back at the process whose ID it carries — and that can only be the maximum ID, because any smaller ID would have already been overwritten by the time the message reaches the max-ID process. This proves both safety (only the true max can ever see its own ID return) and liveness (termination in at most $2n$ message hops for a single initiator: $n$ for the election lap, $n$ for the coordinator lap).

Tradeoffs. Bully requires each process to know the full membership and IDs of all other processes upfront (harder to reconfigure, more messages), but tends to converge faster since it can short-circuit via direct messaging to only higher processes. Ring requires only successor pointers (more scalable membership-wise) but pays a full traversal even in good cases, and is more sensitive to a single crashed successor link, requiring ring-repair logic to skip dead nodes — an added complexity not shown in the idealized pseudocode above.

Consider five processes with IDs $\{1, 2, 3, 4, 5\}$ where $5$ is the current coordinator, arranged in a ring as $1 \to 2 \to 3 \to 4 \to 5 \to 1$. Process 5 crashes. Process 2 is the first to time out waiting for a heartbeat and starts an election.

Bully trace (all processes know all IDs):

Total messages: 3 (P2's ELECTION) + 2 (P3's ELECTION, since P4 is the only live higher id) + 2 (OKs to P2) + 1 (OK to P3) + 3 (COORDINATOR broadcast) = 11 messages, consistent with the $O(n^2)$ worst case bound for small $n$ but far from the maximum possible (which would occur if P1 had detected the failure first).

Ring trace (same scenario, ring order $1\to2\to3\to4\to5\to1$, P5 dead, so P4's successor is repaired to point to P1):

Total messages: 6 (election lap) + 4 (coordinator lap) = 10 messages — close to the theoretical minimum $2n=10$ for a single initiator, since the failure was detected essentially adjacent to the eventual winner. Both algorithms correctly converge on P4, the highest-ID surviving process, confirming the safety property empirically as well as by proof.

Leader election is not a museum piece — it is a live building block inside production distributed systems. ZooKeeper uses a variant of leader election internally (the "Zab" atomic broadcast protocol) to pick its own coordinator among ensemble replicas. Apache Kafka elects a controller broker among the cluster to manage partition leadership assignments, and separately elects a partition leader among in-sync replicas for each topic partition. MongoDB replica sets run a Raft-inspired election among secondaries whenever the primary becomes unreachable. Cluster orchestration systems like Kubernetes rely on leader election (via distributed locks in etcd) to ensure only one instance of a controller is active at a time, even when multiple replicas are running for redundancy. The conceptual language introduced here — candidates, higher-priority preemption, timeout-triggered elections, and the split-brain danger — carries over almost unchanged into the vocabulary used to describe the Consensus Problem and the election phase of Raft Consensus Algorithm, where the same core ideas are hardened with quorum votes, randomized timeouts, and term numbers to withstand network partitions safely.

Ask the tutor: How does Raft's randomized election timeout prevent the split-vote problem that plain Bully or Ring elections don't even consider?