Consistency models explained: CAP, PACELC, linearizability and eventual consistency

Key points

• CAP is a statement about partitions, not a menu of two out of three: partitions happen, and the choice is what to give up while one lasts.
• CAP’s C is linearizability, not the C in ACID, and its A means every non-failing node answers every request, not an uptime figure.
• PACELC names the trade-off that matters every day: when there is no partition, a system still chooses between lower latency and stronger consistency.
• Quorums with R + W > N make every read overlap the latest acknowledged write, but overlap alone is not linearizability.
• Isolation levels describe how transactions interleave; consistency models describe what replicas show and when. A database documents both, separately.
• Choose per feature: uniqueness checks and balances need linearizable operations, a profile edit needs read-your-writes, comment threads need causal order, counters can be eventual.

What a consistency model is

As soon as a database keeps more than one copy of a value, on replicas, in another region or in a cache, a write reaches the copies at different moments. A consistency model is the rule that says what a read is allowed to return in the meantime. The strictest models make the copies behave like one copy. The loosest promise only that the copies agree once writes stop.

The word is overloaded, which causes most of the confusion. The C in ACID means a transaction moves the database from one valid state to another, respecting constraints. The C in CAP means something else: Gilbert and Lynch define it as atomic, or linearizable, data, and note that this has a different meaning from the C in ACID. This post is about the second kind. How transactions interleave is a separate axis, covered in the section on isolation levels below.

What the CAP theorem actually says

Eric Brewer stated CAP as a conjecture in an invited talk at PODC 2000. Seth Gilbert and Nancy Lynch proved it in 2002, with precise definitions:

• Consistency: there is a total order on all operations such that each operation looks as if it completed at a single instant, as if one node were answering requests one at a time. That is linearizability.
• Availability: every request received by a non-failing node must result in a response. No bound on how long, but no node may refuse.
• Partition tolerance: the network may lose arbitrarily many messages between groups of nodes.

The theorem: in an asynchronous network, no system provides both consistency and availability when messages can be lost. The proof is short. Split the nodes into two groups that cannot talk. A write lands on one side; a read arrives on the other. To be available, the second side must answer, and it cannot know about the write, so the answer is stale.

Common misreadings, several of which Brewer corrected himself in his 2012 article “CAP Twelve Years Later”:

• “Pick two of three.” Brewer calls the two-of-three framing misleading. You cannot opt out of partitions on a real network, so the actual choice is what to give up while a partition lasts. There is no useful “CA” distributed system; it is a system that has not met a partition yet.
• “CAP applies all the time.” Without a partition, CAP says nothing, and Brewer points out that a system can then have both. The everyday trade-off is latency, which is what PACELC adds.
• “AP means highly available and CP means consistent.” CAP’s availability is all-or-nothing per node and says nothing about uptime. A CP system that refuses requests on the minority side of a partition can still have excellent uptime, and many systems meet neither strict definition.
• “The choice is global.” Brewer describes it as granular: different operations, data or subsystems can choose differently, and a partition is in practice a timeout, “a time bound on communication” in his words.

PACELC: the trade-off when nothing is broken

Daniel Abadi’s 2012 paper argues that the consistency and latency trade-off has shaped real databases more than CAP. His formulation, PACELC, reads: if there is a partition (P), how does the system trade availability (A) against consistency (C); else (E), in normal operation, how does it trade latency (L) against consistency (C)? Keeping replicas in step means waiting for other machines, often in other buildings or regions, on every write or read. Skipping the wait is faster and means a read can miss a recent write.

Treat the examples as a snapshot of 2012 defaults, not a ranking: most of these systems now let each request choose. Abadi makes the same point about the PA/EL systems: raising R + W buys more consistency for more latency, though he notes they still cannot reach consistency as Gilbert and Lynch define it, even with R + W > N. The quorum section below shows why.

A spectrum of consistency models

Between “one copy” and “eventually the same” there are well-defined steps. Stronger models forbid more anomalies and need more coordination, which shows up as latency and as unavailability during partitions.

Herlihy and Wing’s definition is the one to remember: linearizability gives the illusion that each operation takes effect instantaneously at some point between its invocation and its response. The real-time part is what makes it useful for a lock, a leader lease or a uniqueness check, and it is also what forces coordination.

The session guarantees of Terry and colleagues, from the Bayou project at Xerox PARC, are the most practical step down. Their motivating example is a user who changes a password, then logs in against a replica that has not seen the change and is told the new password is invalid. Read your writes fixes that without making the whole system strongly consistent. Monotonic reads stops a user’s view going backward, for example a comment that appears on one refresh and disappears on the next because the second request hit a lagging replica.

Werner Vogels’ “Eventually Consistent” defines the weak end and lists these same variations: causal, read-your-writes, session, monotonic read and monotonic write consistency. Eventual consistency on its own is a liveness promise with no bound: it says the replicas converge, not when, and not what a reader sees before they do. Systems that rely on it need a way to merge concurrent writes, such as last-write-wins timestamps, version vectors or CRDTs; offline-first apps face the same problem on the client.

Quorum reads and writes: R + W > N

Dynamo-style stores make the trade-off a setting. Each key has N replicas. A write succeeds once W replicas acknowledge it, and a read asks R replicas and returns the newest version among their answers. Vogels states the rule: if W + R > N, the write set and the read set always overlap, so a read sees the latest acknowledged write; if W + R ≤ N, they may not overlap, and reads can be stale. Each operation waits for the slowest of the replicas it needs, so R and W are usually kept below N. A common setting is N = 3 with R = W = 2, a majority each way; in Cassandra’s terms, with a replication factor of 3, a QUORUM request needs answers from 2 replicas.

The simulation below writes version 1 to W random replicas, then reads R random replicas before any background repair runs, and counts how often the read returns the old version. It checks the result against the exact probability that the R replicas read miss all W written ones.

import random
from math import comb

def stale_rate(n: int, w: int, r: int, trials: int = 100_000, seed: int = 7) -> float:
    """Write version 1 to w of n replicas, then read r replicas before any repair."""
    rng = random.Random(seed)
    stale = 0
    for _ in range(trials):
        replicas = [0] * n                    # every replica holds version 0
        for i in rng.sample(range(n), w):     # the write is acknowledged by w replicas
            replicas[i] = 1
        seen = max(replicas[i] for i in rng.sample(range(n), r))  # newest version read
        stale += seen < 1
    return stale / trials

for n, w, r in [(3, 1, 1), (3, 2, 1), (3, 1, 2), (3, 2, 2), (3, 3, 1), (5, 2, 2), (5, 3, 3)]:
    exact = comb(n - w, r) / comb(n, r)       # chance the read set misses every written replica
    print(f"N={n} W={w} R={r}  R+W>N: {r + w > n!s:5}  stale: {stale_rate(n, w, r):.3f}  exact: {exact:.3f}")

N=3 W=1 R=1  R+W>N: False  stale: 0.667  exact: 0.667
N=3 W=2 R=1  R+W>N: False  stale: 0.334  exact: 0.333
N=3 W=1 R=2  R+W>N: False  stale: 0.333  exact: 0.333
N=3 W=2 R=2  R+W>N: True   stale: 0.000  exact: 0.000
N=3 W=3 R=1  R+W>N: True   stale: 0.000  exact: 0.000
N=5 W=2 R=2  R+W>N: False  stale: 0.300  exact: 0.300
N=5 W=3 R=3  R+W>N: True   stale: 0.000  exact: 0.000

With N = 3 and one replica per operation, two reads in three are stale until the write spreads. With R + W > N the stale rate is zero in every trial. Real systems also repair in the background, through read repair, hinted handoff and anti-entropy, so the stale window for W + R ≤ N is usually short, but nothing bounds it.

Overlap is not linearizability. A write that has reached some replicas but not yet W of them is visible to some quorums and not others, so two reads in a row can return new, then old:

# N=3, W=2, R=2: every read quorum overlaps every write quorum.
replicas = {"a": 0, "b": 0, "c": 0}  # the version each replica holds

def read(names):
    return max(replicas[n] for n in names)  # newest version among those asked

replicas["a"] = 1           # a write of version 1 has reached a, not yet b or c
print(read(["a", "b"]))     # 1  reader 1 sees the new value and finishes
print(read(["b", "c"]))     # 0  reader 2 starts later and sees the old one
replicas["b"] = 1           # the write now has its W=2 acknowledgements
print(read(["b", "c"]))     # 1  from here on every quorum read sees version 1

Reader 2 started after reader 1 finished and still saw an older value, which a single copy could never do. Algorithms that make quorum reads linearizable have the reader write the newest value back to a quorum before returning. Other gaps remain. Concurrent writes resolved by last-write-wins depend on clocks. And stores that keep accepting writes while a replica is down, by storing hints for it on another node, are counting acknowledgements that may not come from the key’s normal replicas, so the overlap argument holds only while those replicas are reachable.

What real databases document

Vendors document these guarantees in their own words. Four examples, described neutrally:

Two patterns repeat. The strong option is per request, so the same table can serve a strongly consistent read for a checkout and an eventually consistent read for a product list. And the strong option has limits written into the documentation, such as indexes or regions where it is not available. Read those limits before you design around the guarantee. PostgreSQL vs MongoDB covers the wider choice between two of these.

Isolation levels are not consistency models

Isolation levels answer a different question: when several transactions, each touching many rows, run at once, which interleavings are allowed? Serializable means the result equals some one-at-a-time order of the transactions. It does not say that order matches real time, and it says nothing about replicas. Consistency models answer: for single operations on copied data, what may a read return, given what has already happened?

• A serializable primary with asynchronous read replicas still serves stale reads from the replicas. The isolation level did not change; the consistency of replica reads is eventual.
• DynamoDB documents both axes on one page: read-committed isolation for items, and a separate choice between eventually and strongly consistent reads.
• The two combine. Serializable plus linearizable, so that transactions are ordered and the order respects real time, is called strict serializability. It is what most people imagine a single database gives them.
• Weak isolation causes bugs even on one node. Two Read Committed transactions that each read a balance and write a new one can lose an update; PostgreSQL’s Serializable level detects that pattern and asks you to retry.

How to choose, feature by feature

Do not pick one model for the whole system. Ask, for each feature, what a user or another service would see as a bug, and choose the weakest model that rules it out.

Two habits help. Keep the strongly consistent part small, a single row or a single shard, so the coordination it needs stays cheap; sharding and consistent hashing is about choosing keys that make that possible. And move work that can be eventual off the request path, into queues and projections, with the retries made safe as in idempotency and job queues. Event sourcing and CQRS is that pattern taken all the way: a consistent write model and eventually consistent read models.

BYD Tech builds web apps and their backends: the code lives in the client’s GitHub from day one, the founders are on the calls, and AI-assisted work is reviewed by an engineer.