Consensus Algorithms: Paxos and Raft Basics For students.

30 September 2026Engineering Try the interactive 3D model →

A consensus algorithm lets a group of computers agree on a single value even when some crash or the network misbehaves. Imagine five servers running a database: a client writes "balance = 500", and consensus makes sure every surviving server eventually agrees the balance is 500 — not 400 on one machine and 600 on another. Paxos and Raft are the two classic algorithms solving this problem.

It matters because agreement is the foundation of every reliable distributed system. Databases, configuration services, leader election and blockchains all need a group of machines to settle on one truth.

Key Concepts

Quorum (majority) — the minimum servers that must agree: floor(N/2) + 1 for N servers. Any two majorities overlap in at least one server, which prevents split decisions.
Leader (Raft) — one elected server handles all writes and replicates them to followers; if it dies, followers elect a new one.
Term (Raft) — a logical clock number increasing with each election; servers reject messages from old terms, stopping a dead leader from causing confusion after recovery.
Proposer / acceptor (Paxos) — Paxos splits roles: proposers suggest values, acceptors vote, reaching agreement in two phases (prepare/promise, then accept/accepted).
Log replication — both algorithms keep an ordered log of commands on every server; once a majority commits an entry, it is permanent and survives crashes.

Formulas

Quorum size: Q = floor(N/2) + 1. For N = 5, Q = 3; for N = 7, Q = 4. A write commits only after Q servers acknowledge it.
Fault tolerance: N servers survive F = floor((N − 1)/2) failures and keep working. Five servers tolerate 2 failures; seven tolerate 3.
Why majorities work: any two quorums share at least 2Q − N servers (≥ 1). With N = 5, Q = 3, any two majorities share at least one server, so a new leader always finds the latest committed value.

Worked Example

A Raft cluster has 7 servers. Two crash during an outage. Can it still elect a leader and commit writes? What if 4 crash?

Quorum: Q = floor(7/2) + 1 = 4. A leader needs 4 votes; a write needs 4 acknowledgements.
With 2 crashed, 5 remain — more than the quorum of 4, so the survivors elect a leader and keep committing writes.
With 4 crashed, only 3 remain — fewer than 4, so no leader can be elected and no writes commit. The cluster correctly stops rather than risking two sides disagreeing.
Check: F = floor((7 − 1)/2) = 3, so the cluster survives up to 3 failures — consistent with the answers above.

Common Misconceptions

"Consensus means all servers must agree." Only a majority must. Requiring every server would halt the system on a single crash; majority quorums are the whole point.
"Consensus makes the system always available." During a network split, only the side holding a majority keeps working; the minority must refuse writes to stay safe.

Real-World Applications

etcd and Consul: use Raft to store cluster configuration and service discovery data reliably.
Databases: CockroachDB, TiDB and MongoDB replica sets use Raft-like consensus to keep replicas consistent.
Kubernetes: its API server state lives in etcd, so Raft quietly underpins every Kubernetes cluster.

Consensus turns a crowd of unreliable machines into one reliable decision-maker. Remember the quorum rule — majority wins, minorities wait — and you understand the beating heart of etcd, modern databases and every system that must never disagree with itself.