Raft Overview

Raft's design bet is decomposition. Instead of one monolithic correctness argument, you get three sub-problems you can build and reason about separately:

1. Leader election — pick exactly one node to be in charge.
2. Log replication — the leader streams an ordered log of commands to everyone.
3. Safety — the rules that keep 1 and 2 correct through crashes and partitions.

Roles

Every node is in exactly one of three states:

• Follower — passive; answers RPCs and resets its election timer whenever the leader's heartbeat arrives.
• Candidate — a follower whose timer expired; it is collecting votes.
• Leader — handles all client requests, replicates the log, sends heartbeats.

Terms: Raft's logical clock

Time is divided into terms, integers that only move forward. Each term has at most one leader (a term can also end with no winner and a new election). Every RPC carries the sender's term, and the rule is universal: see a term greater than yours ⇒ adopt it and become a follower. This is how a deposed leader — isolated for a minute, still believing it rules — discovers reality the instant it hears from the cluster. There is no separate "am I still leader?" protocol; terms do all of it.

            timeout                 majority of votes
follower ----------->  candidate ------------------->  leader
   ^                    |     ^                          |
   |  sees higher term  |     | split vote: timeout,     |
   +--------------------+     | term+1, retry            |
   ^                          +--------------------------+
   |                                                     |
   +------------------ sees higher term -----------------+

State you will maintain for the rest of this course:

• current_term — highest term seen (must survive crashes)
• voted_for — who got this node's vote in current_term, or none (must survive crashes)
• log[] — the replicated entries (must survive crashes)
• commit_index, last_applied — volatile bookkeeping, rebuilt after restart

The transition rules, exactly

• follower → candidate: increment current_term, set voted_for = self. Every retry increments again — three straight timeouts from term 0 leave you a candidate at term 3.
• anything → follower on seeing term T > current_term: set current_term = T and clear voted_for — that vote belonged to an older term and means nothing in the new one.
• An equal term must NOT clear voted_for. This is the classic implementation trap: voted_for means "my single vote in this term." Clear it while the term is unchanged and the node can vote twice in one term — two candidates can then both assemble a "majority," giving two leaders and the exact split-brain Raft exists to prevent.
• candidate → leader is the only legal path to leadership. A follower has won nothing and can never jump straight to leader.

Raft is generic — the state machine is yours

Raft never inspects commands. It delivers the same ordered log to every node; each node applies entries to a deterministic state machine. Ours is a KV map (set x=5) — exactly what etcd is. The same trick powers replicated locks, queues, and counters.

Your exercise

Implement the role transitions: INIT, BECOME_CANDIDATE, BECOME_FOLLOWER <term>, BECOME_LEADER, STATUS. The grader-caught mistake is honoring an illegal BECOME_LEADER: straight after INIT n1 it must be ignored, and STATUS still prints state=follower term=0 voted_for=none. Also verify your increments accumulate — three BECOME_CANDIDATE in a row from INIT n5 prints state=candidate term=3 voted_for=n5 — and that BECOME_FOLLOWER 5 after leading at term 1 prints state=follower term=5 voted_for=none (strictly greater term: adopt it, clear the vote).