Leader Election in Distributed Systems

Introduction

In distributed systems, many protocols assume there is a single coordinator that can make decisions, sequence operations, or serve as a bottleneck for contentious requests. Leader election is how you designate that coordinator in a system where nodes can crash and networks can partition.

The problem is deceptively simple: how do you pick one node out of many to be “in charge”? The answer requires handling failures, network delays, and the possibility that multiple nodes might think they are the leader simultaneously.

Why Leader Election Matters

Many distributed protocols perform better with a single leader. Consider a replicated log: without a leader, multiple nodes might try to append at the same index. With a leader, all writes go through one node, which sequences them and replicates to followers.

But leadership introduces a dependency. If the leader crashes, you need to elect a new one quickly while ensuring that no two nodes believe they are the leader. The system must make progress even as leadership changes.

Basic Approaches

Highest Node ID

The simplest approach is to elect the node with the highest identifier (ID). When nodes notice the leader is gone, they wait a random timeout and then propose themselves as leader if they have the highest ID among nodes that have responded. This is similar to Raft’s randomized election timeout approach.

The randomness breaks ties. If all nodes used the same timeout, they would all propose themselves simultaneously and likely deadlock.

Bully Algorithm

The bully algorithm elects the highest-ID node as leader. When a node notices the leader is unresponsive, it sends an election message to all nodes with higher IDs. If none respond, it becomes leader. If any respond, the responding node with the highest ID wins.

The name “bully” comes from the fact that the highest-ID node always wins, regardless of who initiated the election. In practice, this works well when node IDs correlate with reliability or capacity.

Bully Algorithm Sequence Diagram

In the bully algorithm, the highest-ID node always wins by forcing younger nodes out of elections:

sequenceDiagram
    participant N1 as Node 1 (ID=1)
    participant N3 as Node 3 (ID=3)
    participant N5 as Node 5 (ID=5)
    participant N7 as Node 7 (ID=7)

    Note over N1,N7: Node 7 (current leader) crashes
    N1->>N3: ELECTION
    N3->>N5: ELECTION
    N5->>N7: ELECTION
    Note over N7: No response — Node 7 is down
    N5->>N1: OK(ID=5)
    N5->>N3: OK(ID=5)
    Note over N5,N1: N3 and N1 acknowledge N5
    N5->>N1: COORDINATOR(ID=5)
    N5->>N3: COORDINATOR(ID=5)
    Note over N5,N1: N5 becomes leader

Leader Election Algorithm Comparison

Algorithm	Time Complexity	Message Complexity	Assumptions	Best For
Highest-ID	O(1) to detect failure	O(n) election msgs	Random timeout	Simple systems
Bully	O(n) worst case	O(n^2) in worst case	Synchronous network	Small clusters
Lease-based	O(1) lease check	O(n) heartbeats	Synchronized clocks	Long-running leadership
Consensus-based	O(election)	O(n) RPCs	Faulty but async	Critical coordination

Algorithm	Partition Tolerance	Recovery Speed	Implementation	notes
Highest-ID	Low (no quorum)	Fast	Simple	Risk of split brain
Bully	Low	Moderate	Moderate	Highest-ID wins always
Lease-based	Medium	Lease-dependent	Moderate	Clock skew risk
Consensus-based	High	Election timeout	Complex	Strong guarantees

Lease-Based Leadership

A more sophisticated approach uses leases. Rather than claiming leadership forever, a node holds leadership for a fixed period (the lease). To renew leadership, it must successfully extend the lease before it expires.

sequenceDiagram
    participant L as Leader
    participant F1 as Follower 1
    participant F2 as Follower 2

    rect rgb(40, 60, 40)
        Note over L,F2: Leadership with Lease
        L->>F1: Heartbeat + Extend Lease
        L->>F2: Heartbeat + Extend Lease
        F1-->>L: ACK
        F2-->>L: ACK
        Note over L: Lease valid for next 10s
    end

    rect rgb(80, 40, 40)
        Note over L,F2: Lease Expires
        L-xF1: Heartbeat (fails)
        L-xF2: Heartbeat (fails)
        Note over F1: Lease expired, starts election
    end

Leases provide a form of eventual leader detection. If the leader fails to extend its lease (because it crashed or is network-partitioned), other nodes will notice after the lease expires and initiate an election.

The trade-off is that leases assume synchronized clocks. Clock skew can cause leases to expire at different times on different nodes, potentially leading to multiple leaders. Bounded clock skew can be addressed by setting lease durations with sufficient margin.

Consensus-Based Election

Some systems use consensus protocols for leader election. Paxos can elect a leader as part of the consensus process (the node that successfully proposes in a round becomes the leader). Raft explicitly separates leader election (Phase 1 of Paxos) from normal operation.

Using consensus for leader election provides strong guarantees but adds complexity. The benefit is that the elected leader is guaranteed to be unique and recognized by a majority.

Split Brain and Quorum

The fundamental challenge in leader election is split brain: the network partitions and both sides elect a leader, each believing they are in charge. The consequences depend on what the system does with leadership.

If the system uses quorum-based replication (like Paxos or Raft), writes to the minority partition will fail to achieve consensus. This prevents split brain from corrupting data, but the minority partition cannot make progress.

If the system relies on a single leader without quorum guarantees (like primary-backup replication without a quorum), split brain can cause data divergence. One partition might apply writes that the other partition does not know about.

Understanding these trade-offs connects to the CAP Theorem. Systems that prioritize availability during partitions may choose eventual leadership, trading consistency for availability.

Detecting Leader Failure

Accurate failure detection is crucial. Too sensitive and you get spurious elections; too insensitive and you delay recovery.

Heartbeats: The most common approach. The leader sends periodic heartbeats to followers. If a follower misses enough heartbeats, it assumes the leader is dead and initiates an election.

Epochs or Terms: Many protocols use logical timestamps (epochs or terms) that increment whenever leadership changes. Nodes refuse to accept messages from older epochs. This handles the case where a leader that was thought dead actually recovers and tries to reclaim leadership.

Practical Considerations

In practice, leader election is built into consensus protocols rather than implemented separately. If you need leader election for your application, consider using an existing coordination service like etcd or ZooKeeper, which handle leader election and provide guarantees about leader uniqueness.

Building your own leader election from scratch is error-prone. The edge cases (simultaneous elections, network partitions, message reorder) are subtle. My post on Distributed Transactions discusses how to handle these edge cases when coordination is involved.

Timeout Selection Guidance

Picking election timeouts is a balancing act. Set them too short and you get spurious elections from transient network hiccups. Set them too long and you maximize downtime during an actual failure.

For a cluster in the same data center: election timeout of 150-300ms with heartbeat every 50ms is a reasonable starting point. This gives you a 100-250ms window to detect failure before triggering an election, while avoiding false positives from normal network variation.

For geo-distributed clusters, you need to account for round-trip time between sites. An election timeout of 2-5 seconds with heartbeats every 500ms works better when RTT between nodes is 100ms+. The timeout must exceed the maximum expected network delay by a comfortable margin.

A usable formula: set election_timeout_min to 2x the P99 network RTT between nodes, and election_timeout_max to 3-4x. This gives enough headroom for network variation without being too slow to detect failures.

One risk that does not get enough attention: thundering herds. When the leader fails, every node whose election timeout fires at roughly the same moment tries to elect itself. Randomized jitter on the timeout breaks this up. This is why Raft and ZooKeeper both randomize their timeouts rather than using fixed values.

Relationship to Consensus

Leader election and consensus are related but distinct. Leader election chooses a node; consensus agrees on a value. Raft combines these by using the leader election phase (similar to Paxos Phase 1) to establish a leader who then proposes values.

Paxos can operate without a distinguished leader, but practical implementations usually designate one to improve performance. The Raft Consensus Algorithm post goes into detail on how this works.

Which Approach to Use

flowchart TD
    A[Need Leader Election?] --> B{What's your priority?}
    B --> C[Correctness & Safety]
    B --> D[Simplicity & Speed]
    B --> E[Long-Running Leadership]
    B --> F[Minimal Complexity]

    C --> G[Consensus-based<br/>Use Raft or Paxos]
    D --> H{Cluster size?}
    H -->|< 10 nodes| I[Bully Algorithm]
    H -->|> 10 nodes| J[Highest-ID + Timeout]

    E --> K{Can you tolerate clock sync?}
    K -->|Yes| L[Lease-based]
    K -->|No| M[Consensus-based]

    F --> N[Use existing coordination service<br/>etcd, ZooKeeper]

    I --> O[End]
    J --> O
    L --> O
    M --> O
    G --> O
    N --> O

Decision guidance:

• Consensus-based (Raft/Paxos): Choose when correctness is critical and you can handle complexity. Used in etcd, CockroachDB, TiKV.
• Bully Algorithm: Good for small, stable clusters where highest-ID correlates with reliability.
• Highest-ID: Simple scenarios, non-production systems, or when IDs naturally represent priority.
• Lease-based: Long-running operations where you need bounded leader tenure without full consensus.
• Coordination Service: Most practical choice. etcd and ZooKeeper handle all edge cases.

Conclusion

Leader election is fundamental to many distributed systems. The right approach depends on your requirements for consistency, availability, and recovery time. Simple approaches like highest-ID work well in stable environments. Lease-based approaches provide better progress guarantees. Consensus-based approaches provide strong consistency at the cost of complexity.

For most applications, using an existing coordination service is the practical choice. For understanding how these services work internally, studying leader election algorithms is invaluable.