Skip to content

10. Consensus algorithms — how distributed systems agree without trusting timing

⏱️ Estimated time: 18 min | Level: advanced

ELI5 callback: The town crier pins one notice on the bulletin board. The board rules decide delivery, and the town directory helps readers find it.

Why agreement is hard once machines can delay or disappear

Distributed systems fail by delay, duplication, and split views. Two nodes may each think the other one died. See. Without agreement, both may accept conflicting writes. Consensus exists to let a cluster choose one safe history. It requires quorums, durable logs, and careful leadership rules. That cost is high, but the alternative is worse. Diagram: 

node A sees timeout        node B sees timeout
each side suspects failure independently
write accepted here?      write accepted there?
+--------- network partition ---------+
quorum rule decides which side may continue
the losing side must stop pretending

  1. A client asks to append a new value.
  2. One replica times out talking to another.
  3. Local guesses are no longer enough.
  4. The cluster needs a shared safety rule.
  5. Consensus supplies that rule through quorum-backed decisions.
  6. Failure detection is never perfect.
  7. Safety matters more than immediate progress.
  8. Durable logs matter because memory forgets on restart.
  9. Quorums prevent one noisy node from inventing history. Consensus begins where trust in timing ends.

Raft makes the core flow easier to reason about

Raft organizes nodes into leader, followers, and candidates. One elected town crier proposes the next state change. Each replicated notice carries term, index, and command data. Followers append entries and acknowledge them. An entry commits after a majority stores it. Raft is popular because the flow is teachable. Now watch. Diagram: 

client -> leader -> followers
append entry -> replicate -> ack majority
commit index advances after quorum
followers apply only committed entries
old leader with stale term must step down
elections choose a new leader when needed

  1. The leader receives a command.
  2. It appends the entry locally first.
  3. It sends AppendEntries to followers.
  4. A majority acknowledges the entry.
  5. Only then does the leader mark it committed.
  6. Terms prevent stale leadership from lingering.
  7. Commit needs a majority, not good feelings.
  8. Followers stay mostly simple by design.
  9. Heartbeats are lightweight proofs of current leadership. Raft is simple enough to teach, not simple enough to wing.

Paxos solves the same safety problem with a different mental model

Paxos talks in proposers, acceptors, and learners. It focuses on choosing one value safely despite unreliable timing. The language feels heavier than Raft, but the safety goal is similar. See. Proposal numbers prevent older proposals from overwriting newer promises. Acceptors promise before they accept. Learners observe what value actually won. Diagram: 

proposer -> prepare(n) -> acceptors
acceptors -> promise(n) -> proposer
proposer -> accept(value,n) -> acceptors
majority accepted -> learners discover chosen value
higher proposal numbers can supersede stalled attempts
safety holds even when retries happen repeatedly

  1. A proposer sends Prepare with a proposal number.
  2. Acceptors promise not to accept lower numbers later.
  3. The proposer picks the safe value to continue with.
  4. It sends Accept requests using that same number.
  5. A majority acceptance makes the value chosen.
  6. Paxos prizes safety under ugly timing assumptions.
  7. The protocol is smaller than its reputation suggests.
  8. Multi-Paxos adds a stable leader for efficiency.
  9. Implementation clarity matters as much as theory knowledge. Do not fear Paxos; fear an incomplete implementation of Paxos.

Quorums, terms, and logs are the non-negotiable safety machinery

The replicated log acts like a guarded bulletin board. But not every appended entry is committed immediately. Quorum checks, term comparisons, and commit indices are board rules. These rules stop stale leaders from overwriting safe history. Leases alone are not enough. Durability depends on what a majority has accepted. Simple, no? Diagram: 

append locally != committed globally
majority stored entry -> eligible to commit
stale term -> reject leadership claim
conflicting suffix -> overwrite only under protocol rules
snapshot and compaction keep logs manageable
safety comes from intersections of majorities

  1. Entry 42 reaches one follower only.
  2. The leader crashes before quorum acknowledgment.
  3. Entry 42 is not safely committed yet.
  4. A new leader may replace that uncommitted tail.
  5. Committed entries survive because quorums intersect.
  6. Committed and merely replicated are different states.
  7. Majority intersection is the heart of safety.
  8. Compaction must preserve the committed prefix.
  9. Client acknowledgments should follow commit, not wishful append. The protocol sounds strict because data loss is expensive.

Consensus gives ordered truth, not total system perfection

Clients still need a town directory or redirect path to the leader. Consensus picks a safe history, not a perfect user experience. It does not remove latency from distant regions. It does not make non-idempotent clients magically safe. Snapshotting, compaction, and membership changes remain hard. So what to do? Use consensus only for data that truly needs one agreed order. Diagram: 

client hits follower -> redirect to leader
leader changes -> clients refresh routing info
snapshots trim old log safely
membership changes follow controlled joint rules
wide area latency still shapes commit speed
consensus protects order, not every product requirement

  1. Put metadata, locks, or config changes behind consensus.
  2. Keep bulky analytics streams outside that hot path.
  3. Test leader failover under load.
  4. Rehearse snapshot restore and member replacement.
  5. Explain to clients what errors are retryable.
  6. Consensus is for the small set of truly critical decisions.
  7. Overusing it adds latency and operational weight.
  8. Client retry logic still matters a lot.
  9. Safe ordering is valuable precisely because it is expensive. Use the hammer where nails exist, not on every screw.

Where this lives in the wild

  • etcd, where Raft protects cluster metadata and service coordination.
  • Apache ZooKeeper, where Zab-style consensus coordinates shared state.
  • Kafka KRaft mode, where controller metadata needs agreed ordering.
  • CockroachDB, where consensus-backed replicas protect transactional ranges.
  • Consul, where cluster membership and key metadata rely on agreement.

Pause and recall

  • Why can two healthy-looking nodes still disagree about the world?
  • What does a majority give that a timeout cannot give?
  • Why is a replicated entry not always a committed entry?
  • When should you avoid putting a workload behind consensus?

Interview Q&A

Q: What does a consensus algorithm guarantee at a high level? A: It guarantees that replicas can agree on one safe ordered history despite crashes and timing uncertainty. Common wrong answer to avoid: "It guarantees zero latency and perfect availability under every failure."

Q: Why is quorum central to consensus? A: Because intersecting majorities preserve safety when leaders change and messages arrive late. Common wrong answer to avoid: "Quorum is only about performance tuning, not correctness."

Q: Why do people say Raft is easier than Paxos? A: Because its roles and leader-driven flow are easier to visualize, even though implementation still demands rigor. Common wrong answer to avoid: "Raft is trivial, so production code can skip many edge cases."

Q: What does consensus not solve for you? A: It does not solve client idempotency, global low latency, or every application-level workflow concern. Common wrong answer to avoid: "Once you add consensus, the distributed system becomes simple everywhere."

Apply now (5 min)

Take a three-node metadata service. Write the quorum size and the client write acknowledgment rule. Sketch one leader failover where an uncommitted entry disappears. Then sketch one committed entry that must survive the failover. List which data in your system truly deserves consensus. Add one client redirect rule for follower responses. Now watch safety and latency become separate design questions.

Bridge. Consensus gives us agreement. But no system is perfect — next we tackle leader election. → 11