Catalog My learning Blog
Distributed Systems Explained: CAP, Clocks and Replication · Phase 3 · Lesson 17 · 3 min read

Leader Election in Distributed Systems

On this page
  1. Why elect a leader
  2. The Bully algorithm
  3. Randomized timeouts with majority votes (Raft-style)
  4. Lease-based election through a coordination service
  5. Split brain: two leaders for a moment
  6. Choosing a leader election approach
  7. Check yourself

Why elect a leader

A leader simplifies everything else: one node orders writes, assigns work, or runs the nightly job, so decisions don't conflict. The difficulty is changing leaders safely when the current one fails, or seems to.

The Bully algorithm

A classic approach (Garcia-Molina, 1982): every node has a unique id; the highest-id live node should lead.

  1. A node noticing the leader is gone sends Election messages to all higher-id nodes.
  2. If any answers, it takes over the election; the lower node waits.
  3. If none answers, the node declares itself leader and announces Coordinator to everyone.

It's simple, but it assumes reliable failure detection. If the highest-id node is merely slow, or a partition separates nodes, two nodes can each conclude they're the highest live node and both declare themselves leader. Every node coming back also triggers a new election.

Randomized timeouts with majority votes (Raft-style)

As in Day 16: followers wait a random election timeout, become candidates, and need a majority of votes within a numbered term. Two properties make it hold up under failures:

  • Majority votes: a node on the minority side of a partition can't win, so at most one leader per term.
  • Terms: messages carry the term, so a node hearing a higher term steps down immediately.

Randomization keeps candidates from colliding; when they do (a split vote), the next random timeout usually resolves it.

Bully elects the highest live id by messaging higher nodes; Raft-style election uses random timeouts and majority votes per term; lease-based election goes through a coordination service.
Bully elects the highest live id by messaging higher nodes; Raft-style election uses random timeouts and majority votes per term; lease-based election goes through a coordination service.

Lease-based election through a coordination service

Most applications don't implement elections; they borrow consensus. Every candidate tries to acquire a lease in etcd, ZooKeeper, Consul or the Kubernetes API (a Lease object). The holder is leader and must renew the lease periodically; if it stops, the lease expires and another candidate takes it. The coordination service runs Raft or ZAB underneath, so lease ownership is consistent.

Kubernetes controllers, many job schedulers and HA pairs of services elect leaders exactly this way.

Split brain: two leaders for a moment

No election scheme can stop an old leader from believing it's still leader. It may be paused by garbage collection, cut off by a partition, or simply not have checked its lease yet, while a new leader is elected. During that window, both may act.

Defenses, in increasing strength:

  • Check before acting: confirm leadership (lease still valid, or a quorum still acknowledges you) right before each important action. Narrows the window; doesn't close it.
  • Lease margins: stop acting a safety margin before your lease expires, assuming bounded clock drift.
  • Fencing tokens: each new leadership gets a higher number (the term or lease revision), passed with every write; storage rejects writes with an older number (Day 18). This closes the window, for resources that check tokens.

Choosing a leader election approach

NeedUse
Leader for your own service (scheduler, singleton worker)Lease in etcd, ZooKeeper or Kubernetes, plus fencing tokens for writes
Leader within a replicated data storeThe store's own consensus (you won't write this)
Simple, trusted, small LAN with tolerance for brief duplicatesBully-like schemes, with care

Check yourself

It relies on timeouts to detect failures; a slow node or a partition can make two nodes each believe they're the highest live node.

A candidate needs votes from a majority, and each node votes for at most one candidate per term. Any two majorities overlap in at least one node, so two candidates can't both win the same term.

A fencing token: every leader gets a strictly increasing number, and the storage remembers the highest it has seen and rejects writes with a lower one. The paused leader's old token is rejected, even though it still thinks it's the leader.

When your application needs one active worker or scheduler and you already run a coordination service; you reuse its consensus instead of implementing elections yourself.

Long garbage collection pauses, VM freezes or network partitions that make an old leader miss that it was replaced, while it keeps acting as leader.