CAP Theorem and Consistency Models Explained Without the Myths

"CAP theorem: consistency, availability, partition tolerance; pick two." Almost every candidate has heard it, and many repeat it in interviews, then say "so we chose AP" as if that settled the design. It is one of the most misunderstood ideas in the field. The slogan is not exactly wrong, but it hides what the theorem says, when it applies, and the trade-off you actually face every day, which is not about partitions at all.

This article first builds a clear vocabulary for "consistency" when data lives in several places, then states CAP precisely, adds PACELC, works through quorum arithmetic, and ends with the practical skill: choosing a consistency level per feature.

• What consistency means for replicated data (and how it differs from the C in ACID).
• The main consistency models: linearizable, causal, session guarantees and eventual.
• What the CAP theorem states, and the common myths around it.
• PACELC: the latency-versus-consistency trade-off when nothing is broken.
• Quorums: N, W and R, with a program that checks overlap.
• Resolving conflicts when replicas accept concurrent writes.
• How to choose consistency per feature, with worked examples.

• In ACID (article 12), consistency means a transaction keeps the database valid: constraints hold.
• In distributed systems, consistency describes what reads may return while copies of the data are being updated: will a reader see the latest write, an older value, or values in a strange order?

This article is about the second meaning. When someone says "eventually consistent", they mean that one.

A consistency model is a promise about which results reads may return. Jepsen, which tests databases' guarantees, maintains a reference describing many models and how they relate (Consistency models). For system design, five are enough.

The system behaves as if there were a single copy of the data, and every operation takes effect at one instant between its start and finish. Once a write completes, every read that starts afterwards sees it (or a later value), whichever replica serves it (Linearizability).

• Example need: "seat C14 is booked" must be seen by everyone the moment the booking succeeds; a username, once taken, must be taken for everyone.
• Cost: replicas must coordinate on writes (or reads must go to a leader), adding latency, and during a network partition some requests must be refused.

Operations that are causally related are seen by everyone in the same order; operations that are unrelated (concurrent) may be seen in different orders by different readers.

• Example need: a reply must never appear before the message it replies to; "unfriend X" followed by "post a private photo" must not let X see the photo.
• Cost: lower than linearizability; the system must track dependencies.

Weaker promises scoped to one client's session, which fix the most visible anomalies cheaply:

• Read your writes: a user always sees their own changes.
• Monotonic reads: a user never sees data go backwards in time.
• Monotonic writes: a user's writes are applied in the order they made them.

Article 15 showed how to provide read-your-writes with replica routing.

If writes stop, all replicas eventually converge to the same value. Before then, reads may return stale values, and different replicas may disagree. There is no bound on how long "eventually" takes, though in practice it is usually milliseconds to seconds.

• Example fit: like counts, view counts, follower counts, feed contents, DNS records, cached product descriptions.
• Benefit: replicas can accept and serve requests without waiting for each other, which helps latency and availability.

Eric Brewer proposed the idea in 2000; Seth Gilbert and Nancy Lynch proved a formal version in 2002 (Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services). In their terms:

• C (consistency) means linearizability (they call it atomic consistency): every read sees the most recent completed write.
• A (availability) means every request received by a non-failing node gets a non-error response, eventually.
• P (partition tolerance) means the system keeps operating even when the network loses arbitrary messages between nodes.

The theorem: when a network partition occurs, a replicated system cannot guarantee both C and A. A node cut off from the others must either answer (and risk returning stale data or accepting a conflicting write: giving up C) or refuse or wait (giving up A).

   Region West                     Region East   Replica W  ---- link cut ----   Replica E   client: "book seat C14"         client: "book seat C14"

• Choose consistency (CP behaviour): the side that cannot reach a majority refuses the booking ("please try again"). No double booking, but some users get errors.
• Choose availability (AP behaviour): both sides accept their booking. Everyone gets an answer, and after the link heals you discover two bookings for one seat, which must be resolved somehow.

Brewer's article also recommends treating partitions explicitly: detect them, enter a mode that limits risky operations, and recover by reconciling afterwards.

Daniel Abadi pointed out that CAP says nothing about normal operation, yet the most important trade-off is present all the time (Consistency Tradeoffs in Modern Distributed Database System Design):

If there is a Partition, choose Availability or Consistency; Else, choose Latency or Consistency.

Keeping replicas strongly consistent means waiting for other replicas (often in other zones or regions) before answering. That costs latency on every request, not only during rare partitions. Many systems that relax consistency do so to be fast, not because partitions are common.

Examples from earlier articles:

• Synchronous replication across regions added about 150 ms to every write (article 15): EC, paying latency.
• Asynchronous read replicas answer fast but may be stale: EL.

In leaderless or quorum-based replication (article 15), each piece of data lives on N replicas. A write is considered successful when W replicas acknowledge it; a read asks R replicas and takes the newest version among the answers.

If W + R > N, every set of W replicas overlaps every set of R replicas in at least one node, so every read contacts at least one replica that has the latest acknowledged write. The program below checks this by brute force for N = 3, and also shows how many replicas can be down while writes and reads still succeed.

// File: QuorumDemo.javaimport java.util.ArrayList;import java.util.List;public class QuorumDemo {    // Every subset of n replicas with exactly k members, as bit masks.    static List<Integer> subsets(int n, int k) {        List<Integer> out = new ArrayList<>();        for (int mask = 0; mask < (1 << n); mask++) {            if (Integer.bitCount(mask) == k) {                out.add(mask);            }        }        return out;    }    // True if every possible write set shares at least one replica with every possible read set.    static boolean alwaysOverlap(int n, int w, int r) {        for (int writeSet : subsets(n, w)) {            for (int readSet : subsets(n, r)) {                if ((writeSet & readSet) == 0) {                    return false;                }            }        }        return true;    }    public static void main(String[] args) {        int n = 3;        System.out.println("N = " + n + " replicas");        for (int w = 1; w <= n; w++) {            for (int r = 1; r <= n; r++) {                System.out.printf("W=%d R=%d  overlap guaranteed: %-5s  writes survive %d down, reads survive %d down%n",                        w, r, alwaysOverlap(n, w, r), n - w, n - r);            }        }    }}

N = 3 replicasW=1 R=1  overlap guaranteed: false  writes survive 2 down, reads survive 2 downW=1 R=2  overlap guaranteed: false  writes survive 2 down, reads survive 1 downW=1 R=3  overlap guaranteed: true   writes survive 2 down, reads survive 0 downW=2 R=1  overlap guaranteed: false  writes survive 1 down, reads survive 2 downW=2 R=2  overlap guaranteed: true   writes survive 1 down, reads survive 1 downW=2 R=3  overlap guaranteed: true   writes survive 1 down, reads survive 0 downW=3 R=1  overlap guaranteed: true   writes survive 0 down, reads survive 2 downW=3 R=2  overlap guaranteed: true   writes survive 0 down, reads survive 1 downW=3 R=3  overlap guaranteed: true   writes survive 0 down, reads survive 0 down

Read the table as a menu of trade-offs:

• W=2, R=2 (a common choice for N=3): reads and writes overlap, and both keep working with one replica down.
• W=1, R=1: fastest and most available, but a read may miss the latest write: eventual consistency.
• W=3, R=1: fast reads that always overlap, but a single replica failure blocks all writes.
• W=1, R=3: fast, very available writes, but any replica failure blocks reads that need the overlap.

Overlap is necessary for reading the latest write, but not sufficient for linearizability. Concurrent writes may be ordered differently on different replicas; a write that reached only some replicas before failing can be seen by some readers and not others; and if conflicts are resolved by "latest timestamp", clock skew (article 18) can choose the wrong winner. Systems add mechanisms such as read repair, versioning and, for linearizable operations, consensus (article 22). Amazon's Dynamo paper also describes sloppy quorums with hinted handoff: when the usual replicas are unreachable, writes go temporarily to other nodes and are handed back later, which favours availability over strict overlap (Dynamo).

If replicas accept writes independently (AP behaviour, multi-leader replication, or W=1), two replicas can end up with different versions. Options:

Amazon's Dynamo paper describes the shopping-cart example: when concurrent versions of a cart appear, they are merged so that added items are never lost, accepting that a deleted item can occasionally reappear (Dynamo). That is a business decision about which mistake is cheaper.

The practical skill is not "is the system CP or AP?" but "what does each operation need?"

Suppose Pixly expands to serve users in India and Europe, with a deployment in each region.

• User accounts and usernames: must be unique globally. Writes go to one home region (a single primary); signups from Europe pay the cross-region latency on that one rare operation. During a partition, signups in the cut-off region fail with a friendly error (CP for this operation).
• Photos and captions: each photo is owned by its uploader's home region; replicated asynchronously to the other region for fast reads there. Readers abroad may see a new photo a second late (eventual), and uploaders always read their own from their home region (read your writes).
• Likes: counted in each region and merged as counters (merge-friendly; a CRDT-style counter). Totals converge after a partition (AP for this operation).
• Feeds: built per region from replicated events; eventual.

Asked "is Pixly CP or AP?", the right answer is: "Different operations make different choices: usernames and anything involving money are CP; likes, feeds and photo replication are AP with session guarantees for users' own data."

• Reciting "pick two" and labelling the whole system CP or AP.
• Assuming CAP forces a sacrifice when there is no partition.
• Forgetting the latency cost of strong consistency (PACELC).
• Believing W + R > N alone gives linearizability.
• Using last-write-wins for data where losing a write matters.
• Strong consistency everywhere "to be safe", paying latency for counters and feeds.

• Define terms before using them: "by strong consistency I mean linearizable for this operation".
• Choose per feature, with a reason tied to the cost of a wrong answer.
• If you use quorums, give N, W and R and what they tolerate.
• If asked about CAP, state it precisely: during a partition, choose between consistency and availability for each operation; otherwise the trade-off is latency.

• Next: Idempotency, Retries and Message Delivery Guarantees, which makes retries safe in a world of partial failure and eventual consistency.
• Later: consensus for linearizable coordination (article 22) and multi-region design (article 24).