CS Fundamentals Trainer · Guides

The CAP theorem and consistency models

What CAP really says, a CP versus AP partition experiment, quorums (R + W > N), the spectrum from linearizable to eventual, and PACELC.

12 min read

The CAP theorem is the most quoted and most misquoted result in distributed systems. The slogan "pick two of consistency, availability, partition tolerance" is wrong in a way that matters. This guide states what the theorem actually says, shows it in a small experiment, and then covers what you really choose between in practice: the consistency models and the latency trade-off that applies even when nothing is broken.

1. What the theorem says

Eric Brewer conjectured it in 2000, and Seth Gilbert and Nancy Lynch proved a precise version in 2002 [1]. Three properties of a replicated service:

• Consistency (C): here it means linearizability: every operation appears to take effect at one instant between its start and its end, so a read after a completed write sees that write (or a later one), as if there were a single copy of the data. This is a strong notion, not the "C" of ACID.
• Availability (A): every request that reaches a non-failed node gets a (non-error) response, in finite time.
• Partition tolerance (P): the system keeps working even when the network drops or delays messages between nodes.

The theorem: when the network is partitioned, a system cannot be both consistent and available.

The argument is short. Split two replicas by a partition. A client writes x = 1 to one side. Another client reads x from the other side. That node has two choices: answer with the old value (available, but not consistent: the read missed a completed write) or refuse to answer until it can talk to the other side (consistent, but not available). There is no third option.

2. Why "pick two" is misleading

• You cannot choose to give up P. Networks drop packets, links fail, a node pauses for garbage collection and looks dead. If your system spans more than one machine, partitions will happen, so P is not a menu item. What you choose is what to do when one happens: stay consistent or stay available.
• It only concerns the moment of a partition. When the network is healthy, you can have both. The theorem says nothing about normal operation.
• The definitions are narrow. "Available" means every non-failed node answers every request; a system that merely answers most requests, or only from a majority side, is not "A" in the theorem's sense. "Consistent" means linearizability, nothing weaker. Real systems sit on a spectrum, and Martin Kleppmann points out that CAP's definitions of consistency and availability are ambiguous and do not match what real databases offer, and proposes describing a system by how its operations behave when the network is slow (a "delay-sensitivity" framework) instead [2].
• It is not a statement about quality. Neither choice is "better". It depends on what a wrong answer costs.

3. A small experiment

I simulated five nodes holding a shopping cart, and cut the network into a group of two (A, B) and a group of three (C, D, E). Then I wrote to the cart from both sides and read it back. Two modes:

• CP (consistent, partition tolerant): a write or read is allowed only on the side that holds a majority of the nodes (here three of five).
• AP (available, partition tolerant): every node serves requests using what it has, and conflicts are repaired after the partition heals (here with "last write wins").

Result:

CP during partition: A (minority side): unavailable, no majority
                     D (majority side): ok   -> reads [milk,bread]
   after heal, the minority catches up: [milk,bread]   (nothing was lost)

AP during partition: A: ok  (cart = [milk,eggs])
                     D: ok  (cart = [milk,bread])      <- two different carts
   after heal + last-write-wins: [milk,bread]          (the other write is lost)

The CP system told the client on the minority side "no", and never showed a wrong cart. The AP system answered everyone, produced two diverging versions, and when the partition healed, one customer's addition (eggs) was silently discarded. That is the trade: an error now, or a conflict to resolve later.

Here is the model (a short Python script you can run as it stands). Each node keeps (version, value) for a key. A partition splits the nodes into groups that cannot talk. In CP mode a group needs a strict majority to read or write; in AP mode every group serves requests from its own nodes, and repair applies last write wins (the highest version) after the heal.

class Cluster:
    def __init__(self, names, mode):
        self.data = {n: {} for n in names}      # node -> {key: (version, value)}
        self.mode, self.groups, self.clock = mode, [set(names)], 0

    def partition(self, *groups): self.groups = [set(g) for g in groups]
    def heal(self): self.groups = [set(self.data)]
    def group_of(self, node): return next(g for g in self.groups if node in g)

    def _need_majority(self, node):
        if self.mode == "CP" and len(self.group_of(node)) <= len(self.data) // 2:
            raise RuntimeError("unavailable: no majority")

    def write(self, via, key, value):
        self._need_majority(via)
        self.clock += 1
        for n in self.group_of(via):             # only the nodes this node can reach
            self.data[n][key] = (self.clock, value)

    def read(self, via, key):
        self._need_majority(via)
        return self.data[via].get(key)

    def repair(self, key):                       # after healing: the highest version wins
        best = max(d[key] for d in self.data.values() if key in d)
        for d in self.data.values(): d[key] = best

for mode in ("CP", "AP"):
    c = Cluster("ABCDE", mode)
    c.write("A", "cart", "[milk]")
    c.partition("AB", "CDE")
    for via, value in (("A", "[milk,eggs]"), ("D", "[milk,bread]")):
        try: c.write(via, "cart", value); print(mode, via, "write ok")
        except RuntimeError as e: print(mode, via, "write refused:", e)
    c.heal(); c.repair("cart")
    print(mode, "after heal:", c.data["A"]["cart"][1])

Running it prints that in CP mode the write through A is refused and the cart ends as [milk,bread], and in AP mode both writes succeed and the cart also ends as [milk,bread], because bread carried the higher version and eggs is gone.

A real AP system can avoid silent loss by keeping both versions and merging them (a shopping cart can be merged by taking the union of items). Dynamo-style stores use version vectors to detect that two writes were concurrent, and CRDTs (conflict-free replicated data types) are data structures designed so that any merge order gives the same result.

4. Quorums: how replicated stores pick the side

Take N replicas of each item. A write must be acknowledged by W of them and a read must ask R of them. If

R + W > N

then every read set and every write set overlap in at least one replica, so a read always contacts a replica that saw the latest acknowledged write. I checked it by brute force for N = 3 and N = 5: for every R and W, "every read set intersects every write set" is true exactly when R + W > N.

Be careful: overlapping quorums are necessary for the guarantee but not sufficient for full linearizability in a real store. Concurrent writes, clock problems, "sloppy" quorums that accept writes on other nodes during a failure, and partial failures during a write can all still produce stale or lost reads. Consensus algorithms (Raft, Paxos) add the missing pieces: a single leader per term, ordered logs, and majority commit.

5. Consistency models: the spectrum

From strongest to weakest. Each model allows more behaviour, and costs less coordination.

The practical middle: session guarantees such as read-your-writes and monotonic reads are cheap (route a user to one replica or remember a version) and remove most of what users notice as "inconsistent". The caching guide's section on replicas shows the same problem from the application side (caching strategies). Do not confuse these with the isolation levels of a database transaction, which are about concurrent transactions on one database (transaction isolation levels); strict serializability combines both ideas.

6. PACELC: what about when nothing is broken?

Daniel Abadi pointed out that CAP only describes the failure case, while the trade-off between consistency and latency exists all the time [3]. His formulation, PACELC: if there is a Partition, choose Availability or Consistency; Else (normal operation), choose Latency or Consistency.

The reason is physics: to be strongly consistent, a write must be acknowledged by replicas that may be in other data centres, so it costs at least one cross-region round trip (tens to hundreds of milliseconds). A system can answer faster by acknowledging after one local replica and replicating in the background, at the price of stale reads. So:

• A system built for low latency everywhere typically chooses PA/EL: available during partitions, low latency otherwise, weaker consistency.
• A system built for correctness typically chooses PC/EC: consistent in both cases, paying in latency and in availability during partitions.
• Mixed designs exist (PA/EC, PC/EL), and many databases let you choose per request (for example a consistency level on each read or write).

Treat the labels as a way to ask the right question, not as exact classifications of products; vendors' defaults and options change.

7. How to choose

Ask what a wrong answer costs compared with no answer:

Also remember that the choice can differ per feature within one product: use a consistent store for payments and an eventually consistent one for activity feeds.

8. Common mistakes

• "Our database is CA." A distributed system cannot opt out of partitions. A single-node database is trivially "CA" because there is nothing to partition.
• Treating CAP's C as ACID's C, or "availability" as "high uptime". The words are used in a specific, narrow sense.
• Ignoring the normal case. Most of the time there is no partition; latency and consistency are the daily trade-off (PACELC).
• Assuming a quorum alone gives linearizability. See section 4.
• Relying on timestamps from different machines for "last write wins". Clocks drift, so the "last" write may be the older one. Prefer versions, or logical clocks, and be explicit about what is lost.
• Not testing partitions. Tools such as Jepsen test real databases under partitions and often find that the documented guarantees do not hold in every case. Write your own failure tests.

9. Questions interviewers like to add

"Can you have CP and AP at once?"

Per request, yes: the same store may offer strong reads for some calls and fast stale reads for others. For one operation during one partition, no.

"Is a system with a majority leader (Raft) CP?"

Yes in the usual sense: the minority side cannot elect a leader or commit, so it is unavailable for writes, while the majority side stays consistent.

"How do two sides reconcile after a partition?"

Last write wins (simple, loses data), version vectors that keep both and ask the application to merge, CRDTs that merge automatically, or a rule specific to your domain (union of cart items, maximum of a counter).

"Does eventual consistency mean data can be wrong forever?"

No. It means replicas converge if updates stop. The questions are how long "eventually" is (usually milliseconds to seconds) and what the application does with stale reads in the meantime.

10. Things to mention in an interview

• State the theorem correctly: during a partition you choose between consistency (linearizability) and availability; P is not optional.
• Give the one-paragraph proof argument with two replicas.
• Name the consistency spectrum and the session guarantees.
• Bring up PACELC and the latency cost of consistency even when everything works.
• Explain R + W > N and its limits.
• Choose per feature, and say what a wrong answer costs.

Quick recap

1. CAP: in a partition, a replicated system must choose between linearizable consistency and availability.
2. Partitions cannot be avoided, so the real choice is C or A during one.
3. In the simulation, the CP side returned an error and lost nothing; the AP side answered and lost an update.
4. R + W > N makes read and write quorums overlap, but is not the whole story.
5. Consistency is a spectrum: linearizable, sequential, causal, session guarantees, eventual.
6. PACELC: even without partitions, you trade latency against consistency.
7. Decide per feature by the cost of a wrong answer versus no answer.

Sources

1. Seth Gilbert and Nancy Lynch, Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services, ACM SIGACT News, 2002. The proof of the theorem.
2. Martin Kleppmann, A Critique of the CAP Theorem, 2015. On the ambiguity of CAP's definitions and a delay-sensitivity alternative.
3. Daniel Abadi, Consistency Tradeoffs in Modern Distributed Database System Design, IEEE Computer, 2012. PACELC.
4. Eric Brewer, CAP Twelve Years Later: How the "Rules" Have Changed, IEEE Computer, 2012.
5. Giuseppe DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007. Quorums, version vectors, and the shopping cart example.
6. Diego Ongaro and John Ousterhout, In Search of an Understandable Consensus Algorithm (Raft), 2014.
7. Kyle Kingsbury, Jepsen: analyses of distributed databases under failures.

Practise this topic: Distributed Systems & Messaging System Design

More guides