CAP Theorem Explained for Distributed Systems (Correctly)

by
Home » Distributed Systems » Replication, Consistency & Consensus » CAP Theorem Explained for Distributed Systems (Correctly)

Distributed Systems Series — Part 3.4: Replication, Consistency & Consensus

The Most Misunderstood Theorem in Distributed Systems

The CAP theorem is cited in almost every distributed systems discussion. It is also almost always cited incorrectly. Engineers use it to justify technology choices, classify databases into camps, and explain architectural decisions — often in ways that would not survive five minutes of scrutiny from anyone who has read the original work carefully.

This post explains CAP correctly. That means going beyond the slogan, understanding what the theorem actually states and does not state, examining where it applies and where it does not, and replacing the CP-vs-AP database taxonomy — which is more misleading than useful — with a framework that actually helps engineers make decisions.

To understand CAP correctly, we need to connect it to everything Part 1 and Part 2 established about Network Partitions and unreliable communication, and everything Post 3.3 established about Consistency Models and what clients observe in replicated systems.

Where CAP Came From

Eric Brewer introduced the CAP conjecture at the ACM Symposium on Principles of Distributed Computing in 2000. He proposed that distributed systems could not simultaneously provide three properties: consistency, availability, and partition tolerance. In 2002, Seth Gilbert and Nancy Lynch published a formal proof of Brewer’s conjecture, turning it into a theorem.

Brewer himself later wrote, in a 2012 retrospective, that the theorem had been widely misapplied and that the “two out of three” framing was an oversimplification that created more confusion than clarity. Understanding CAP correctly means understanding what Brewer was actually trying to say — and what the theorem’s precise formal statement actually means.

The Three Properties — Precisely Defined

The confusion around CAP starts with imprecise definitions of its three properties. Each term has a specific technical meaning that differs from its everyday usage.

Consistency in CAP means linearisability — the strongest consistency model described in Post 3.3. Every read returns the result of the most recent write. All clients see the same value at the same time. The system appears to have a single copy of the data. This is not eventual consistency, causal consistency, or any weaker model — it is specifically linearisability. This precision matters enormously: when people say “CAP means you can’t have consistency and availability,” they mean you cannot have linearisability and availability simultaneously during a partition. Weaker consistency models are a different story entirely.

Availability in CAP means that every request to a non-failed node receives a response — not an error, not a timeout, a response. The response does not need to contain the most recent data. The system just cannot refuse to answer. This is also more specific than the everyday meaning of “availability.” A system that returns an error during a partition is not available in the CAP sense even if it is technically running.

Partition tolerance means the system continues operating when the network drops or delays messages between nodes. A network partition is a situation where some nodes cannot communicate with other nodes — not because they have failed, but because the network connection between them has failed. As established in Post 1.3, partitions are not rare edge cases. They happen due to router failures, misconfigurations, cloud networking issues, and traffic spikes. In any system that communicates over a real network, partitions will occur.

Why Partition Tolerance Is Not Optional

The “pick two” framing implies that CA — consistency and availability, without partition tolerance — is a viable option. In a real distributed system running over a real network, it is not.

A system without partition tolerance would need to stop operating the moment any network message could potentially be lost. That means stopping whenever a packet is delayed, whenever a node is unreachable for any reason, whenever the network hiccups. No production distributed system does this — the unavailability would be constant and catastrophic.

What “CA without P” actually describes is a single-node system that does not distribute data across a network. A traditional relational database running on a single server is CA: it is consistent (one copy, no replication) and available (serving all requests) because it never has to tolerate a network partition between data replicas. The moment you add a second node and replicate data across a network, you are in the distributed system domain and partition tolerance is mandatory.

The real statement of the CAP theorem is therefore this: in the presence of a network partition, a distributed system must choose between consistency and availability. Outside of a partition, you can have both. During a partition, you must choose one.

What the Choice Actually Looks Like

Consider a replicated system with two nodes — Node A and Node B — both holding a copy of a bank account balance. A network partition occurs: Node A and Node B can no longer communicate.

A client sends a write to Node A: set the balance to £500. Node A accepts the write and updates its local copy. Now Node B still shows the old balance. A second client reads the balance from Node B.

The system must now choose:

Preserve consistency: Node B refuses to serve the read because it cannot confirm whether its data is current — it cannot reach Node A to check. The client receives an error or a timeout. The system is unavailable during the partition but consistent — when the partition heals, both nodes agree on the correct balance.

Preserve availability: Node B serves the read from its local copy, returning the old balance. The client receives a response, but the response is stale. The system is available during the partition but inconsistent — when the partition heals, the two nodes must reconcile their diverged state.

Neither choice is wrong in isolation. Which is correct depends entirely on the application. A bank account balance reconciliation that results in a customer being shown an incorrect balance is a serious problem. A social media post count that temporarily shows a stale number is not. The CAP theorem does not tell you which to choose — it tells you that you must choose, and that you cannot avoid the choice by clever engineering.

The 2012 AWS US-East-1 outage demonstrated this at scale. When the network partition split the region, systems had to make exactly this choice in real time. Systems designed for consistency stopped accepting writes until the partition healed — brief unavailability, but no data corruption. Systems designed for availability continued serving reads and accepting writes on both sides of the partition — continuous service, but state divergence that had to be reconciled when connectivity returned. Netflix, which had invested heavily in designing for the AP side of this trade-off, continued serving users throughout the outage while systems that had not made this choice explicit failed completely.

Why the CP-vs-AP Database Taxonomy Is Harmful

The most common misapplication of CAP is classifying databases as either “CP systems” or “AP systems” as if this were a permanent, global property of the system.

This taxonomy is harmful for three reasons.

First, most real systems are neither purely CP nor purely AP. They make different trade-offs for different operations. Cassandra, often labelled an “AP system,” supports quorum reads and writes that provide strong consistency. DynamoDB, also often labelled “AP,” offers strongly consistent reads as an explicit option. PostgreSQL with asynchronous replication can serve stale reads from replicas while remaining consistent on the primary — making it simultaneously CP (primary reads) and AP (replica reads) depending on which node serves the request.

Second, CAP only applies during partitions. The CP-vs-AP label implies a permanent system property, but the trade-off only materialises when the network actually partitions. During normal operation, a well-designed system provides both consistency and availability. Classifying a system as “AP” does not mean it provides no consistency — it means it prioritises availability over consistency specifically when a partition occurs.

Third, the classification conflates many different consistency levels. “C” in CAP means specifically linearisability. A system that provides causal consistency or read-your-writes consistency — both weaker than linearisability — is not providing CAP-C, but it is providing meaningful consistency guarantees. Calling such a system “AP” implies it provides no consistency at all, which is false and misleading.

Kyle Kingsbury, who has spent years testing distributed systems for correctness through the Jepsen project, has repeatedly documented cases where systems claimed to be “CP” but actually lost data during partitions, and systems claimed to be “AP” that actually rejected requests during partitions. The real behaviour of a system under partition is determined by its implementation, not by its marketing label.

PACELC: What CAP Leaves Out

CAP only addresses what happens during a network partition. But partitions are rare — most of the time, networks are working correctly. During normal operation, the trade-off that engineers face every day is not between consistency and availability but between consistency and latency.

In 2012, Daniel Abadi proposed the PACELC model as an extension of CAP that addresses this gap. PACELC states: if there is a partition (P), a system must choose between availability (A) and consistency (C) — this is the CAP theorem. Else (E), even when the system is operating normally, it must choose between latency (L) and consistency (C).

The latency-consistency trade-off is what engineers actually navigate daily. Synchronous replication provides strong consistency but adds write latency — every write must wait for acknowledgement from all replicas before completing. Asynchronous replication provides lower write latency but allows replicas to fall behind — reads may return stale data. Quorum reads and writes sit in the middle: faster than full synchronous replication, stronger than pure asynchronous, but still introducing coordination overhead.

PACELC classifications are more precise than CAP classifications. DynamoDB is PA/EL — it prioritises availability over consistency during partitions, and latency over consistency during normal operation. Google Spanner is PC/EC — it prioritises consistency over availability during partitions (a partition can make it unavailable), and consistency over latency during normal operation (its cross-region commits are slow but always consistent). Understanding a system through the PACELC lens gives a much clearer picture of its actual behaviour than the CP-vs-AP binary.

How Engineers Should Actually Use CAP

CAP is most useful not as a classification tool but as a design prompt — a question to answer explicitly for every operation in a distributed system.

For each critical operation, ask: if a network partition occurs while this operation is in flight, what should the system do? Return an error and preserve consistency? Return a potentially stale result and preserve availability? The answer should be explicit, documented, and consistent with the application’s correctness requirements.

Different operations within the same system can have different answers. A payment confirmation may require consistency — return an error during a partition rather than risk a double-charge. A product recommendation feed may prefer availability — return a slightly stale list rather than show an error page. A user session check may prefer availability — allow the user to continue rather than log them out because the session store is temporarily unreachable.

This per-operation thinking is more useful than system-level classification. It forces engineers to think about failure behaviour at the point where it matters — the specific operation — rather than abstractly at the system level.

CAP is a warning label, not a checklist. It tells you that a choice exists and must be made — it does not make the choice for you.

Debunking Common CAP Myths

“NoSQL databases are AP and relational databases are CP.” False. This taxonomy conflates database architecture with CAP behaviour. Many NoSQL databases offer strong consistency options. Many relational databases offer eventual consistency through asynchronous replication. The consistency behaviour of a system depends on its replication and consistency configuration, not its data model.

“You must choose AP or CP once, at system design time.” False. Many systems allow per-operation consistency configuration. Cassandra’s consistency levels, DynamoDB’s read consistency option, and MongoDB’s read and write concerns all allow applications to choose stronger or weaker consistency per request based on what that specific operation requires.

“Network partitions almost never happen in practice, so CAP rarely matters.” False, and dangerous. Partitions happen regularly in production at scale — due to hardware failures, software bugs, configuration changes, and traffic spikes. Designing a system under the assumption that partitions will not occur is designing a system that will fail in an uncontrolled way when they do. The correct assumption is that partitions will happen and the system’s behaviour during them should be deliberate, not accidental.

“CAP means distributed systems cannot be both consistent and available.” False during normal operation. CAP only constrains behaviour during a network partition. Outside of a partition, a well-designed distributed system can be both consistent and available. The theorem says nothing about normal operation.

Key Takeaways

  1. CAP states that during a network partition, a distributed system must choose between consistency (linearisability) and availability — not between all possible consistency models and availability
  2. Partition tolerance is not optional in real distributed systems — any system communicating over a real network will eventually experience partitions, making P a mandatory property
  3. The real CAP trade-off is binary only during partitions — outside of partitions, well-designed systems can provide both consistency and availability simultaneously
  4. The CP-vs-AP database taxonomy is misleading — most real systems make different trade-offs for different operations, and CAP classifications are often incorrect or misapplied
  5. PACELC extends CAP to cover normal operation — the latency-vs-consistency trade-off that engineers navigate daily is more practically relevant than the partition-time trade-off CAP describes
  6. CAP should be used as a per-operation design prompt — for each critical operation, define explicitly what the system does during a partition — not as a global system classification
  7. CAP is a warning label, not a checklist — it tells you that a choice exists and must be made deliberately, not accidentally

Frequently Asked Questions (FAQ)

What is the CAP theorem?

The CAP theorem, proven by Seth Gilbert and Nancy Lynch in 2002 based on Eric Brewer’s 2000 conjecture, states that in the presence of a network partition, a distributed system cannot simultaneously provide both consistency (linearisability — all clients see the same data) and availability (every request receives a non-error response). Outside of a partition, a well-designed system can provide both. The theorem constrains behaviour specifically during partition events.

What does “pick two” mean in CAP?

The “pick two” slogan is a simplification that creates more confusion than clarity. Partition tolerance is not optional in any real distributed system — any system communicating over a real network will experience partitions. The practical implication is that distributed systems must choose between consistency and availability specifically when a partition occurs. During normal operation, both can be provided simultaneously. The slogan “pick two” makes CAP sound like a design-time choice when it is actually a runtime constraint that surfaces during failures.

What is the difference between CAP consistency and eventual consistency?

CAP’s C specifically means linearisability — the strongest consistency model, where every read returns the most recent write and all clients see the same value simultaneously. Eventual consistency is a much weaker model — replicas may temporarily diverge and will converge eventually with no timing guarantee. A system that provides eventual consistency is not providing CAP-C. The CAP theorem says nothing about whether a system can provide eventual consistency during a partition — it can, because eventual consistency does not conflict with availability.

What is PACELC?

PACELC is a 2012 extension of CAP by Daniel Abadi that addresses what CAP leaves out: the trade-off during normal (non-partition) operation. PACELC states: during a Partition (P), choose between Availability (A) and Consistency (C); Else (E), even during normal operation, choose between Latency (L) and Consistency (C). The latency-consistency trade-off — synchronous vs asynchronous replication, quorum reads vs single-replica reads — is what engineers navigate every day, making PACELC a more practically useful framework than CAP alone.

Are Cassandra and DynamoDB AP systems?

Only partially and only during partitions. Both Cassandra and DynamoDB prioritise availability over consistency when a network partition occurs — they continue accepting writes on both sides of the partition rather than refusing requests. But both also offer configurable consistency levels that can provide strong consistency at the cost of availability and latency. Calling them “AP systems” without qualification implies they provide no consistency guarantees, which is false. The CP-vs-AP taxonomy oversimplifies real system behaviour.

How should I apply CAP in system design?

Use CAP as a per-operation design prompt, not a global system classification. For each critical operation in your system, ask: if a network partition occurs while this operation is in flight, what should happen? Accept an error to preserve consistency, or return a potentially stale result to preserve availability? Document the answer explicitly. Different operations can have different answers. Payment confirmations may require consistency. Product feeds may prefer availability. Making these decisions explicit before incidents occur is far better than discovering the system’s default behaviour during a production outage.

Continue the Series

Series home: Distributed Systems — Concepts, Design & Real-World Engineering

Part 3 — Replication, Consistency & Consensus

Previous: ← 3.3 — Consistency Models: Strong, Eventual, Causal and Session

Next: 3.5 — Quorums and Voting in Distributed Systems →

Not read Parts 1 or 2 yet?

Discover more from Rahul Suryawanshi

Subscribe now to keep reading and get access to the full archive.

Continue reading