Leader Election

A follower expects a heartbeat from the leader every few dozen milliseconds. If its randomized election timeout (typically 150–300 ms) expires in silence, it assumes the leader is dead and stands for election:

1. current_term += 1
2. voted_for = self
3. reset the election timer
4. send RequestVote(term, my_id, last_log_index, last_log_term) to every peer

It wins on votes from a majority (counting itself), becomes leader, and immediately heartbeats to shut down everyone else's timers. If the vote splits, nobody wins; a new timeout fires and a higher term tries again. Randomized timeouts make repeat collisions unlikely.

The vote rule — get every clause right

on RequestVote(candidate_id, candidate_term, cand_last_idx, cand_last_term):
    if candidate_term < current_term:
        reply NO                              # stale candidate, refuse flat
    if candidate_term > current_term:
        current_term = candidate_term         # adopt the newer term
        voted_for = none                      # the vote is available again
    up_to_date = cand_last_term > my_last_term
              or (cand_last_term == my_last_term and cand_last_idx >= my_last_idx)
    if (voted_for is none or voted_for == candidate_id) and up_to_date:
        voted_for = candidate_id              # record BEFORE replying
        reply YES
    else:
        reply NO

Two clauses carry the safety load:

"none or the same candidate." Vote replies get lost; candidates retransmit. If your rule is "already voted ⇒ NO", a retransmitted request from the very candidate you voted for gets refused, and elections stall for no reason. Re-granting to the same candidate in the same term is idempotent and required.

The up-to-date check (§5.4.1). Without it, this happens: a leader replicates set balance=100 to a majority {A, B, C} and acks the client. D, partitioned the whole time, times out and campaigns with an empty log. If A or B may vote for D, D can become leader — and D's empty log becomes the cluster's truth, erasing an acknowledged write. The check guarantees that in any majority a candidate assembles, at least one voter would have refused a candidate missing committed entries.

The comparison order kills two seductive wrong intuitions:

1. "Longer log wins." No: last TERM dominates. A candidate whose last entry is (idx 4, term 3) beats a voter at (idx 5, term 2) — the shorter log is newer history.
2. "Enough data excuses a stale term." No: the term check comes first. A candidate at term 4 with a 100-entry log is refused flat by a voter already at term 5.

One more subtlety: granting a vote mutates you. You may have adopted a larger current_term, and you set voted_for — two of Raft's three durable fields. They must stick so the next request sees them.

Your exercise

Implement the vote decision with state that persists across requests. The grader-caught mistakes, verbatim: after STATE 5 none 10 5, REQUEST_VOTE c4 4 100 5 must print NO — huge log, stale term. After STATE 5 c1 10 5, the retry REQUEST_VOTE c1 5 10 5 must print YES — same candidate, same term, grant again. And state must stick: when c1 and then c2 both ask in term 1, the output is YES then NO — forget to record voted_for on the first grant and you print two YESes, handing one term two leaders.