The idea: two answers to one question

Five servers must agree on one replicated log: the same values in the same order, even when servers crash. Multi-Paxos (Lamport, 1989/1998) and Raft (Ongaro and Ousterhout, 2014) both solve it with a leader and majorities of 3 out of 5, so any two majorities share a server. The page runs both on the same five servers, with the same election timeouts and the same client writes, on one clock: Raft on the left, Multi-Paxos on the right. Every message takes one tick.

The scoreboard counts three things: the ticks from the start of an election to a working leader (a majority, the leader included, has answered its first AppendEntries or Accept), the messages sent, and the elections (Raft) or ballots (Paxos) tried. Each server shows its role, its term or promised ballot, its log (value plus term, or value plus ballot; green = committed or chosen, yellow = not yet) and its election timer.

Two side-by-side sequence diagrams. Raft: the candidate sends RequestVote with term 2, last index and last term, followers answer vote yes only if their log is not newer; then AppendEntries with term, prev and entries, answered ok. Multi-Paxos: the proposer sends Prepare with ballot 2.4 for slots 2 on, acceptors answer Promise plus what they accepted; then Accept with ballot 2.4, slot 2, value z, answered Accepted.
Both protocols elect a leader with one round trip to a majority, then spend one more round trip per write: a term is a ballot and a log index is a slot.

With a stable leader there is no difference at all (Demo: stable leader, 3 writes): each write costs 4 ticks (client → leader → followers → leader → client) and 10 messages in both lanes. The differences are all in how a new leader is chosen and what it does with the log it inherits.

Raft: terms, votes, one log

  • Terms. Time is cut into numbered terms with at most one leader each. A follower whose election timer fires adds 1 to the term, becomes a candidate, votes for itself and sends RequestVote(term, lastLogIndex, lastLogTerm).
  • One vote per term. A server votes for the first candidate it hears from in a term, and only if the candidate's log is at least as up to date as its own: a later last term, or the same last term and at least as long. This election restriction means the winner already holds every committed entry, so a vote never carries log entries.
  • AppendEntries carries the entries with the index and term of the entry before them. A follower whose log does not match there says no, and the leader moves back one entry (Demo: a stale server times out first, S5). A follower drops any entry that conflicts with the leader's.
  • Commit. An entry of the leader's own term stored on a majority is committed; older entries are committed with it.
  • Randomized timeouts. Each server draws a new timeout every time it restarts its timer, so after a split vote one candidate usually times out well before the other.

Multi-Paxos: ballots, promises, slots

  • Ballots. A ballot is a number no other server can pick: here round.id, so S4's ballots are 1.4, 2.4, 3.4… and 2.1 < 2.4 < 3.1. A would-be leader picks a round above any it has seen.
  • Phase 1 for all slots at once. Prepare(ballot, first slot not known chosen). An acceptor that has promised nothing higher promises to ignore lower ballots and reports every value it has accepted from that slot on; otherwise it answers Nack. This is the "Multi" in Multi-Paxos: single-decree Paxos (see Paxos) runs phase 1 for every value; a stable leader runs it once.
  • Any server can lead, even one with an old log, because the Promises tell it what may already be chosen. For each slot it must propose the reported value with the highest ballot again, under its own ballot; only free slots get new values.
  • Phase 2 per write. Accept(ballot, slot, value); a value accepted by a majority with the same ballot is chosen.
  • No election rule. Paxos is safe with any number of proposers, but it does not say who should propose or when to retry. Real systems add a leader-election module, random backoff or leases; the page uses the simplest rule (retry at once after a Nack) to show why that is needed.

A leader crash: who may win, and what happens to unfinished entries

In Demo: leader crash, y only on S2, the leader S1 sends a new entry y to S2 only and crashes; S3 times out first. Both lanes have a working leader S3 after 9 ticks, with the same number of messages. The logs end up different:

Before: S2 holds x and an uncommitted y, S3 and S4 hold x. Raft: S2 refuses S3's RequestVote because its log is longer; S3 wins with S4 and S5, its next entry z goes to index 2 and S2 drops y; the log is x z. Multi-Paxos: S2's Promise reports slot 2 = y with ballot 1.1, S3 proposes y again under its own ballot, z goes to slot 3; the log is x y z.
Raft's new leader overwrites an uncommitted entry it does not have; a Paxos leader re-proposes every value a Promise reports. Both are correct: y was never acknowledged.

Paxos keeps y here only because S2's Promise was among the first three answers; had S3 heard from S4 and S5 first, y would be lost just as in Raft. Either way the client never got OK for y, so it must retry, and real systems tag requests with an id so a retry is not applied twice.

The election restriction costs time when the wrong server times out first. In Demo: a stale server times out first, S5 was down while y was written. In Raft, S2, S3 and S4 refuse it, and the next election (S3, term 3) gives a working leader after 10 ticks and 2 elections. In Paxos, S5 simply becomes leader: the Promises tell it about y, it re-proposes it, and it works after 8 ticks with 1 ballot and fewer messages (14 against 23 for the election). The price is bigger messages: the Promises carry log entries, and in a real system that can be a long suffix.

Two candidates at once

Demo: two time out together (S3 down) makes S1 and S5 time out in the same tick. In Raft, S2 votes for S1 and S4 votes for S5: a split vote, 2 against 2, nobody wins term 2. The next timeouts are random (S5 draws 4, S1 draws 8), so S5 starts term 3 alone and wins: a working leader after 13 ticks and 3 elections.

In Paxos, ballot numbers break the tie at once (2.5 beats 2.1), but the loser retries at once with 3.1, whose Prepare reaches the acceptors in the same tick as S5's Accept 2.5. The acceptors promise 3.1 first and reject the Accept; S5 retries with 4.5 and knocks out 3.1 the same way. This livelock (duelling proposers) is safe, since nothing wrong is ever chosen, but makes no progress: the page stops it after 8 ballots, with no working leader.

Time flows down. S1 sends Prepare 2.1 and S5 Prepare 2.5; the acceptors Nack 2.1 and promise 2.5; S5 sends Accept 2.5 while S1 sends Prepare 3.1, which arrives first, so the acceptors Nack the Accept; S5 sends Prepare 4.5 at once and S1's Accept 3.1 is Nacked; and so on, nothing is chosen.
Two proposers that retry at once keep pre-empting each other: every Accept arrives just after a higher Prepare, so Paxos stays safe but chooses nothing.

The same tie-break order (a Prepare handled before an Accept arriving in the same tick) is unlucky on purpose; in a real network it happens by chance, and with fixed retry timers it can happen again and again. Raft builds the cure into the protocol: one vote per term stops two leaders in a term, and random timeouts make a repeat split unlikely.

Which one?

RaftMulti-Paxos
steady state (one write)1 round trip, 4 ticks, 10 messagesthe same
who can become leaderonly a server with an up-to-date logany server
election messagessmall (term, last index, last term)Promises carry accepted values
new leader's logalready complete; it overwrites followers' extra entriesfilled in from the Promises, re-proposed under its ballot
log holesnever: entries are appended in orderpossible (slots chosen out of order); filled with no-ops
competing candidatesone vote per term + random timeoutsnot specified: add backoff, a leader election or leases
specificationone paper with membership changes, snapshots and client rulesa family of variants; many details left to the implementer
used inetcd, Consul, CockroachDB, TiKV, Kafka KRaftChubby, Spanner, Megastore, many custom systems

In practice the choice is rarely about speed. Raft is easier to implement and to check against its paper; Paxos-based designs give more freedom (any leader, out-of-order slots, variants such as EPaxos or Flexible Paxos). Howard and Mortier showed that, written in the same terms, the two differ mainly in how they elect a leader.

See also Raft (elections, log repair, partitions on one cluster), Paxos (single-decree Paxos step by step), Leader Election (Bully, ring and lease-based election) and Kafka KRaft (a Raft-style quorum in practice).

What the page leaves out

Heartbeats are not drawn and timers only run during an election; messages take exactly one tick and are never reordered or duplicated; the client always knows the leader. Left out: Raft's no-op entry at the start of a term, pre-vote and leader leases, log compaction and snapshots, membership changes (joint consensus), Paxos learners as separate roles, out-of-order slots and no-op filling beyond the simplest case, batching and pipelining, Fast/Flexible/EPaxos, and Byzantine faults (see PBFT).