The Lineage of Consensus Algorithms

Database replication, cross-service transactions, and blockchain ledgers all require several nodes to agree on a single value. This is the consensus problem.

Unlike 2PC, Paxos has no single point of failure, and Raft kept Paxos's safety while making understandability a design goal. PBFT showed that nodes can reach agreement with practical performance even when some of them send false messages. Tolerating stronger faults costs more nodes and more messages. This article explains why each algorithm's steps lead to safe agreement. Paxos, Raft, and PBFT each come with a simulator that lets you step through their messages.

Watch the video explainer4:01Synthesized narration · burned-in captions

Show transcript

Getting several nodes to agree on a single value: build a distributed system, and sooner or later you'll face this consensus problem. From 2PC to Paxos, Raft, and PBFT, let's follow what each consensus algorithm evolved to solve.

First, the failure model. With crash faults, a node simply stops. It never lies. With Byzantine faults, anything goes: a node may send false messages, tamper with them, or ignore them. To tolerate f failures, you need 2f+1 nodes for crash faults, but 3f+1 for Byzantine faults.

In 1985, FLP proved that in an asynchronous system where one node may crash, no deterministic algorithm can guarantee safety, liveness, and fault tolerance at once. So practical algorithms lean on tools like timeouts: they always preserve safety, and guarantee liveness once the network settles down.

The simplest protocol is two-phase commit, or 2PC. A coordinator sends Prepare to every participant, and if all vote yes, it commits. But if the coordinator crashes after the vote, participants that voted yes are blocked until it recovers, unable to commit or abort. Timing out on their own risks disagreeing with the others. 2PC effectively tolerates zero failures.

Paxos, proposed by Leslie Lamport in 1989, answered this with one idea: majorities. In phase one, a proposer sends Prepare with a number n and collects Promises from a majority of acceptors. In phase two, it sends Accept, and once a majority accepts, the value is chosen. Any two majorities overlap, and a proposer must re-propose the highest-numbered value its promises report, so a chosen value is never overwritten. But Paxos is notoriously hard to understand, extending it to a replicated log isn't obvious, and dueling proposers can stall progress indefinitely.

Raft, published in 2014, made understandability its design goal. It splits consensus into leader election, log replication, and safety. When a node's election timeout fires, it increments the term, becomes a candidate, and becomes leader with a majority of votes. Every write flows from the leader through AppendEntries, and an entry from the current term commits once a majority stores it. And since nodes only vote for candidates whose logs are at least as up to date as their own, committed entries survive into every future leader.

For environments where nodes can lie, PBFT offered a practical answer in 1999. The primary assigns an order, then two rounds of all-to-all messages, Prepare and Commit, each gather 2f+1 matching votes. With n = 3f+1, any two of those quorums share at least f+1 nodes, so at least one honest node is always in both. The price is a message count that grows with the square of the cluster size, so in practice PBFT tops out at a few dozen nodes.

In the real world, Google's Chubby and Spanner run on Paxos, while etcd, CockroachDB, and TiKV run on Raft. Byzantine fault-tolerant consensus lives on in the blockchain world, in Hyperledger Fabric and Tendermint.

Looking back, the stronger the failures you must survive, the more nodes and messages you need. Paxos's difficulty gave birth to Raft: understandability is a design goal in its own right. And always keep safety, guarantee liveness once the network settles: that is the strategy modern consensus algorithms share.

In the article, you can step through Paxos, Raft, and PBFT yourself with interactive simulators.

2PC appeared in 1978, the Byzantine Generals Problem was formulated in 1982, and Paxos, PBFT, and Raft followed. Paxos, PBFT, and Raft, right of the dashed line in the timeline, keep reaching agreement despite failures: Paxos and Raft tolerate crash faults, and PBFT tolerates Byzantine faults.

Fault Models — Crash Faults vs Byzantine Faults

Every consensus algorithm assumes a fault model: a description of how nodes can fail.

Crash Fault: A node suddenly stops and never responds again. Until it stops, it behaves correctly and never sends false messages.
Byzantine Fault: A node can behave arbitrarily, including sending false messages, tampering with messages, or ignoring requests.

Crash faults are a special case of Byzantine faults, so an algorithm that tolerates Byzantine faults also tolerates crash faults. The cost is more nodes and more messages.

Fault Model	Required Nodes	Node Behavior
Crash Fault	2f + 1 (tolerates f failures)	Only stops; never lies
Byzantine Fault	3f + 1 (tolerates f failures)	Can behave arbitrarily

The FLP Impossibility Theorem — The Limits of Consensus in an Asynchronous Model

In 1985, Fischer, Lynch, and Paterson proved the following theorem.

FLP Impossibility Theorem: In an asynchronous model where even one node can crash, no deterministic algorithm can simultaneously guarantee Safety, Liveness, and Fault Tolerance.

Practical algorithms reach consensus by relaxing one of the theorem's assumptions:

Randomization: Introducing randomness into proposer election, which guarantees liveness probabilistically
Partial Synchrony Model: Assuming that after some point (GST: Global Stabilization Time), messages arrive within a bounded delay
Failure Detectors: Using imperfect failure detection based on timeouts

Paxos and Raft always guarantee safety and guarantee liveness once the network has been stable for long enough.

2PC — The Simplest Agreement

Two-Phase Commit (2PC) is the basic protocol for distributed transactions. A Coordinator obtains agreement from all participants in two phases: Prepare → Commit.

Problems with 2PC

2PC is simple, but because it depends on a single Coordinator, it has these weaknesses:

Blocking: If the Coordinator crashes, participants that already voted Yes wait indefinitely for the Commit/Abort decision. A participant that times out and aborts on its own may end up with a different outcome from the others.
Zero Fault Tolerance (f=0): A single Coordinator crash halts the entire system. The Coordinator is a single point of failure.

Paxos reaches agreement as long as a majority of Acceptors is running, so it keeps working when a minority of them stops.

Paxos — The Theoretical Foundation of Consensus

Paxos, proposed by Leslie Lamport in 1989, became the theoretical foundation for crash-fault-tolerant consensus algorithms. Google's Chubby lock service and Spanner use it.

Paxos's Three Roles

Proposer: Proposes a value. Each proposal carries a unique proposal number.
Acceptor: Decides whether to accept a proposal. Agreement is reached when a majority accepts the same value.
Learner: Receives the agreed-upon value and applies it to the state machine. The rest of this section focuses on the interaction between Proposers and Acceptors.

Single-Decree Paxos Protocol

Paxos operates in two phases. 2PC also has two phases, but Paxos moves forward once a majority responds instead of waiting for everyone.

Phase 1 — Prepare/Promise:

A Proposer selects a proposal number n and sends Prepare(n) to all Acceptors
If n is the highest seen, an Acceptor replies with Promise(n, previously accepted value)

Phase 2 — Accept/Accepted:

After receiving a majority of Promises, the Proposer sends Accept(n, v)
- If any Promise includes a previously accepted value, it must choose the value with the highest proposal number
- Otherwise, it proposes its own value
If the Acceptor hasn't made a Promise for a higher number, it replies Accepted(n, v)

Paxos Simulator

Step through Single-Decree Paxos with different scenarios.

Scenario:

PreparePromiseAcceptAccepted

Initial state: N1 is the Proposer and N2–N5 are Acceptors. N1 starts consensus with proposal number n=1.

[1] N1 begins consensus as Proposer

Step 1 / 51 / 5

Why Paxos Is Safe

Paxos's safety rests on ordering by proposal number.

Acceptors reject Accept for any proposal number smaller than the highest Promise they've made
Proposers adopt previously accepted values included in Promises

These two constraints ensure that once a majority has accepted a value, no later proposal can override it. This is the Paxos safety theorem.

Challenges with Paxos

Paxos is correct, but hard to understand and implement.

Hard to Understand: Lamport's original paper "The Part-Time Parliament" is written as an allegory about an ancient Greek parliament, and many researchers struggled with it. Lamport later explained the algorithm again in "Paxos Made Simple".
Non-Obvious Extension to Multi-Paxos: Single-Decree Paxos decides only one value. The paper does not specify how to extend it to practical log replication (Multi-Paxos), so each implementation developed its own optimizations.
Liveness Issues (Livelock): Two Proposers that keep outbidding each other with higher proposal numbers can prevent agreement indefinitely (the "Proposer Conflict" scenario in the simulator shows one such preemption, where a Prepare with a higher proposal number displaces an earlier proposal).

Raft — Redesigned for Understandability

Raft, published by Diego Ongaro and John Ousterhout in 2014, was designed to be as safe as Paxos but far easier to understand.

Raft's Design Approach

Raft pursues understandability through two choices:

Problem Decomposition: It treats consensus as three separate problems: leader election, log replication, and safety.
Strong Leader: All writes go through the Leader, and log entries flow in one direction, from the Leader to the Followers.

Raft's State Transitions

Each node has three states: Follower, Candidate, and Leader.

Leader Election

All nodes start as Followers
A node whose election timeout expires becomes a Candidate and increments its term
It votes for itself and sends RequestVote RPCs to other nodes
Upon receiving a majority of votes, it becomes Leader
The Leader periodically sends heartbeats (empty AppendEntries) to reset election timeouts

Election Restriction: A node grants its vote only if the candidate's log is at least as up-to-date as its own (compare the last log term first, then the last log index). Together with the commitment rule below, this ensures that a node missing a committed entry cannot become Leader in a later term.

Log Replication

The Leader appends client writes to its log
The Leader sends log entries to all Followers via AppendEntries RPC
For entries from the Leader's current term, once a majority responds → commit (apply to state machine)

A Leader must not commit an entry from a previous term merely by counting replicas. Older entries become committed only indirectly, when the Leader commits at least one entry from its current term on a majority.

AppendEntries keeps logs consistent through its prevLogIndex / prevLogTerm checks (Log Matching): if two logs contain an entry with the same index and term, all preceding entries are identical.

These rules preserve the Leader Completeness Property: once committed, an entry appears in the log of every future Leader.

Membership changes use overlapping majorities so that the old and new configurations cannot choose different Leaders. The paper uses joint consensus; some implementations use the later one-server-at-a-time variant.

Raft Simulator

Visualize Raft's leader election, log replication, and fault tolerance.

Scenario:

Replicated Log

empty

RequestVoteVote / OKAppendEntries

Initial state: all nodes are Followers at term=0, and there is no Leader yet. Each node has an election timeout; when it expires, the node becomes a Candidate.

[1] All nodes start as Followers

Step 1 / 51 / 5

Raft vs Paxos

Aspect	Paxos	Raft
Leader role	Optimization	Required
Log flow	Any Proposer → Acceptor	Leader → Follower (unidirectional)
Understandability	Notoriously difficult	A primary design goal
Safety proof	Equivalent	Equivalent
Adoption	Chubby, Spanner	etcd, CockroachDB, TiKV

PBFT — Byzantine Fault Tolerance

Paxos and Raft handle only crash faults. Where nodes can send false messages, a protocol that tolerates Byzantine faults is needed.

In 1999, Miguel Castro and Barbara Liskov proposed PBFT (Practical Byzantine Fault Tolerance), which showed that Byzantine-fault-tolerant consensus can run with practical performance.

The PBFT Protocol

PBFT operates in three phases.

Pre-prepare: The Primary (equivalent to a leader) assigns a sequence number to the request and sends it to all other nodes
Prepare: Each backup (every node except the Primary) that receives the Pre-Prepare sends a Prepare message to all other nodes (all-to-all communication)
Commit: Once a node, the Primary included, holds the Pre-Prepare and $2f$ matching Prepare messages ( $2f+1$ in total), it sends a Commit message to all other nodes

The Prepare phase (counting the Pre-Prepare) and the Commit phase each collect $2f+1$ matching messages. With $n = 3f + 1$ , any two such quorums share at least $f+1$ nodes, so even if $f$ nodes are Byzantine, at least one shared node is correct.

Why 3f+1 Is Required

With $n$ total nodes and $f$ Byzantine nodes, there are $n - f$ honest nodes. To make progress even when the Byzantine nodes stay silent, the honest nodes alone must be able to supply $2f+1$ messages:

$n - f \geq 2f + 1 \implies n \geq 3f + 1$

With 4 nodes, the system tolerates $f=1$ ; with 7 nodes, $f=2$ Byzantine failures.

PBFT Simulator

Step through PBFT's three phases with zero, one, or two Byzantine nodes.

Scenario:

Pre-preparePrepareCommitByzantine message

PBFT normal case: 4 nodes (n=3f+1, f=1). N0 is the Primary and N1–N3 are Backups (the other nodes). A client request arrives.

[1] 4-node PBFT (f=1): tolerates up to 1 Byzantine fault

Step 1 / 41 / 4

Challenges with PBFT

$O(n^2)$ Message Complexity: Because of all-to-all communication, message volume grows quadratically with node count
Scalability: In practice, the limit is on the order of tens of nodes
View Change Complexity: The protocol for replacing a faulty Primary is complex

Algorithm Comparison

Algorithm	Fault Model	Fault Tolerance	Message Complexity	Latency (communication steps to commit)	Use Case
2PC	Crash	0	O(n)	2 (Prepare → Vote)	Databases
Paxos	Crash	f < n/2	O(n)	4 (Prepare → Promise → Accept → Accepted); 2 for Multi-Paxos with a stable Leader, since only Phase 2 runs	Chubby, Spanner
Raft	Crash	f < n/2	O(n)	2 (AppendEntries → response)	etcd, CockroachDB
PBFT	Byzantine	f < n/3	O(n²)	3 (Pre-prepare → Prepare → Commit)	Blockchain

A step is one one-way message delay; messages sent in parallel count as one step. With no failures, steps run from the first message sent by the Coordinator (2PC), Proposer (Paxos), Leader (Raft), or Primary (PBFT) until that node knows the request is committed. Client requests and replies are excluded, and Raft and PBFT assume an established Leader or Primary.

Real-World Adoption

Paxos Family

Google Chubby: Distributed lock service using Multi-Paxos.
Google Spanner: Globally distributed database using Paxos for replication.
Apache ZooKeeper: Uses the Zab protocol (a Paxos variant).

Raft Family

etcd: Kubernetes backend store. Uses Raft for consistency.
CockroachDB: Distributed SQL database. Each Range is a Raft group.
TiKV: Distributed KV store (storage layer of TiDB). Uses Raft.
Consul: Service mesh control plane. Uses Raft for consensus.

PBFT Family

Hyperledger Fabric: Enterprise blockchain. Versions up to v0.6 used PBFT. From v1.0, Fabric moved to a crash-fault-tolerant ordering service built on Kafka, and v1.4.1 added Raft. v3.0 also offers a BFT ordering service built on the SmartBFT library, which is based on the BFT-SMaRt protocol; Raft remains available.
Tendermint: Blockchain consensus engine. A PBFT variant.

Summary

Tracing the algorithms from 2PC to PBFT shows that tolerating stronger faults requires more nodes and more messages. Crash faults need $2f+1$ nodes; Byzantine faults need $3f+1$ nodes and all-to-all communication.

Raft was a response to the difficulty of Paxos: it keeps the same safety while making understandability and ease of implementation a design goal. It is now used in etcd, CockroachDB, TiKV, and other systems.

The FLP impossibility theorem shows that in an asynchronous model, no deterministic algorithm can guarantee safety, liveness, and fault tolerance together. Practical systems work around this with timeouts and randomization: Paxos, Raft, and PBFT always preserve safety and guarantee liveness once the network has been stable for long enough.

References

Lamport, L. "The Part-Time Parliament". ACM TOCS, 1998.
Lamport, L. "Paxos Made Simple". 2001.
Ongaro, D. and Ousterhout, J. "In Search of an Understandable Consensus Algorithm". USENIX ATC, 2014.
Castro, M. and Liskov, B. "Practical Byzantine Fault Tolerance". OSDI, 1999.
Fischer, M., Lynch, N., and Paterson, M. "Impossibility of Distributed Consensus with One Faulty Process". JACM, 1985.
Lamport, L., Shostak, R., and Pease, M. "The Byzantine Generals Problem". ACM TOPLAS, 1982.