CODING CHALLENGE · N°49

Raft Leader Election (Majority)

Easy Distributed SystemsConsensusRaft

The heartbeat of the Raft consensus algorithm: a candidate becomes leader only if it wins votes from a strict majority of the cluster. That majority rule is what guarantees at most one leader per term — the property that keeps a distributed system consistent. Decide the outcome of an election round. Solve it in Python or TypeScript, with hidden tests.

The problem

A Raft cluster has n nodes. In an election, a candidate votes for itself and requests votes from the other n-1 peers; you are given grants, a list of booleans (one per peer) saying whether each granted its vote. The candidate becomes leader iff it collects a strict majority — more than half of n, i.e. ⌊n/2⌋ + 1 votes (including its own). Return True if it becomes leader, else False.

EXAMPLE 1

Input n = 5, grants = [True, True, False, False]

Output True

1 self + 2 = 3 votes; majority of 5 is 3

EXAMPLE 2

Input n = 5, grants = [False, False, False, False]

Output False

only its own vote — far short of 3

EXAMPLE 3

Input n = 4, grants = [True, False, False]

Output False

2 votes, but a majority of 4 is 3 — a split vote fails

CONSTRAINTS

The candidate always counts its own vote, so total votes = 1 + (number of True in grants).
Majority means strictly more than half: ⌊n/2⌋ + 1. For even n, exactly half is not enough.
This strict-majority rule is why two candidates can never both win the same term — any two majorities overlap on at least one node, and a node votes once per term.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement election_result(n, grants): count 1 (self) plus the granted votes, and return whether that reaches the majority threshold ⌊n/2⌋ + 1.

HINTS — 4 IDEAS

Total votes = 1 (the candidate’s own) + the number of True entries in grants.
The threshold to win is n // 2 + 1 — a strict majority of the whole cluster, not of those who replied.
Return total_votes >= threshold.
Note that a single-node cluster (n = 1) always elects its candidate, and an even cluster can suffer a split vote where no one wins.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

A follower whose election timer fires becomes a candidate: it increments its term, votes for itself, and asks the others for votes. A node grants its vote only if the candidate’s term is at least its own, it has not already voted this term, and the candidate’s log is at least as up-to-date as its own. A candidate that collects a majority becomes leader; a node that sees a higher term steps down.

Complexity

O(N) messages per election round.

Common mistakes

Granting more than one vote per term — that is exactly how you get two leaders (split brain).
Skipping the log-up-to-date check and electing a candidate missing committed entries.
Not stepping down when you observe a higher 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.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Distributed Systems