The Problem and the Players

A single server that applies commands in order is easy to reason about: it is a state machine. Feed it the same commands in the same order and it always ends up in the same state. The whole trick of fault-tolerant systems is to run several copies of that state machine and keep them in sync — a replicated state machine. If every replica applies the same log of commands in the same order, the replicas are interchangeable, and the service survives the loss of a minority of them.

So the real problem is not replicating the state machine. It is replicating the log. That is what a consensus algorithm does, and Raft (Ongaro & Ousterhout, In Search of an Understandable Consensus Algorithm) is a consensus algorithm designed above all to be understandable. Keep the paper open while you take this course — Figure 2 of the paper is the complete specification, and every challenge here implements a piece of it verbatim. Struct and field names in this course deliberately match the paper (currentTerm, votedFor, prevLogIndex, leaderCommit, …) so the paper reads as your documentation.

Terms: Raft's logical clock

Raft divides time into terms, numbered with consecutive integers. Each term begins with an election; at most one leader can win a given term. Terms act as a logical clock: every message carries the sender's term, and servers use it to detect stale information. Two rules from Figure 2 ("Rules for Servers, All Servers") do most of the work:

• If a request or response contains a term T > currentTerm: set currentTerm = T and convert to follower.
• If a message carries a term smaller than currentTerm, it is stale: reject or ignore it (replying with your own term so the sender can update itself).

The three states

At any moment a server is in exactly one of three states (paper §5.1):

• Follower — passive; responds to requests from leaders and candidates.
• Candidate — trying to get elected leader.
• Leader — handles all client requests and drives log replication.

Figure 4 of the paper draws the transitions:

// Follower  --times out, starts election-->            Candidate
// Candidate --times out, new election-->               Candidate (again)
// Candidate --receives votes from majority-->          Leader
// Candidate --discovers current leader or new term---> Follower
// Leader    --discovers server with higher term-->     Follower

A follower that hears nothing from a leader for an election timeout assumes the leader is dead: it increments currentTerm, votes for itself, and becomes a candidate. A candidate that gathers votes from a majority of the cluster becomes leader. A candidate that instead receives an AppendEntries request from a legitimate leader (same or higher term) steps back down to follower. And anyone who sees a higher term — leader included — immediately becomes a follower of that term.

Majorities are why Raft works: any two majorities of the same cluster overlap in at least one server, so at most one candidate can win a term, and any elected leader has talked to at least one server that saw previous decisions.

Modeling this deterministically

In this course we never open a socket or start a timer. Time and messages are data: an election timeout is just an event value, an incoming RPC is just a struct. Every function you write is a pure, deterministic step over in-memory state — which is exactly how you want to unit-test a consensus algorithm before you ever wire it to a network.