Notesdistributed🌱 seedling

Consensus

Also: Distributed Consensus · Consensus Algorithm · State Machine Replication · Replicated State Machine

Getting a group of nodes to agree on one value (or one log, entry by entry) even though some may crash and the network may delay messages. Safety always holds; progress needs a majority up and a network that's usually timely.

Also in: Consensus › Majorities and terms

Why it exists

Failover, locks, uniqueness and configuration all need "exactly one" answer that every node accepts. Timeouts and scripts can be fooled by a slow network into Split Brain; consensus can't.

How it works

  • Properties: agreement (no two nodes decide differently), integrity (decide once), validity (the value was proposed), termination (non-crashed nodes eventually decide).
  • Majority quorums: a decision needs more than half the nodes; any two majorities overlap, so later decisions always learn of earlier ones. Terms / ballots / epochs number each leadership period, and messages from older terms are rejected.
  • A log of decisions is Total Order Broadcast; deterministic replicas applying it stay identical (state machine replication).
  • Equivalent problems: linearizable compare-and-set, a lock with one holder, leader election. Algorithms: Raft, Paxos (Multi-Paxos), Zab, Viewstamped Replication.

Trade-offs

Gains Costs
no split brain; committed means permanent a majority round trip and fsync per decision
tolerates f failures with 2f + 1 nodes minority side stops during a partition
one ordered history one leader's throughput per group

In practice

  • Kafka 4.0 (2025) dropped ZooKeeper; metadata runs on its Raft-based KRaft controller quorum.
  • DynamoDB: each partition's replicas form a Multi-Paxos group; millions of groups per Region.

Pitfalls

  • Even cluster sizes: 4 nodes tolerate 1 failure, like 3, and can split 2 | 2.
  • Putting consensus on the data hot path instead of metadata, or sharding into many groups.
  • Two-Phase Commit is not fault-tolerant consensus: it blocks if the coordinator dies.

Recall

These cards are also in your review deck, scheduled with spaced repetition.