the consensus problem, and why raft exists

A database leader acknowledges a write, then disappears. The replacement still owes the client that write, even if the acknowledgment was the old leader's last message. Following the write through that failure made consensus concrete for me. The election has to carry an earlier decision into a new term.

I tried to learn Paxos three times. Reading Ongaro's Raft thesis finally helped me connect the voting rules to the log a database needs. I could follow a command as it was appended and committed, then ask whether the next leader would still have it.

what counts as a decision

I'll start with one log slot. Any of N nodes can propose its value. For now, allow the network to lose a message, deliver it late, or deliver it after a newer message; allow a node to crash as well. I want agreement to survive all that: once a correct node decides on a value, no other correct node may decide on a different value for this slot.

There are two other obligations. Validity requires a value that somebody proposed; always returning null cannot satisfy it when nobody proposed null. Termination requires every correct node to decide eventually. Agreement is about safety. Termination is about progress, and its promise will depend on what we assume about message delivery.

three votes out of which five?

Fix the membership at five. A majority now means three votes, including when two members cannot reach the other three. The three-node side can collect enough votes to continue. The two-node side is stuck one vote short. Waiting longer changes neither count.

Now try counting only the machines that answer. The two-node side suddenly needs just two votes, so it can acknowledge writes too. Restoring the link won't retract an acknowledgment from a client that has already acted on it. The failure was in changing the meaning of a majority during the outage.

Name the nodes A through E. Put a write on A, B, and C, then ask C, D, and E to vote next. C is the witness connecting the two groups. Every possible three-node group has at least one such witness. But a witness that forgets on restart is useless. C needs persisted evidence and a voting rule that uses it; merely storing the earlier write does not yet tell C which future votes to refuse.

I can't finish that argument with a timeout. Without a delivery deadline, no reply could mean a crash or just a longer wait. It is reasonable to trigger another election. It is unsafe to conclude that the old leader has ceased to exist. Agreement can remain intact while the protocol waits forever for enough information.

what FLP rules out

The 1985 FLP result makes that last problem precise. Fischer, Lynch, and Paterson consider a deterministic protocol in a fully asynchronous system where even one node might crash. They construct an admissible execution in which a protocol preserving agreement never reaches a decision. It loses the termination guarantee.

The proof keeps the execution bivalent: either decision is still possible. Each carefully chosen delay leaves another way to postpone the deciding step. This is possible even though non-faulty processes keep taking steps and their messages are eventually delivered. No fixed upper bound forces a message to arrive in time to end the indecision.

To recover a progress guarantee, something in that model has to give. Ben-Or uses randomness and proves probabilistic progress under the protocol's stated assumptions. Partial synchrony takes a different route: in one formulation, delays become bounded after an unknown time. A leader can eventually get a long enough stretch of useful communication. The Dwork–Lynch–Stockmeyer paper spells out the timing models behind that argument.

For Paxos and Raft, I separate two claims when reading a design. Late messages must not corrupt an earlier decision. Finishing a new decision requires enough working replicas and communication that cooperates for long enough. Raft's random election timeouts help break repeated split votes, but leave the arbitrary-delay problem in place. I used to blur this. A cluster refusing writes during a partition may be doing precisely what its safety contract requires.

Paxos

In Paxos, C keeps promises and accepted proposals for the next proposer to inspect. I start with Paxos Made Simple, Lamport's 2001 explanation. The original work was written in 1989 and reached the journal in 1998. The distinction I need before following either account is between one acceptor accepting a proposal and a quorum choosing a value.

The proposer puts a value forward, acceptors hold the durable voting state, and learners discover the chosen result. The proposer works in two phases:

1. Prepare and promise. Pick a unique ballot number n and send Prepare(n). An acceptor that promises to reject lower ballots also reports its highest accepted proposal, if it has one. Wait for a quorum of those promises.
2. Accept. Look through the replies for the highest accepted ballot and use its value. Only if none of the replies reports an accepted proposal may the proposer choose its own value. Send Accept(n, value). An acceptor can accept unless it has promised a higher ballot. Once a quorum accepts, the value is chosen.

There is a wrinkle in the usual overlap explanation. After a quorum chooses v at ballot n, the shared acceptor may move on to another ballot. Its next reply need not mention n at all. The proof follows those intervening ballots by induction: any higher proposal that could have been accepted must still carry v. Taking the highest accepted ballot from the prepare replies therefore preserves that value. That value-selection step is doing work the overlap count cannot do alone.

One chosen value is a start. For a database log, Multi-Paxos uses an instance for each slot and lets a stable leader skip a fresh full prepare for every entry. The implementation still has to persist ballots and fill gaps, bring followers up to date, compact old entries, and replace failed leaders. Chandra, Griesemer, and Redstone's Paxos Made Live describes those engineering problems in Google's Chubby service. Lamport's original fictional parliament leaves more of that work to the reader.

Raft

Ongaro and Ousterhout's 2014 Raft paper puts the log and its recovery into the protocol's main explanation. The authors compared student understanding of Raft and Paxos, too. For me, the useful part is being able to keep following the same command when the leader changes.

Each election attempt has a term. A node can vote once in that term, and a candidate needs a majority to win. Two elected leaders in one term would need a shared voter to vote twice. There can be a term with no leader, though. Randomized timeouts help the candidates get out of repeated split votes.

After winning, the leader appends commands and sends them to followers. A current-term entry can be committed when a majority has stored it. That qualification, current-term, is necessary. A majority of copies of an older entry does not give the leader the same permission.

Before voting, a node compares its log with the candidate's. It compares the last entry's term first and uses the index only to break a tie. So a shorter log ending in a later term can beat a longer one. This election restriction and the log-matching and commit rules make future leaders retain the committed prefix. All of them depend on nodes persisting the required state before replying.

why an old entry on a majority can still be unsafe

Figure 8 of the Raft paper gives a counterexample to treating every majority of stored copies as a commitment. This illustrative trace uses five nodes, all starting with a common prefix. The next log position is the disputed one:

1. In term 2, leader A stores x on A and B, then fails before reaching a majority.
2. E wins term 3 with votes from C, D, and E. It appends a conflicting y from term 3, but stores it only on itself before losing contact.
3. A returns and wins term 4 with A, B, and C. Those voters have no term-3 entry. A copies x to C, so the term-2 entry now exists on a majority: A, B, and C.

If A fails again here, E can win a later election with C, D, and E. E's last log term is 3; C's is 2. C can legally vote for E, whose log will replace x with y. The three stored copies did not make the older entry safe to acknowledge as committed.

Instead, A must get an entry from its current term, term 4, stored on a majority. Committing that entry also commits its preceding log prefix, including x. A no-op can supply the new entry when there is no client command to append. Sections 5.4.2–5.4.3 of the paper explain why this rule, the election restriction, and log matching preserve the prefix across every later election.

I put those two snapshots through a small check of the log-freshness predicate. With A and B unavailable, E can get votes from C, D, and E while C ends in term 2. Append the term-4 entry on A, B, and C, and the eligible reachable voters shrink to D and E. Two votes cannot elect a leader in this membership. The check only compares the last log term and index in the stated snapshots; it does not model the full election protocol. It does let me inspect exactly where C's answer changes.

keeping the evidence after the log grows

Compaction removes some of the evidence we have been following. Before dropping a prefix, save its applied state together with the log position it covers. A follower that has fallen far behind can receive this through InstallSnapshot. I would check the interrupted installation too: after restarting halfway through, the node still needs a consistent pair of saved state and covered log position. Otherwise it cannot tell which entries remain to be applied.

Before counting replies I also need the configuration they belong to. Changing the members can leave a majority of the old group disjoint from a majority of the new one. Joint consensus requires both majorities during the transition. Some implementations restrict changes to one member at a time, with the safety rules for that procedure. Either way, changing membership is part of the protocol.

Reads have a leadership problem even when they append nothing. An isolated old leader can believe it still has authority and answer from stale state. For a linearizable read, a leader needs evidence that it still has authority, plus the required committed state already applied. ReadIndex gets quorum confirmation. LeaseRead needs additional assumptions about timing and clocks.

where these protocols show up

Raft appears in etcd, Consul, TiKV, and CockroachDB. Their read and storage paths add choices beyond the core protocol. ZooKeeper takes a different route with Zab, which predates Raft. Zab orders broadcasts through a leader and also has to carry the committed order through leader replacement.

Spanner uses Paxos groups for replication, then combines that with timestamp rules and TrueTime for externally consistent transactions. Cassandra exposes Paxos through lightweight transactions, which clients request for conditional operations. Its classic protocol needs several network phases beyond an ordinary write. I would compare the latency of the requested operation rather than attach one latency claim to the whole database.

Some applications can merge concurrent updates with a CRDT under a different consistency contract. The replicas here have been trusted to obey the protocol even when they crash or recover. Allow them to send contradictory messages and the fault model changes; that is the problem Byzantine protocols address.

I still find replacing the leader just after an acknowledgment the revealing test. In the trace, the question lands on C. With only a term-2 entry it can vote for E and let x disappear. Once a term-4 entry is committed, a later election must pass voters whose persisted state protects x. The client's acknowledgment depends on the votes those nodes will refuse.