The Many Faces of Consensus — All Equivalent
solve any one of these problems and the solution can be converted into a solution for all the others
Single-value consensus
nodes propose values → one is decided
elects a leader · claims a lease, a
username, or the last seat
Shared log / total order broadcast
append entries in one agreed order
consensus number ∞ · anyone may append
the form most systems actually ship
Linearizable CAS
compare-and-set on one register
consensus number ∞
locks · leases · uniqueness constraints
Atomic commitment
all participants commit, or all abort
consensus with a veto: one abort vote
forces abort · 2PC coordinator = this
CONSENSUS
one agreed value · one agreed order
safety always · liveness with a majority
Fetch-and-add
atomic increment, return the old value
consensus number 2 — the odd one out:
decides only between two proposers
≡ equivalent
≡ equivalent
≡ equivalent
≡
≡
State machine replication
same log + deterministic apply
= identical replicas · serializable txns
Fencing tokens
every log entry gets a monotonic index
zxid / revision — kills zombie writers
Leader election & leases
decide once per epoch (term / ballot)
no split brain · automatic failover
yields
yields
yields
What every consensus algorithm must guarantee
Uniform agreement — no two nodes decide differently.
Integrity — once decided, a node never changes its mind.
Validity — a decided value was proposed by some node.
Termination — every non-crashed node eventually decides
(the only liveness property; needs a majority alive)
The catch
FLP: deterministic + asynchronous + one crash risk ⇒
termination cannot be guaranteed. Timeouts or randomness
make consensus solvable in practice.
Raft / Paxos / Viewstamped Replication / Zab = shared log
with automatic leader election and failover.