Consensus Algorithms: Paxos and Raft

How a group of servers agrees on one value, or one ordered log, even when some of them crash: the problem, how Paxos and Raft solve it, and what it costs.

Overview

The problem

Consensus means getting several servers to agree on one value and never change their minds, even when some servers crash or messages are slow. That sounds small, but many hard problems reduce to it. Picking a single leader is agreeing on who leads. Committing a distributed transaction is agreeing on commit or abort. Keeping replicas in step is agreeing on the order of every write.

A correct consensus algorithm gives three promises. Agreement: no two servers decide different values. Validity: the decided value was actually proposed by someone. Termination: every server that does not crash eventually decides. The first two are about safety (nothing bad happens); the third is about liveness (something good eventually happens).

Leader election — Which server is the leader for this term
Atomic commit — Commit or abort, the same answer on every participant
Replicated log (total order broadcast) — Which entry goes in each log slot, in the same order everywhere
Lock or lease service — Which client holds the lock right now

In practice, systems do not run consensus once. They run it for every slot of a replicated log. Each server applies the log, in order, to its own copy of a state machine (a key-value map, for example). Same starting state plus same log in the same order gives the same result on every server.

Majorities are the core trick

Every practical algorithm uses a quorum: a majority of the servers. Any two majorities of the same group share at least one server. So if a value was accepted by one majority, any later majority contains a server that knows about it. That shared server is what stops two different decisions.

The price is that a majority must be reachable to make progress. A cluster of N servers needs floor(N/2) + 1 of them.

3 — 2 — 1
4 — 3 — 1
5 — 3 — 2
7 — 4 — 3

A fourth server adds no fault tolerance over three; it only adds one more server that must answer. That is why clusters use odd sizes, and why the etcd docs say five servers (which survive two failures) are enough in most cases and a cluster should probably have no more than seven: every write waits for a majority, so more servers means slower writes.

Paxos

Leslie Lamport's Paxos was the first widely known solution. His paper The Part-Time Parliament was published in 1998 after years unpublished, and his short restatement, Paxos Made Simple, appeared in 2001. Paxos has three roles: proposers suggest values, acceptors vote, and learners find out what was chosen. One server usually plays all three.

A single round of basic Paxos runs in two phases. Each proposal carries a number, and higher numbers win.

The key rule is in the middle: if any acceptor already accepted a value, the proposer must propose that value, not its own. That rule is what makes a chosen value stick.

Paxos is safe even with competing proposers, but two proposers can keep interrupting each other with higher numbers, so neither finishes. Lamport's fix is a distinguished proposer, in effect a leader. Once a stable leader exists, it can skip phase 1 for later log slots, which is the idea usually called Multi-Paxos. Lamport's papers leave many practical details (leader changes, membership changes, log compaction) to the implementer, which is a big reason Paxos is known as hard to build.

Raft

Raft (Ongaro and Ousterhout, 2014) was designed to be easier to understand than Paxos while giving the same guarantees. It splits the problem into three parts: leader election, log replication and safety. A server is always in one of three states.

Terms and elections

Time is divided into numbered terms. Each term has at most one leader. A follower that hears no heartbeat for its election timeout becomes a candidate, adds one to the term, votes for itself and asks the others for votes. A server gives at most one vote per term, and only to a candidate whose log is at least as up to date as its own (compare the term of the last entry first, then the log length). A candidate with a majority wins.

If two candidates split the votes, both time out and try again. Raft makes this rare by picking each timeout at random from a range. The paper suggests a range such as 150 to 300 ms, and it reports that without randomness elections consistently took more than 10 seconds because of repeated split votes.

Log replication

The leader appends each client command to its log and sends it to the followers. Once a majority has stored the entry, the leader marks it committed, applies it and answers the client. Followers learn the commit point with the next message.

Safety

The voting rule means a new leader always has every committed entry, because a committed entry is on a majority, and a candidate needs a vote from a majority, and those groups overlap. Raft adds one subtle rule: a new leader never counts replicas to commit an entry left over from an older term. It commits an entry from its own term, and the older entries before it become committed along with it.

What consensus costs

Every write waits for a majority — One network round trip plus a disk flush on each server before the client hears back
All writes go through one leader — The leader's CPU, disk and network cap write throughput
No progress without a majority — A minority side of a network split cannot accept writes
A pause after a leader dies — Roughly one election timeout before a new leader takes over
Reads need care — A leader that was cut off may not know it lost its job, so a linearizable read must confirm leadership first

The theory also sets a limit. Fischer, Lynch and Paterson proved in 1985 (the FLP result) that in a fully asynchronous system, where messages can be delayed without bound, no deterministic algorithm can guarantee consensus terminates if even one process may crash. Paxos and Raft never give a wrong answer, but they only promise progress when the network behaves well enough for a leader to stay in place. Raft states this as a timing rule: the time to reach all servers should be much shorter than the election timeout, which should be much shorter than the typical time between server failures.

What you will be able to do

Say what consensus is and name four problems that reduce to it.
Explain why majorities make agreement safe, and size a cluster for a number of failures.
Walk through the two phases of Paxos and why a proposer must reuse an accepted value.
Walk through a Raft election and a Raft write, step by step.
State what consensus costs, and what the FLP result does and does not mean.

Key concepts

Consensus: A group of servers deciding one value, with no two servers deciding differently, even when some crash.
Quorum: A majority of the servers, floor(N/2) + 1. Any two majorities overlap, which is what keeps decisions consistent.
Replicated log: An ordered list of commands that every server stores and applies in the same order, so every copy reaches the same state.
Term (Raft): A numbered period with at most one leader. A server that sees a higher term updates its own and steps down if it was leader.
Election timeout: How long a follower waits without hearing from a leader before it starts an election. Randomized so that two followers rarely start at once.
Committed entry: A log entry stored on a majority. Raft guarantees it will be in the log of every future leader.
Proposal number (Paxos): A unique, ordered number on each Paxos proposal. Acceptors promise to ignore anything numbered lower than the highest they have seen.
FLP result: The 1985 proof that no deterministic algorithm can guarantee consensus finishes in a fully asynchronous system with even one possible crash.

When to use it

Explaining how etcd, ZooKeeper or Kafka in KRaft mode keep their metadata consistent.
Choosing a replicated store for data where two servers must never disagree, such as leader identity, locks or configuration.
Contrasting a Raft group with plain single-leader replication, where failover is decided by timeouts and can split the brain.
Sizing a cluster: how many servers you need to survive one or two failures, and what each extra server costs in write latency.

Interview questions

Walk through what happens in Raft when the leader crashes.
Why must a consensus cluster have a majority to make progress? What happens in a network split?
How is Paxos different from Raft?
What does the FLP impossibility result mean in practice?
Why is total order broadcast the same problem as consensus?