Leader Election

Why Distributed Systems Need Leaders

In a distributed system with multiple nodes, certain operations require coordination: deciding which node processes a write, determining the order of events, or assigning work to workers. Without a designated leader, every node must coordinate with every other node for each decision, which is expensive (O(n^2) messages) and slow.

A leader simplifies coordination. One node makes decisions, and the others follow. The leader accepts writes, sequences operations, and distributes work. The followers replicate the leader's decisions and stand ready to take over if the leader fails.

The hard part is not picking a leader. The hard part is ensuring that exactly one leader exists at any given time, even when nodes crash, networks partition, and messages arrive out of order. Two nodes both believing they are the leader (split brain) is one of the most dangerous failure modes in distributed systems. It leads to conflicting writes, data corruption, and inconsistent state.

The Bully Algorithm

The Bully algorithm is the simplest leader election protocol. Every node has a unique numeric ID. The node with the highest ID is the leader.

When a node detects that the leader is down (via missed heartbeats), it initiates an election:

1. The detecting node sends an ELECTION message to all nodes with higher IDs
2. If any higher-ID node responds with OK, the detecting node yields — it knows a higher-ranked node will take over
3. If no higher-ID node responds (they are all down), the detecting node declares itself the leader and sends a COORDINATOR message to all nodes
4. A higher-ID node that receives an ELECTION message responds with OK and starts its own election with even higher-ID nodes

The algorithm is called "Bully" because the highest-ranked available node always wins. It is straightforward to implement but has drawbacks: it generates O(n^2) messages in the worst case, and if the highest-ID node is flapping (repeatedly crashing and recovering), the system spends all its time re-electing.

The Ring Algorithm

In the Ring algorithm, nodes are arranged in a logical ring. Each node knows its successor. When a node detects the leader has failed:

1. It sends an ELECTION message around the ring, including its own ID
2. Each node that receives the message adds its own ID and forwards it to the next live node
3. When the message returns to the node that started the election, it contains the IDs of all live nodes
4. The node with the highest ID (or lowest, depending on convention) in the list is declared the leader
5. A COORDINATOR message is sent around the ring to announce the new leader

The Ring algorithm generates fewer messages than Bully (O(n) per election) but requires maintaining the ring topology and handling ring breaks when nodes fail.

Neither Bully nor Ring handles network partitions correctly. If the network splits, each partition might elect its own leader, resulting in split brain. For partition-tolerant leader election, you need consensus algorithms.

Raft: The Industry Standard

Raft is the most widely used consensus-based leader election algorithm in production systems. It was designed by Diego Ongaro and John Ousterhout specifically to be understandable — a reaction to the notoriously difficult Paxos algorithm.

In Raft, every node is in one of three states: follower, candidate, or leader.

Normal operation: The leader sends periodic heartbeats to all followers. Followers reset their election timer each time they receive a heartbeat. Everything is stable.

Election trigger: If a follower's election timer expires (it has not heard from the leader for a randomized timeout, typically 150-300ms), it transitions to candidate and starts an election.

Voting: The candidate increments the current term number, votes for itself, and sends RequestVote RPCs to all other nodes. Each node votes for at most one candidate per term (first-come-first-served). A candidate wins if it receives votes from a majority of nodes.

Randomized timeouts prevent ties. If two nodes start elections simultaneously, they are unlikely to have the same timeout, so one will typically complete its election before the other. If a tie does occur (no candidate gets a majority), both candidates time out and start a new election with incremented terms. In practice, elections complete within a few hundred milliseconds.

Term numbers prevent stale leaders. Every message in Raft includes the sender's term number. If a node receives a message with a higher term, it immediately becomes a follower. A leader that was network-partitioned and reconnects will discover that the cluster has moved to a higher term and step down. This prevents split brain without requiring explicit leader revocation.

Safety guarantee: Raft ensures that a new leader always has all committed entries from previous terms. A candidate cannot win an election unless its log is at least as up-to-date as a majority of nodes. This prevents data loss during leader transitions.

ZooKeeper's Leader Election

Apache ZooKeeper uses a variant of the Zab (ZooKeeper Atomic Broadcast) protocol for leader election. ZooKeeper is widely used as a coordination service — it is the backbone of Kafka (pre-KRaft), HBase, Solr, and many other distributed systems.

ZooKeeper provides ephemeral sequential znodes that make leader election straightforward for client applications:

1. Each participant creates an ephemeral sequential znode under a designated path (e.g., /election/candidate-000001)
2. The participant with the lowest sequence number is the leader
3. Each non-leader watches the znode immediately preceding it (not the leader znode — this prevents the "herd effect" where all nodes react simultaneously to the leader's failure)
4. When the leader crashes, its ephemeral znode is automatically deleted, and the next-in-line node is notified

This approach is simple for application developers but introduces a dependency on ZooKeeper itself, which must be deployed and operated as a separate cluster.

etcd and Kubernetes

etcd uses Raft directly for consensus and leader election among its own nodes. Kubernetes relies on etcd as its source of truth, and many Kubernetes components (like the controller manager and scheduler) use etcd-based leader election to ensure only one instance is active at a time.

The Kubernetes leader election library creates a Lock resource (a Lease object) in etcd. The leader periodically renews the lease. If the leader fails to renew within the lease duration, another instance acquires the lock and becomes the new leader. This is a lease-based approach rather than a voting-based approach.

Failure Modes That Break Leader Election

Network partitions are the primary threat. If the network splits, nodes on each side of the partition might elect their own leader. Raft handles this because a leader needs a majority of votes, and only one side of a partition can have a majority. But if you use a simpler algorithm (Bully, Ring) without majority-based quorums, you will get split brain.

Clock skew can cause premature elections. If one node's clock runs fast, its election timeout expires before the leader's heartbeats stop, triggering unnecessary elections. Raft mitigates this with randomized timeouts, but significant clock skew still causes instability.

Byzantine failures (nodes lying or behaving maliciously) are not handled by Raft, Bully, or Ring. These algorithms assume crash-stop failures: a node is either working correctly or completely dead. For Byzantine fault tolerance, you need algorithms like PBFT, which require 3f+1 nodes to tolerate f faulty nodes.

Slow leaders are a subtler problem. The leader is technically alive but processing requests slowly due to GC pauses, disk I/O, or resource contention. Followers may trigger an election, but the old leader has not crashed and may still be processing requests. Raft handles this with term numbers — the old leader will discover the new term and step down — but there is a window where both leaders may issue conflicting operations.

Leader Election in Practice

Kafka (pre-KRaft) used ZooKeeper for controller election. The controller is the Kafka broker responsible for partition leadership assignments and metadata management. When the controller fails, ZooKeeper elects a new one. Starting with KRaft (Kafka Raft), Kafka eliminated the ZooKeeper dependency by implementing Raft-based consensus directly.

Redis Sentinel monitors Redis master nodes and promotes a replica to master when the current master fails. Sentinels use a Raft-like voting protocol among themselves to agree on which replica should be promoted. You need at least three Sentinel instances to tolerate one failure.

MongoDB replica sets elect a primary using a protocol similar to Raft. Members vote, and a candidate needs a majority. The primary handles all writes; secondaries replicate asynchronously. Elections typically complete in 10-12 seconds, during which writes are unavailable.

Interview Guidance

When leader election comes up in a system design interview, the interviewer wants to see that you understand why a leader is needed, how elections work at a high level, and what failure modes exist. You do not need to implement Raft from scratch. But you should know:

• Why a quorum (majority) is necessary to prevent split brain
• The difference between a coordination service (ZooKeeper, etcd) and building election into your application
• That leader election introduces a single point of coordination (the leader) which can become a bottleneck
• That leaderless designs (like Dynamo-style systems) avoid election entirely at the cost of increased complexity for writes

Real-World Production Example

When Apache Kafka removed its ZooKeeper dependency with the KRaft (Kafka Raft) protocol in version 3.3, it was one of the most significant architectural changes in the Kafka ecosystem. For over a decade, Kafka relied on ZooKeeper for controller election — the controller is the broker responsible for managing partition leadership, topic configuration, and cluster metadata. This external dependency created operational pain: operators had to deploy and maintain a separate ZooKeeper cluster, monitor it independently, and troubleshoot complex failure scenarios when ZooKeeper and Kafka disagreed about cluster state.

KRaft embeds leader election directly into Kafka using a Raft-based consensus protocol. A subset of Kafka brokers are designated as "controllers," and they use Raft to elect a single active controller and replicate metadata changes. The metadata log (topic configurations, partition assignments, broker registrations) is itself a Raft-replicated log, which means metadata changes are committed with the same consistency guarantees as Raft provides. When the active controller fails, the remaining controllers elect a new leader through Raft's standard election mechanism — typically within a few hundred milliseconds.

The migration from ZooKeeper to KRaft taught the Kafka community an important lesson about leader election dependencies: if your system depends on an external service for leader election, that external service becomes the most critical component in your infrastructure. ZooKeeper outages caused Kafka outages, even though Kafka itself was healthy. By internalizing leader election, KRaft eliminated an entire category of operational failures and simplified the deployment model from two distributed systems to one.

Original DosiBridge notes for Leader Election

This section is written specifically for this page, not copied from a general system-design checklist. The useful way to study Leader Election is to connect the concept to a production service where growth exposes the first weak assumption in the original design. That framing changes the design discussion from definitions to operating choices.

What makes this topic distinct

• Membership: For Leader Election, decide the membership before choosing tools; otherwise the design looks clean but fails when leader changes.
• Clock Drift: For Leader Election, decide the clock drift before choosing tools; otherwise the design looks clean but fails when election changes.
• Retry Semantics: For Leader Election, decide the retry semantics before choosing tools; otherwise the design looks clean but fails when leader changes.
• Partition Behavior: For Leader Election, decide the partition behavior before choosing tools; otherwise the design looks clean but fails when election changes.
• Reconciliation: For Leader Election, decide the reconciliation before choosing tools; otherwise the design looks clean but fails when leader changes.

Production review question

If a team adopts Leader Election, what observable signal proves it helped instead of only making the architecture diagram more fashionable?

Practical metric to track

Track leader-election health as a named dashboard or review item: combine one user-facing metric, one saturation metric, and one correctness metric. For Leader Election, this keeps the discussion grounded in behavior that can be measured after deployment instead of generic advice that sounds good in an interview but never gets verified.