Distributed Consensus

Cloud services build reliable systems from unreliable components. Hosts crash, hard disks stop working, networks falter, but reliable cloud services keep running, ideally without you noticing. Distributed consensus is at the core of making that work.

Distributed consensus is the problem of getting a collection of hosts to agree on the same result even when messages can be delayed, dropped, or reordered and some hosts may fail. Consensus algorithms must satisfy two core goals:

Safety: different participants do not decide different outcomes.
Liveness: when enough of the system is healthy, some outcome eventually gets chosen.

Distributed consensus is extremely common in distributed database systems. It is used to replicate state across hosts so that the system keeps serving requests even if some number of hosts fail.

Paxos solves this for a single write-once register. A proposer tries to get a value chosen by a quorum of acceptors, and learners observe the chosen result. In classic Paxos, a proposer first runs prepare to claim a ballot and discover any earlier accepted value, then runs accept to try to have one value chosen for that ballot. Once a quorum of acceptors accepts a value, that Paxos instance has chosen its one immutable result. I sketched the happy path below. Wikipedia shows other scenarios. I omitted the learners, since in practice the proposer often does double-duty as a learner.

  Proposer     Acceptor 1  Acceptor 2  Acceptor 3
         │              │           │           │
phase 1: ├─prepare(n)──>│           │           │
         ├─prepare(n)───┼──────────>│           │
         ├─prepare(n)───┼───────────┼──────────>│
         │<─promise(v)──┤           │           │
         │<─────────────┼───promise─┤           │
         │<─────────────┼───────────┼───promise─┤
phase 2: ├─accept(n,v)─>│           │           │
         ├─accept(n,v)──┼──────────>│           │
         ├─accept(n,v)──┼───────────┼──────────>│
         │<────accepted─┤           │           │
         │<─────────────┼──accepted─┤           │
         │<─────────────┼───────────┼──accepted─┤

Raft & Multi-Paxos apply the same idea to state machine replication: conceptually, using many Paxos instances chained together, one for each slot in a replicated log. A stable leader amortizes the cost of prepare across many log entries, so the system can keep appending commands without paying for a full leadership handoff on every slot.

CASPaxos is like classic Paxos in that it replicates whole values, not entries in an append-only log, but it allows thosse values to be (safely) updated over time. This is where it gets its name: the CAS in CASPaxos stands for Compare And Swap. The result is a rewritable register. prepare recovers the latest accepted value, the proposer applies its update function locally, and accept tries to install the resulting new value. That gives you linearizable read-modify-write style updates without needing a replicated log. CASPaxos needs just 2 persistent fields per register: a promised ballot and an accepted ballot. It is also, in my opinion, one of the nicest ways to learn the fundamentals of distributed consensus.

# Distributed Consensus