Raft Leader Election (Majority)

Start from brute force

The version most people write first is “at least half”: 1 + sum(grants) >= n / 2. It looks right and passes every odd cluster, because n / 2 is never a whole number there, so reaching 2.5 of 5 already means 3 votes. It costs O(n) time for the one pass over grants and O(1) space, so speed is not the problem; correctness is. On an even cluster it accepts a tie: (4, [True, False, False]) has 2 votes, 2 ≥ 2.0 is true, and it returns True where the answer is False. Two candidates holding disjoint pairs of a 4-node cluster would then both become leader in the same term.

The approach

The insight is that a Raft election is decided by a fixed number, not by who replied: the candidate needs a strict majority of the whole cluster, n // 2 + 1 votes, and its own vote counts toward it. Any two sets of that size share at least one node, and a node votes at most once per term, so two candidates can never both reach it in the same term. That overlap is the entire safety argument, which is why the bar is computed from n and nothing else.

The reference does it in three lines. votes = 1 + sum(1 for g in grants if g) adds the self-vote to the granted ones (in TypeScript, grants.filter((g) => g).length). majority = n // 2 + 1 uses integer division, so for n = 4 the bar is 3, not 2. It returns votes >= majority, the same test as votes > n // 2. A single-node cluster passes on its own vote, 1 ≥ 1.

Walk through an example

The first example, n = 5 and grants = [True, True, False, False], counted the way the reference counts it.

Complexity

Reference: O(n) time, one pass over the n − 1 entries of grants, and O(1) extra space, because the generator counts without building a list (the TypeScript filter builds an O(n) array; a loop counter avoids it). Naive “at least half”: the same O(n) time and O(1) space; its defect is the threshold, not the cost.

Edge cases to test

• n = 1, grants = []: True. The self-vote alone meets the bar of 1 // 2 + 1 = 1.
• n = 2, grants = [False]: False. A two-node cluster needs both votes, so one failed node stops all elections; the “at least half” rule wrongly returns True here.
• n = 4, grants = [True, False, False]: False. Two of four is a tie, and an even cluster needs n / 2 + 1 = 3.
• n = 5, grants = [False, False, False, False]: False. Only the self-vote, 1 of the 3 needed.
• n = 6, grants = [True, True, False, False, False]: False. Three votes is exactly half of six; the bar is 4.

Common mistakes

• Forgetting the self-vote: sum(grants) alone gives 2 on the first example, short of 3, so a candidate that won is reported as losing.
• Testing “at least half” with votes >= n / 2. It passes every odd cluster and accepts a tie on every even one, e.g. (4, [True, False, False]).
• Computing the bar from len(grants) or from the peers that replied instead of from n. The bar then shrinks when nodes are unreachable, which is exactly when the overlap guarantee matters.
• Treating the majority rule as sufficient on its own. It prevents two leaders only because every node grants at most one vote per term; a voter that grants twice breaks the overlap argument.

Follow-ups an interviewer asks next

Now write the voter side. When should a node grant its vote?

Reject a request whose term is older than the voter’s own; a newer term makes the voter adopt it and become a follower first. Grant only if it has not already voted for a different candidate in that term and the candidate’s log is at least as up to date: a higher last-log term, or the same last-log term and a last index at least as large. Persist the term and vote before replying, so a restart cannot vote twice.

What happens when no candidate reaches the majority?

Nobody leads that term. Each candidate’s election timer expires and it starts a new election in the next term. Raft makes repeats unlikely with randomized election timeouts (the paper’s example range is 150 to 300 ms), so one node usually times out first, wins, and starts sending heartbeats before the others time out again.

Votes arrive one at a time over the network. How do you decide as they come in?

Keep a set of the node ids that granted, so a retried or duplicated reply is never counted twice, and become leader the moment the set plus the self-vote reaches n // 2 + 1. Ignore replies stamped with an older term, and step down to follower as soon as any reply carries a higher term than your own.

Membership is changing. What is n during a reconfiguration?

In Raft’s joint consensus, decisions need separate majorities of both the old and the new configuration, so the check becomes two calls of this function, one per member set, and both must pass. Counting only the new configuration could let an old-configuration majority and a new-configuration majority each elect a leader in the same term.

Where this shows up

Raft leader election is how consensus systems like etcd and Consul pick a single leader safely despite crashes and partitions. The term counter, majority vote, and one-vote-per-term rules are precisely what guarantee at most one leader per term — the invariant the rest of the protocol (and your cluster’s correctness) rests on.

Reference solution

def election_result(n, grants):
    votes = 1 + sum(1 for g in grants if g)   # self-vote plus granted votes
    majority = n // 2 + 1                      # strict majority of the cluster
    return votes >= majority


print(election_result(5, [True, True, False, False]))   # -> True
print(election_result(4, [True, False, False]))         # -> False

function electionResult(n: number, grants: boolean[]): boolean {
  const votes = 1 + grants.filter((g) => g).length;   // self + granted votes
  const majority = Math.floor(n / 2) + 1;              // strict majority
  return votes >= majority;
}

console.log(electionResult(5, [true, true, false, false]));  // -> true
console.log(electionResult(4, [true, false, false]));        // -> false