A single machine fails, so we keep copies of the data on several machines. The moment we do, a new question appears: when a client reads one copy, what is it allowed to see relative to writes that landed on other copies? Consistency models are the precise answers to that question. They are the contract between a replicated store and its clients, and most design decisions in a distributed database (how many acknowledgements to wait for, whether a leader is needed, whether writes can conflict) are really decisions about which contract to offer.

This chapter walks the spectrum from the strongest model (linearizability) to the weakest useful one (eventual consistency), explains what CAP does and does not say, and shows two ways to get useful guarantees without coordinating every operation: tunable quorums and conflict-free replicated data types.

In one minute

• Replication buys fault tolerance and read scalability; the price is keeping copies in agreement. A consistency model states how much agreement clients may assume.
• CAP: during a network partition a system must choose between answering every request and never returning stale data. Partitions are not optional, so the real choice is C or A while partitioned. PACELC adds the normal-case trade-off: latency versus consistency.
• "Consistent" in CAP means linearizable; "consistent" in ACID means application invariants hold. Different concepts, same word.
• Linearizability: every operation appears to take effect at one instant between its start and end, in real time. It needs coordination (consensus or a leader with a quorum) and is the most expensive model.
• Sequential consistency keeps program order and a single global order but drops real time. Causal consistency orders only operations that could have influenced one another; vector clocks detect which those are.
• Session guarantees (read-your-writes, monotonic reads, monotonic writes, writes-follow-reads) describe what one client sees and are often what an application actually needs.
• Quorums with R + W > N make read and write sets overlap, so a read sees the latest acknowledged write. That is recency for one key, not linearizability, and sloppy quorums break even that.
• CRDTs converge without coordination by restricting data types to merges that are commutative, associative and idempotent: counters, registers, sets.

Achieving availability

A system is fault tolerant when it keeps serving requests although some components have failed. For storage the main tool is replication: hold the same data on several nodes so a dead disk or an unreachable rack does not make it unavailable. Replication also spreads read load and lets you place copies near users.

The cost is immediate. A write that reaches only some replicas leaves copies in disagreement, and a client reading the wrong copy sees the past. There are two ways to avoid showing stale data: make the write wait until enough copies have it (costing latency and, when copies are unreachable, availability), or make the read consult enough copies to find the newest value (costing read latency). Every replication design chooses a point on this line, whether it is single-leader (PostgreSQL streaming replication, Kafka partitions), multi-leader (cross-region writes with conflict handling) or leaderless (Dynamo, Cassandra, Riak). Later chapters cover the machinery; this one covers what the client is promised.

The infamous CAP theorem

The three letters

Consistency in CAP is a strong, specific property: every read returns the most recent write, as if there were a single copy. That is linearizability. Availability means every request to a non-failed node gets a non-error response, with no bound on time. Partition tolerance means the system keeps working when the network drops messages between groups of nodes.

Gilbert and Lynch's proof is short. Split the nodes into two groups that cannot talk. A client writes to group one, then another client reads from group two. The reading node either answers (available, but it cannot know about the write, so not linearizable) or refuses (linearizable, not available).

The misreading and PACELC

"Pick two of three" misleads because partitions are not a design choice; any multi-machine system will see them. The decision is what to do during a partition: keep answering with possibly stale data (AP) or refuse some requests to stay correct (CP). The labels are coarse, since a system may be CP for writes and AP for reads.

CAP also says nothing about normal operation. PACELC (Abadi, 2012) fills that in: if there is a Partition, choose A or C; Else choose between Latency and Consistency. Dynamo and Cassandra are PA/EL; systems built on synchronous consensus such as Spanner or etcd are PC/EC.

CAP consistency versus ACID consistency

ACID's C says a transaction preserves the application's invariants (balances non-negative, foreign keys valid). CAP's C says the replicated register behaves like one copy. Confusing them yields claims like "eventually consistent systems cannot maintain invariants", which the coordination-avoidance work in the transactions chapter refutes.

Harvest and yield

Fox and Brewer replaced the binary choice with two continuous metrics. Yield is the fraction of requests that complete. Harvest is the fraction of the data a completed answer reflects. A search service with one of ten index shards down can keep yield at 100% and let harvest drop to 90%, or fail requests touching the missing shard to keep harvest at 100%. Degrading along the harvest axis is how many real systems behave, and it is a more useful vocabulary than "AP".

Shared memory and ordering

Registers as the model

The book borrows the vocabulary of shared-memory concurrency. A register is a unit of storage with read and write; a distributed store is an array of registers accessed by processes concurrently. Each operation has an invocation and a response separated by some duration; operations whose durations overlap are concurrent, and the model must say what a read concurrent with a write may return.

Register type	Guarantee for a read overlapping a write
Safe	Returns the last completed write if there is no overlap; otherwise any value in the domain
Regular	Returns the last completed write or the value of an overlapping write
Atomic	Every operation appears to occur at a single instant within its duration; reads never go backwards. An atomic register is a linearizable register

A single leader that applies writes in order and answers from the latest value gives you an atomic register for one key. The hard part is many keys, many replicas, failures.

Ordering

With one copy there is one history of writes; with replicas there is a history per replica, and clients may observe them in different orders. A consistency model is mostly a statement about which orderings clients may observe and whether they must agree. Two notions matter. Real-time order: A completed before B began on an idealised global clock. Causal order (happens-before): B could have been influenced by A, because the same process ran A then B, or B read what A wrote, or by transitivity. Causal order is partial; operations without a causal path are concurrent. Linearizability respects real time, sequential consistency respects program order, causal consistency respects happens-before, eventual consistency promises only convergence.

Consistency models

Each model admits every history the model above it admits, plus more.

Strict consistency

Any write is visible to every subsequent read by any process, instantly. This needs a global clock and zero propagation delay, so it is a reference point only: what a single-threaded program on one machine gives you.

Linearizability

Linearizability (Herlihy and Wing, 1990) is the strongest model a real system offers. Each operation appears to take effect atomically at a linearization point between its invocation and response. Once a write's point has passed, every read that starts afterwards returns that value or a newer one; no read returns an older value after a newer one has been observed; nobody sees partial effects.

Linearizability is a single-object, single-operation property. It composes (a system of linearizable objects is linearizable) but says nothing about multi-object transactions. That is serializability, an isolation property. A store can be linearizable per key with no transactions, or serializable and non-linearizable (a serial order that ignores real time, as with stale snapshot reads). Strict serializability is both.

The cost. In one process, hardware provides linearizable registers through atomic instructions such as compare-and-swap (write only if the value is still the one you read); the cache-coherence protocol behind CAS is a tiny consensus protocol. Across machines there is no shared cache line. To make a write visible at one instant to readers on any replica, the replicas must agree on write order before answering reads: either a single leader all operations pass through (with a guarantee there is only one leader), or quorum reads that overlap quorum writes and repair before returning. Either way every operation waits on a network round trip to a majority, and under a partition the minority side must stop answering.

Checking it. Take a recorded history, choose a linearization point inside each operation's duration, and ask whether the resulting sequence is one a single register could produce. If any placement works, the history is linearizable. Jepsen's checkers do exactly this search and have found violations in many databases claiming strong consistency.

Sequential consistency

Sequential consistency (Lamport, 1979) drops the real-time clause: all operations fit a single total order that preserves each process's program order and that every process observes. A write may become visible some time after it completed, and two processes' writes may be ordered differently from how a stopwatch saw them. A single-leader system with followers applying the log in order gives this to clients that read from one follower: all writes in the same order, just late. It is too weak for anything relying on real time, such as "I released the lock before you tried to take it".

Causal consistency

Causal consistency requires all processes to observe causally related operations in the same order, while concurrent operations may appear in different orders. Nobody may see Bob's reply without Alice's question, but unrelated posts by Alice and Carol may appear in either order. It is the strongest model achievable while staying available under partitions: each replica accepts writes locally and ships them lazily, exposing a write only after its dependencies.

Vector clocks implement the dependency tracking. Each process keeps one counter per process, increments its own on each local event, attaches the vector to messages, and on receipt takes the component-wise maximum. For vectors V(a) and V(b): a happened before b if every component of V(a) is at most that of V(b) and one is strictly less; a and b are concurrent if neither dominates. Concurrent writes to one key are conflicts: the store keeps both as siblings for the application to reconcile (Dynamo, Riak) or picks a winner by last-writer-wins, which silently discards a write. Vector clocks grow with the number of writers, so systems prune entries (Dynamo truncates at ten) or use per-server entries; Riak's dotted version vectors avoid sibling explosion.

Session models

The models above are stated from an omniscient observer's view. Session models (Terry et al., 1994) describe what one client sees within a session, which is what developers usually mean by "consistent" and is far cheaper than linearizability.

Guarantee	Statement	Anomaly it prevents
Read-your-writes	A client's later reads reflect its own earlier writes	Save profile, refresh, see the old one
Monotonic reads	A client never sees an older value after a newer one	A comment vanishes and reappears
Monotonic writes	A client's writes apply in issue order on every replica	Two appended log lines swapped
Writes-follow-reads	A write depending on a read is ordered after it everywhere	A reply shown before the comment

Implementations: route a session to one replica (sticky sessions), or return a version token (log position, vector clock, hybrid-logical-clock timestamp) with each response and have the client send it back so a replica waits until it has caught up. Azure Cosmos DB's session level and MongoDB's causally consistent sessions work with tokens.

Eventual consistency

Eventual consistency says only that if writes stop, replicas eventually hold the same value: no bound on "eventually", no guarantee about reads in between, including reads that go backwards. It is a liveness property, not a safety property. Useful systems layer something on top: quorums, session guarantees or CRDTs.

Tunable consistency

N, R and W

Dynamo-style stores let the operator choose, per operation, how many replicas participate. N is the replication factor; W the number of replicas that must acknowledge a write before success is reported; R the number that must respond to a read before the coordinator returns the newest version it saw. Cassandra exposes these as consistency levels (ONE, QUORUM, LOCAL_QUORUM, ALL); Riak as r, w, pr, pw.

The overlap rule and its limits

If R + W > N, every read set shares a replica with every write set, so some responder holds the latest acknowledged write and the coordinator can return it by comparing versions. With N = 3: W = 2, R = 2 is balanced; W = 3, R = 1 favours reads; W = 1, R = 3 favours writes. A quorum in the strict sense is a majority, floor(N/2) + 1.

The overlap guarantees a read observes some value at least as new as the last acknowledged write. It does not make the system linearizable:

• Concurrent writes with W = 2 can each reach a different pair of replicas; the winner is picked by timestamp (depending on clock sync) or both are kept as siblings. One write may be lost or deferred to the application.
• Partial writes that failed (W not met) remain on the replicas that got them and may be read later; there is no rollback.
• Read-write races: a read may see the new value from one replica while a slightly later read hits only replicas that lack it, unless read repair is synchronous.
• Sloppy quorums (Dynamo writes to the first N healthy nodes, not the home replicas) draw read and write sets from different nodes, so overlap no longer holds.
• Quorums are per key; nothing orders writes to two keys.

What you get is a knob between latency and staleness, plus the ability to keep serving with N - W replicas down for writes and N - R for reads. That is useful, and it is not a substitute for consensus when you need a single-copy illusion.

Witness replicas

Replication multiplies storage by N. Witness replicas cut that: the replica set is split into copy replicas that store data and witness replicas that normally store only enough to vote (a record that a write happened, not its payload). Witnesses count toward quorums, so five nodes can decide while three hold full copies. When copy replicas fail and a quorum cannot be formed from them, witnesses are promoted and store data until copies recover, then demoted. Spanner uses witnesses in multi-region configurations (they vote in Paxos but do not serve reads); Cassandra's transient replication (experimental, 4.0) stores data on transient replicas only while a full replica is down and drops it once incremental repair has moved it.

Strong eventual consistency and CRDTs

From eventual to strong eventual

Strong eventual consistency (Shapiro et al., 2011) adds a safety clause: any two replicas that have received the same set of updates, in any order, are in the same state. Conflicts are impossible by construction, so updates may arrive late, duplicated or reordered and replicas still converge deterministically. The structures that make this work are CRDTs, conflict-free replicated data types:

• State-based (convergent, CvRDT): replicas ship whole states and apply a merge that is commutative, associative and idempotent (a join semilattice). Idempotence makes duplicates and reordering harmless, so the transport only needs eventual delivery. Delta CRDTs ship only recent changes.
• Operation-based (commutative, CmRDT): replicas ship operations that commute; the transport must deliver each exactly once in causal order, since operations are generally not idempotent. Less bandwidth, more demands on messaging.

The two flavours are equally expressive.

The standard catalogue

CRDT	State	Update	Merge	Notes
G-counter	one integer per replica	increment own slot	component-wise max	value = sum of slots
PN-counter	two G-counters P and N	increment adds to P, decrement to N	merge each	value = sum(P) - sum(N); cannot enforce a lower bound
LWW-register	value plus timestamp	set with new timestamp	keep higher timestamp, tie-break by replica id	concurrent writes lose one; needs sane or hybrid logical clocks
MV-register	set of (value, vector clock)	set with writer's clock	keep undominated pairs	exposes siblings instead of discarding
G-set	a set	add	union	no removal
2P-set	add set plus tombstones	add; remove adds a tombstone	union of both	removed elements cannot return; tombstones grow
OR-set (add-wins)	elements with unique tags	add makes a fresh tag; remove deletes observed tags	union minus observed removes	re-add works; concurrent add and remove resolves as add
Sequence CRDTs (RGA, Logoot, YATA)	elements with position ids	insert between neighbours, delete by tombstone	union with deterministic order	collaborative text (Yjs, Automerge)

Merge semantics encode business rules, so pick the type for the rule: a shopping cart wants an OR-set, a "last seen" field an LWW-register, a like count a PN-counter. CRDTs cannot express invariants that need coordination, such as "never below zero" or "username is unique"; those need a consensus round or an escrow scheme. In production: Riak data types, Redis Enterprise active-active, Akka distributed data, and collaborative editors built on Yjs or Automerge.

Design trade-offs

Model or mechanism	Coordination per operation	Available under partition	Programmer effort	Typical use
Linearizable	majority round trip or single leader	no, minority stops	lowest	locks, leader election, uniqueness
Sequential	ordered log, read from one replica	partially	low	reporting replicas
Causal	dependency tracking, lazy propagation	yes	medium, conflicts possible	feeds, geo-replicated stores
Session guarantees	version token or sticky routing	yes	low	per-user consistency
Tunable quorum	R or W replicas	up to N - R or N - W failures	medium, LWW or siblings	Cassandra, Riak, DynamoDB
CRDTs	none	yes	medium, choose types up front	counters, carts, presence, editing
Plain eventual	none	yes	high	caches, DNS, metrics

Pick the weakest model your invariants allow, then verify. Many "we need strong consistency" requirements are read-your-writes for one user; many "eventual is fine" decisions leak into a payment flow that assumed monotonic reads.

Interview angle

• Explain CAP in two sentences, then say what is wrong with "pick two". Under a partition you can keep answering or keep returning the latest value, not both. Partitions are not a choice, so the decision is behaviour during partitions, and CAP is silent about normal operation, where the trade-off is latency versus consistency (PACELC).
• Compare linearizability and serializability. Linearizability is a real-time recency guarantee for single operations on single objects. Serializability is an isolation guarantee for multi-object transactions with no real-time requirement. Strict serializability is both; a snapshot-reading replica can be serializable yet non-linearizable.
• N = 3, W = 2, R = 2: is it linearizable? No. Reads see a value at least as new as the last acknowledged write, but concurrent writes resolve by timestamp, failed writes linger, sloppy quorums break overlap, and reads can go backwards without synchronous read repair. You get bounded staleness.
• How would you implement read-your-writes cheaply? Route a session to one replica, or return a version token with each write and have reads carry it so a lagging replica waits or forwards. Far cheaper than linearizing everything.
• Design a like counter across three regions with a flaky link. A PN-counter with one slot pair per region: increment locally, replicate state asynchronously, merge by component-wise max. Expose the approximate total; if an exact total at an instant is needed, snapshot at a causal barrier rather than coordinating every increment.
• Why vector clocks rather than Lamport timestamps for causal consistency? Lamport clocks give a total order consistent with causality but cannot detect concurrency: a smaller timestamp does not imply happens-before. Vector clocks capture happens-before exactly, so concurrent writes can be flagged as conflicts.
• What goes wrong when an LWW register relies on wall clocks? A node whose clock runs ahead wins with an older write and the newer one vanishes silently. Use hybrid logical clocks or an MV-register that keeps siblings.
• What do witness replicas buy and cost? Five voters with three full copies: less storage and cross-region bandwidth. In exchange witnesses serve no reads, and promotion after copy failures takes time with reduced durability meanwhile.

Pitfalls and misconceptions

• "Eventually consistent" is a safety guarantee. It is liveness: convergence at some unspecified time, with nothing promised before then.
• Quorum reads and writes make a system strongly consistent. They give single-key recency under ideal conditions; concurrent writes, failed writes, sloppy quorums and clock skew all produce non-linearizable histories.
• CAP consistency equals ACID consistency. CAP's C is linearizability; ACID's C is "invariants hold". Isolation levels are a third axis.
• A CP system is unavailable. It refuses some requests on the minority side of a partition. Most of the time there is no partition.
• Causal and session guarantees are too weak to matter. They prevent the anomalies users notice, are achievable while available, and are what most applications actually rely on.
• CRDTs solve all conflicts. They converge to a state chosen by the merge rule, which may not be the one the business wants, and they cannot enforce global invariants.
• Linearizability is a property of the database alone. Caches and connection poolers in front of a linearizable store can destroy it from the client's view.

Key terms

Term	Meaning
Consistency model	A contract stating which histories of reads and writes clients may observe from a replicated store
CAP theorem	Under a partition a system cannot be both linearizable and respond to every request
PACELC	Under a partition choose availability or consistency; otherwise choose latency or consistency
Harvest and yield	Fraction of data reflected in an answer, and fraction of requests answered
Atomic register	A register where every operation appears to occur at one instant; a linearizable register
Linearizability	Every operation takes effect at one instant between start and end, consistent with real time
Compare-and-swap	Atomic write-if-unchanged instruction underlying lock-free linearizable structures
Serializability	Transactions execute as if in some serial order; an isolation property, not a recency one
Sequential consistency	One total order preserving each process's program order, without real-time constraints
Causal consistency	Causally related operations are seen in the same order everywhere; concurrent ones may differ
Vector clock	One logical counter per process; detects happens-before and concurrency exactly
Session guarantees	Read-your-writes, monotonic reads, monotonic writes, writes-follow-reads
Eventual consistency	Replicas converge if updates stop; nothing promised in between
Quorum	A majority of replicas, floor(N/2) + 1; any two majorities intersect
Sloppy quorum	Writing to the first N reachable nodes instead of the home replicas, breaking overlap
Witness replica	A replica that votes but stores no data unless promoted
Strong eventual consistency	Replicas that received the same updates in any order are in the same state
CRDT	A data type whose merge is commutative, associative and idempotent, so replicas converge without coordination

Further reading

• Database Internals, Chapter 11; DDIA Chapters 5 and 9 cover the same ground from the application side.
• Seth Gilbert and Nancy Lynch, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services", ACM SIGACT News, 2002.
• Daniel Abadi, "Consistency Tradeoffs in Modern Distributed Database System Design", IEEE Computer, 2012 (PACELC).
• Armando Fox and Eric Brewer, "Harvest, Yield, and Scalable Tolerant Systems", HotOS 1999.
• Martin Kleppmann, "A Critique of the CAP Theorem", https://arxiv.org/abs/1509.05393
• Maurice Herlihy and Jeannette Wing, "Linearizability: A Correctness Condition for Concurrent Objects", ACM TOPLAS, 1990.
• Douglas Terry et al., "Session Guarantees for Weakly Consistent Replicated Data", PDIS 1994.
• Marc Shapiro, Nuno Preguiça, Carlos Baquero and Marek Zawirski, "A Comprehensive Study of Convergent and Commutative Replicated Data Types", INRIA, 2011, https://hal.inria.fr/inria-00555588
• Giuseppe DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store", SOSP 2007, https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
• Jepsen's consistency model map, https://jepsen.io/consistency