Leader Election

Leader election is the process by which a group of nodes selects exactly one node to coordinate a task, such as accepting writes for a shard, running a scheduled job, or assigning partitions. A single leader avoids conflicting concurrent actions and simplifies ordering. The hard part is not choosing a leader. It is guaranteeing that a previous leader that is slow, partitioned, or paused does not keep acting as leader after a new one is chosen.

Why systems use a leader

• Ordering. One node sequences writes, so replicas apply them in the same order (see replication protocols).
• Coordination. One node assigns work, for example partition ownership in a cluster.
• Exclusivity. Some jobs must run on one node at a time: cron-like schedulers, compaction coordinators, singleton consumers.

The cost is that the leader is a bottleneck and, until failure is detected and a replacement is elected, a temporary point of unavailability.

Requirements

• Safety. At most one leader per term or lease period.
• Liveness. If the current leader fails, a new one is eventually elected.
• Failure detection. The group must detect leader failure, typically by missed heartbeats. A slow leader is indistinguishable from a dead one, so detection is inherently uncertain (see gossip and failure detection).

Approaches

Bully algorithm

Each node has a unique numeric ID. The node with the highest ID among live nodes is leader.

1. A node that notices the leader is down sends an ELECTION message to all nodes with higher IDs.
2. If none reply, it declares itself leader and sends COORDINATOR to all.
3. If a higher node replies, that node takes over the election and the sender stops.

sequenceDiagram
    participant N2 as Node 2
    participant N3 as Node 3
    participant N4 as Node 4
    participant N5 as Node 5 (failed leader)
    Note over N2: detects N5 is down
    N2->>N5: ELECTION
    Note over N5: no reply
    N2->>N3: ELECTION
    N2->>N4: ELECTION
    N3-->>N2: OK, taking over
    N4-->>N2: OK, taking over
    Note over N3,N4: N3 and N4 each start their own election, only N4 has no higher live node
    N4->>N5: ELECTION
    Note over N4: no reply from N5
    N4->>N2: COORDINATOR
    N4->>N3: COORDINATOR

In the diagram, every live node below the highest live ID eventually hands over, so the highest live ID (Node 4) wins. Bully assumes reliable failure detection and a network without partitions. Under a partition, each side elects its own leader, so it is unsafe in real networks. It also causes many messages, at worst O(n^2), and any recovering high-ID node forces a new election.

Consensus-based election (Raft)

Election is a consensus problem: nodes agree on who leads in a given term. In Raft, a node needs votes from a majority to become leader, and each node votes once per term. Since two majorities overlap, two leaders cannot exist in the same term. A leader that loses contact with the majority cannot commit entries, and it steps down on seeing a higher term. This approach is safe under partitions and is used in etcd, Consul, and CockroachDB.

Lease-based election with a coordination service

Applications often delegate election to ZooKeeper or etcd, which themselves run consensus.

ZooKeeper recipe:

1. Each candidate creates an ephemeral sequential znode under an election path, such as /election/n_0000000007. An ephemeral znode is deleted when the creating client's session ends.
2. The candidate with the lowest sequence number is leader.
3. Every other candidate sets a watch on the znode with the next lower sequence number, not on the leader itself. When it disappears, the watcher checks whether it is now the lowest.

Watching only the predecessor avoids a herd effect, where every candidate wakes up and contends when the leader fails.

etcd approach (simple form): A candidate creates a key attached to a lease, a time-limited grant that must be renewed by keepalive messages. A transaction writes the key only if it does not exist. The holder is leader and keeps renewing the lease. If it stops renewing, the lease expires, the key is removed, and other candidates compete.

sequenceDiagram
    participant A as Candidate A
    participant B as Candidate B
    participant E as etcd
    A->>E: create /leader with lease (if absent)
    E-->>A: success, A is leader
    B->>E: create /leader with lease (if absent)
    E-->>B: fail, key exists
    B->>E: watch /leader
    loop every keepalive interval
        A->>E: renew lease
    end
    Note over A: A crashes, lease expires
    E-->>B: /leader deleted
    B->>E: create /leader with lease
    E-->>B: success, B is leader

Lease duration trades detection speed against false positives: short leases fail over quickly but expire during brief pauses; long leases tolerate pauses but delay failover.

A lease holder should treat the lease as expired locally somewhat before the service does, using a safety margin that covers clock drift and renewal delay. Failover time after a crash is at least the remaining lease duration, because no other candidate can acquire the key before it expires. The margin reduces overlap between old and new leaders but cannot remove it, because a process can pause between checking the lease and acting.

Database-based election is also used: a row updated with a conditional write (UPDATE ... WHERE holder = me OR expires_at < now) acts as a lease. It inherits the same problems described next.

Split brain

Split brain occurs when two nodes both act as leader at once. Causes:

• Network partition. The old leader is alive but unreachable, and a new one is elected on the other side.
• Process pause. The old leader freezes because of a long garbage collection pause, VM suspension, or CPU starvation. Its lease expires and a new leader is elected. When the old leader resumes, it still believes it holds the lease because its check of "am I leader" happened before the pause.
• Clock skew. Lease expiry depends on clocks. A leader whose clock runs slow may keep acting after the coordination service considers its lease expired.

Split brain leads to duplicate work, divergent writes, and data corruption. Detection cannot solve it, because the old leader has no way to know it has been replaced.

Fencing tokens

A fencing token is a monotonically increasing number issued each time leadership is granted. The leader includes its token in every request to a protected resource (a database, storage system, or downstream service). The resource remembers the highest token it has seen and rejects any request with a lower token.

sequenceDiagram
    participant A as Old leader (token 33)
    participant L as Lock service
    participant B as New leader (token 34)
    participant S as Storage
    A->>L: acquire lock
    L-->>A: token 33
    Note over A: long pause, lease expires
    B->>L: acquire lock
    L-->>B: token 34
    B->>S: write (token 34)
    S-->>B: accepted, max token = 34
    A->>S: write (token 33)
    S-->>A: rejected, 33 < 34

The enforcement must happen at the resource, since the paused leader cannot check anything. The store below uses a synchronized method so the compare and the update are one atomic step. In Raft, the term number serves as the fencing token. In ZooKeeper, the zxid or znode version can serve, and in etcd the key revision.

public class Main {
    sealed interface WriteResult {
        record Accepted() implements WriteResult {}
        record Rejected(long token, long maxToken) implements WriteResult {}
    }

    static final class FencedStore {
        private long maxToken = 0;
        private String value = "";

        synchronized WriteResult write(long token, String newValue) {
            if (token < maxToken) {
                return new WriteResult.Rejected(token, maxToken);
            }
            maxToken = token;
            value = newValue;
            return new WriteResult.Accepted();
        }

        synchronized String value() {
            return value;
        }
    }

    static String describe(WriteResult result) {
        return switch (result) {
            case WriteResult.Accepted a -> "accepted";
            case WriteResult.Rejected(long token, long max) -> "rejected: token " + token + " < " + max;
        };
    }

    public static void main(String[] args) {
        var store = new FencedStore();
        System.out.println(describe(store.write(34, "from new leader")));
        System.out.println(describe(store.write(33, "from stale leader")));
        System.out.println("value = " + store.value());
    }
}

accepted
rejected: token 33 < 34
value = from new leader

Comparison

Practical guidance

• Prefer an existing coordination service over implementing election by hand.
• Use fencing tokens whenever the leader's actions have side effects on shared state. A lease alone does not give mutual exclusion.
• Keep the leader's work small and make it resumable or idempotent, so a duplicate action from a stale leader does no lasting harm.
• Set lease and heartbeat timeouts well above typical pause times, and monitor leader changes since frequent elections indicate unstable timeouts or network problems.

Interview questions

• Why is a lease alone not enough for mutual exclusion? A leader can pause after checking the lease, resume after it expired, and act while a new leader is also acting. Only the protected resource can reject stale actions, using fencing tokens.
• How does Raft prevent two leaders? A leader needs a majority vote in its term, and each node votes once per term. A leader cut off from the majority cannot commit and steps down when it sees a higher term.
• Why does the ZooKeeper recipe watch the predecessor node? It wakes one candidate per failure instead of all, which avoids a burst of contention.
• What is the trade-off in choosing a lease timeout? Short timeouts give fast failover but risk false expiry during pauses. Long timeouts avoid false expiry but extend downtime after a real failure.