Distributed systems · consistency
S6 said it: across machines there is no free agreement. This sheet is the whole menu of how distributed systems agree, and what each choice costs: CAP and PACELC, the consistency spectrum, quorums, consensus (Raft), and how to move money across services (2PC vs saga). Companion to S6 · Distributed Systems Patterns.
Agreement across machines costs latency or availability; you only choose which. Stronger consistency means more coordination, which means more waiting and less tolerance of partitions. Weaker consistency means less waiting and more uptime, but the application must cope with stale or conflicting reads. Every term below is a point on that one trade.
Before any term, hold the trade. A single machine agrees with itself instantly. The moment two machines must agree on a value or an order, one has to wait for the other, and a network between them can drop, delay, or partition. Consistency is just how hard you insist they agree.
Every read sees the latest write, as if there were one copy. Bought with coordination: writes wait for replicas to agree, and a partition can block progress.
Replicas converge eventually; a read may be stale. Bought with application complexity: you must tolerate stale reads and resolve conflicts, but you get speed and uptime.
Asking for "consistency" without saying which. The word spans a spectrum from "every read is current" to "reads converge someday." Naming the exact level you need, per operation, is the staff move; demanding the strongest everywhere is how you build something slow that still falls over in a partition.
CAP is the famous, slightly misleading start; PACELC is the version that actually guides design.
| Term | Says | The real lesson |
|---|---|---|
| CAP | under a network Partition, choose Consistency or Availability | partitions happen, so you are really choosing CP or AP for that moment |
| CP | stay consistent, refuse some requests | banks, inventory, anything where a wrong answer is worse than no answer |
| AP | stay available, serve possibly-stale data | feeds, carts, presence, anything where uptime beats freshness |
| PACELC | if Partition: A or C; Else (normal): Latency or Consistency | even with no partition, stronger consistency costs latency, every single request |
CAP only talks about the rare partition. PACELC adds the part you pay all the time: in normal operation you still trade latency for consistency. Spanner is "PC/EC" (consistent, pays latency); Dynamo is "PA/EL" (available, low latency, eventual). Quote PACELC, not CAP, to sound like you have shipped one.
Between "strong" and "eventual" sit the levels you actually want most of the time. Stronger is higher in the list and costs more coordination.
| Level | Guarantee | Good for |
|---|---|---|
| Linearizable | reads see the latest write, in real-time order | locks, leader election, counters that must be exact |
| Sequential | one global order all see, not tied to real time | ordered logs, replicated state machines |
| Causal | cause is seen before effect; concurrent ops may differ | comments, chat, collaborative apps |
| Read-your-writes | you always see your own last write | profile edits, "did my post save?" |
| Monotonic reads | you never see time go backwards | feeds that must not flicker stale |
| Eventual | replicas converge, no ordering promise | presence, view counts, caches |
Read-your-writes and monotonic reads are often all a user actually notices, and they are far cheaper than full linearizability (route a session to a replica that has its writes, or read from the leader for a moment). Reach for the weakest level that no user can tell apart from strong.
In a leaderless replicated store you tune consistency with three numbers: how many replicas exist (N), how many must ack a write (W), and how many must answer a read (R).
N = replicas, W = write quorum, R = read quorum
W + R > N => every read overlaps every write => reads see the latest write
(strong-ish: a "strict quorum")
examples (N = 3)
W=3, R=1 fast reads, slow/fragile writes (write needs all 3)
W=1, R=3 fast writes, slow reads
W=2, R=2 balanced, W+R=4 > 3 => overlap guaranteed
W=1, R=1 fastest, W+R=2 < 3 => may read stale (pure eventual)
Set W + R > N and any read is guaranteed to touch at least one replica that has the latest write, so you read fresh. Drop below it (W + R ≤ N) and you have chosen eventual consistency for more speed and availability. Cassandra and Dynamo expose exactly these knobs per query.
Where writes are allowed decides your consistency and your conflicts. Three shapes, each with a clear trade.
When you genuinely need one agreed value or order (a leader, a config, a replicated log), you need a consensus algorithm. Raft is the one to be able to explain; Paxos is the older, harder-to-follow ancestor.
flowchart TB
subgraph LE["Leader election: terms are a logical clock"]
direction TB
F(("follower")) -->|"hears no heartbeat, times out"| C(("candidate"))
C -->|"asks for votes"| V{"a majority of votes?"}
V -->|"yes"| L(("leader for that term"))
V -->|"no"| F
end
subgraph LR2["Log replication"]
direction TB
CW["client writes to the leader"] --> AP["leader appends to its log, ships entries"]
AP --> M{"a majority has stored it?"}
M -->|"yes"| CM["committed, then applied"]
M -->|"no"| AP
CM --> OV["followers that diverge are overwritten to match the leader"]
end
L ~~~ CW
WHY["why a majority, N/2 + 1: any two majorities overlap in one node, so a new leader always sees the latest committed entry"]
V -.-> WHY
classDef good fill:#D6F5E3,stroke:#1B7F46,color:#09244B
classDef accent fill:#DCEBFE,stroke:#4A90D9,color:#09244B
class L good
class WHY accent
Consensus = a majority agrees, and because any two majorities overlap, the system never forgets a committed decision or elects two leaders. It needs 2f + 1 nodes to tolerate f failures (so 3 to survive 1, 5 to survive 2). It is the engine under etcd, ZooKeeper, Consul, and the metadata layer of most databases. Use it for the few things that must be exactly agreed, not for bulk data.
A transaction that spans services cannot use one database's ACID. Two patterns, a sharp trade between consistency and availability.
Prefer a saga at scale: 2PC's blocking lock-hold is a reliability liability across services. Use compensations (refund the charge, release the seat) and make each step idempotent. Reach for 2PC only inside a small, tightly-coupled boundary where you truly need atomicity and can accept the blocking. This is the S6 idempotency-and-sagas slide in one card.
Start from the guarantee the use case actually needs, not from the strongest one available.
flowchart TB
Q{"what must be true?"}
Q --> C1["exactly one leader, lock, or agreed value"]
C1 --> R1["CONSENSUS, Raft, plus majority"]
Q --> C2["every read sees the latest write"]
C2 --> R2["LINEARIZABLE: leader read, or W + R > N"]
Q --> C3["I must see my own writes"]
C3 --> R3["READ-YOUR-WRITES: session routing"]
Q --> C4["cause before effect, chat, comments"]
C4 --> R4["CAUSAL consistency"]
Q --> C5["uptime over freshness, feed, presence"]
C5 --> R5["EVENTUAL, AP, plus quorum tuning"]
Q --> C6["a transaction across services"]
C6 --> C6a["small boundary, need atomic"]
C6a --> R6a["2PC, accept blocking"]
C6 --> C6b["scale, can compensate"]
C6b --> R6b["SAGA: eventual, plus undo steps"]
classDef good fill:#D6F5E3,stroke:#1B7F46,color:#09244B
classDef accent fill:#DCEBFE,stroke:#4A90D9,color:#09244B
class R1 good
class R2 accent
| You need… | Reach for | Seen in |
|---|---|---|
| One agreed leader / config | Consensus (Raft / Paxos) | etcd, ZooKeeper, Consul |
| Strong reads, no conflicts | Single-leader + leader reads | Postgres, MySQL |
| Tunable per-query consistency | Quorums (W + R > N) | Cassandra, Dynamo |
| Globally consistent transactions | Consensus + TrueTime | Spanner, CockroachDB |
| Cross-service transaction at scale | Saga + compensations | microservices, orders |
| Local-fast multi-region writes | Multi-leader / CRDTs | collaborative apps |
The consistency questions that come up, and the sentence or two that shows judgement rather than recall.
Q · CAP, in one breath?
Under a partition you must choose consistency or availability. Partitions are inevitable, so you are really picking CP or AP for that moment. Use PACELC to remember you also trade latency for consistency the rest of the time.
Q · What does W + R > N buy?
A read quorum that overlaps every write quorum, so a read always touches a replica with the latest write and sees fresh data. Drop below it and you have chosen eventual consistency for speed.
Q · Why does consensus need a majority?
Any two majorities share a node, so a new leader always sees the last committed entry and you can never elect two leaders or lose a decision. That overlap is why you need 2f+1 nodes to tolerate f failures.
Q · 2PC vs saga?
2PC gives cross-service atomicity but blocks on locks and stalls if the coordinator dies. A saga uses local commits plus compensations: available and scalable, but only eventually consistent. Prefer sagas across services.
Q · Strong vs eventual, when each?
Strong for money, inventory, locks, where a wrong read is unacceptable. Eventual for feeds, presence, counts, where uptime and latency beat freshness. Most systems mix both, per operation.
Q · Linearizable vs sequential?
Both give a single order. Linearizable also respects real-time: once a write completes, everyone sees it. Sequential only promises some consistent global order, not tied to wall-clock. Linearizable is stronger and costlier.
Q · How does Spanner do global strong consistency?
Consensus (Paxos) per shard for agreement, plus TrueTime (bounded-error clocks) and commit-wait to order transactions globally. It is PACELC PC/EC: consistent, and it pays the latency.
Q · Multi-leader's main problem?
Write conflicts: two regions edit the same row concurrently. You must resolve them, last-write-wins (lossy), CRDTs (auto-merge for some types), or application logic. Single-leader avoids this by construction.
The ways smart people get consistency wrong, and the habit that catches them.
The traps
W=1,R=1 on N=3 and surprised by stale reads.The repeatable move
1. what guarantee does this op truly need?
2. partition: CP or AP? else: latency or consistency?
3. agreed value? consensus. tunable? quorums
4. cross-service? saga + compensations, idempotent
The tell in a design review: "strongly consistent" applied to everything, or a distributed transaction with no compensation plan. Name the level per operation, and push back on the blanket answer.
Pick the weakest consistency the use case can tolerate, tune it with quorums, and use consensus only for the few things that must be exactly agreed. This whole sheet is the S6 "no free agreement" slide unpacked, and idempotency plus sagas are how you live with the consistency you chose.
Companion to S6 · Distributed Systems Patterns. Further reading: Raft paper (Ongaro & Ousterhout) · PACELC · Jepsen consistency models · Fowler · patterns of distributed systems · Saga pattern.