Consensus: Raft and Paxos

Consensus requires a set of nodes to agree on a single value, with three properties:

• Agreement: all correct nodes decide the same value.
• Validity: the decided value was proposed by some node (no values from thin air).
• Termination: all correct nodes eventually decide.

Why is it hard? Because you cannot distinguish a crashed node from a very slow one. If you wait too long, you may sacrifice liveness (termination). If you decide too early, a "dead" node may come back with a conflicting proposal and violate agreement. Every consensus protocol is a careful negotiation of these two dangers.

Consensus underlies: atomic broadcast, replicated state machines, distributed transactions, leader election, and lock services. Get it wrong and your "reliable" database silently splits into two independent primaries.

Fischer, Lynch, and Paterson (1985) proved: in a fully asynchronous system, no deterministic consensus protocol can guarantee both safety and liveness in the presence of even one crash failure.

The intuition: in an async model, you can never know if a node crashed or is just slow. Any protocol that terminates under all message schedules can be "fooled" by an adversarial scheduler that always delivers messages just late enough to keep the system undecided indefinitely. If the protocol tries to force termination, the scheduler can make it violate safety.

The practical escape hatches:

• Partial synchrony (Raft, Paxos): assume messages eventually arrive; use randomized timeouts or leader leases to break liveness deadlocks.
• Randomization (Ben-Or, PBFT variants): a random coin flip breaks symmetry with probability 1 asymptotically.

FLP is not a reason to give up — it's a reason to be precise about your system model assumptions.

A quorum is any subset of nodes such that any two quorums share at least one member. In a cluster of $n = 2f + 1$ nodes with majority quorums of size $f + 1$:

$\text{Any two quorums share} \ge 1 \text{ node}$

This guarantees that the shared node acts as a "witness" — it carries information from any previous quorum decision into any new quorum. That witness is how Raft and Paxos prevent split-brain without a coordinator node.

Quorum arithmetic:

Adding nodes to increase fault tolerance has a cost: each additional replica you add requires a larger quorum, increasing write latency. Going from 3 to 5 nodes doubles fault tolerance but adds one extra round-trip on the critical path.

Raft divides time into terms (monotonically increasing integers). Each term begins with a leader election:

1. A follower times out waiting for a heartbeat → becomes a candidate, increments its term, votes for itself, sends RequestVote RPCs.
2. A candidate wins if it receives votes from a majority. Crucial: a node grants a vote only if the candidate's log is at least as up-to-date as its own (by term, then by log length).
3. The winner becomes leader for the rest of the term, sending periodic heartbeats to suppress further elections.

// Simplified Raft RequestVote response logic
func (r *Raft) handleRequestVote(req RequestVoteArgs) RequestVoteReply {
    if req.Term < r.currentTerm {
        return RequestVoteReply{Granted: false, Term: r.currentTerm}
    }
    logOk := req.LastLogTerm > r.lastLogTerm() ||
        (req.LastLogTerm == r.lastLogTerm() && req.LastLogIndex >= r.lastLogIndex())
    if (r.votedFor == "" || r.votedFor == req.CandidateID) && logOk {
        r.votedFor = req.CandidateID
        return RequestVoteReply{Granted: true, Term: r.currentTerm}
    }
    return RequestVoteReply{Granted: false, Term: r.currentTerm}
}

The "log at least as up-to-date" rule is the safety linchpin: it prevents a leader from being elected if it's missing committed entries.

Once elected, the leader handles all writes:

1. Client sends a command to the leader.
2. Leader appends the entry to its log (with its current term).
3. Leader sends AppendEntries RPCs to all followers in parallel.
4. Once a majority of nodes have acknowledged the entry, the leader marks it committed and applies it to its state machine.
5. The leader piggybacks the commit index on the next AppendEntries; followers apply committed entries.

Critical commit rule: a leader may only commit entries from its own term by counting replicas. It cannot retroactively commit entries from prior terms this way (Raft Figure 8 scenario). Prior-term entries become committed implicitly when a current-term entry is committed and the log is contiguous.

This asymmetry is intentional: it prevents a new leader from incorrectly declaring old entries committed when they were actually superseded during a prior network partition.

A single write from client to commit:

Paxos (Lamport, 1998) solves single-value consensus in two phases. The proposer picks a proposal number $n$ and sends Prepare(n) to a quorum of acceptors. Each acceptor responds with a promise to reject any future Prepare with a lower number, plus the highest-numbered accepted value it has seen (if any). The proposer, having received a quorum of promises, sends Accept(n, v) where $v$ is the value from the highest-numbered prior acceptance it learned (or its own value if none). Acceptors accept if they haven't promised to reject $n$. When a quorum accepts, consensus is reached.

Multi-Paxos extends this to a log by electing a stable leader that skips Phase 1 for subsequent slots, making it efficient in the common (no-failures) case. Paxos is notoriously hard to implement correctly — the paper has many implicit constraints, leading Lamport to later publish Paxos Made Simple. Raft was explicitly designed to be more understandable, with stronger invariants and less implementation freedom.

In practice, most new systems choose Raft. Paxos still powers critical Google infrastructure (Chubby, Spanner) because those teams wrote Paxos before Raft existed and have deep expertise. The algorithms are equivalent in capability; the difference is engineering clarity. If you're starting fresh, implement Raft — Diego Ongaro's thesis has the full invariant list and a test harness.