Database Series : CAP Theorem
DB Series Core Concept Part 3: The Trade-off That Defines Distributed Systems
Introduction
In 1998, Eric Brewer, then a professor at UC Berkeley, was building large-scale distributed systems at Inktomi. He noticed a pattern: every system seemed to make a fundamental trade-off between three desirable properties — and no system could fully achieve all three simultaneously. He formalized this observation as a conjecture in his 2000 PODC keynote. Two years later, Seth Gilbert and Nancy Lynch at MIT published a formal proof. The CAP theorem was born.
Today, CAP theorem is arguably the most cited concept in distributed systems interviews, architecture discussions, and database documentation. Yet it is also one of the most misunderstood. Engineers often recite “pick any two” as if it’s a design menu, not realizing the theorem is making a much more specific — and nuanced — statement.
This article covers CAP theorem in full: what it actually says, what it doesn’t say, how real systems navigate it, and what comes after it.
The Three Properties
Before understanding the trade-off, we need crisp definitions.
Consistency © — Every read receives the most recent write or an error.
This is linearizability in formal terms: the system behaves as if there is a single copy of the data, and all operations on it are atomic and instantaneous. If you write x = 5 and then immediately read x, you get 5. No node returns stale data. This is not the same as "eventual consistency" — CAP consistency is a strong, real-time guarantee.
Important: this “C” is different from the “C” in ACID (which means a transaction takes the database from one valid state to another). CAP’s C is specifically about read-after-write freshness across nodes.
Availability (A) — Every request receives a response (not an error), though it may not be the most recent data.
The system remains operational and responsive. Every non-failing node must return a response within a reasonable time. Crucially, “available” in CAP means no timeouts, no errors — just a response. A system that returns an error for some requests under partition is not available in the CAP sense.
Partition Tolerance (P) — The system continues to operate despite arbitrary message loss or delay between nodes.
A network partition is when nodes in the cluster cannot communicate — due to a dropped link, a misconfigured firewall, a crashed router, or simply high latency. Partition tolerance means the system keeps running even when some messages between nodes are lost or delayed.
Why You Can’t Have All Three
This is the core of the theorem. Let’s reason through it informally, then look at the formal argument.
Imagine a distributed system with two nodes: Node A and Node B, both serving client requests, both holding a copy of some data.
A client writes x = 10 to Node A.
Now a network partition occurs. Node A and Node B cannot talk to each other.
A second client reads x from Node B.
What should happen?
You have exactly two choices:
- Return
x = 10(the latest value) — but Node B doesn't have it yet because the partition blocked replication. So to be consistent, you'd have to either refuse the request or block until the partition heals. That means you've sacrificed Availability. - Return whatever Node B has (possibly stale) — the client gets a response immediately. But you’ve sacrificed Consistency.
There is no third option. The partition is given — you can’t un-partition the network through software. So under partition, you must choose between C and A.
The formal proof by Gilbert and Lynch is more rigorous, using an asynchronous network model with two nodes and showing that linearizability + availability + partition tolerance leads to a contradiction. The key insight: in an asynchronous network, there’s no way to distinguish a very slow node from a failed one, so any system that claims partition tolerance must also handle message loss, and handling message loss forces the C vs. A trade-off.
The real CAP insight is: in the presence of a partition, choose between Consistency and Availability. Outside of partitions, you can have both.
The CAP Triangle
Let’s visualize the three zones:
The CA Zone: A Distributed Myth
The Venn diagram shows a CA zone — systems with Consistency and Availability but without Partition Tolerance. In practice, this zone is theoretical for distributed systems.
Here’s why: in any system that runs across more than one machine, network partitions are not optional. Networks drop packets. Links fail. Data centers lose connectivity. You cannot opt out of partition tolerance if you want a multi-node system. The only way to achieve CA is to run on a single node — which sidesteps the “distributed” part entirely.
Traditional single-node RDBMS (Postgres, MySQL on one server) are CA — they’re consistent and available, but they’re not distributed, so partition tolerance is irrelevant. Once you shard, replicate, or cluster them, they slide into CP or AP territory.
The practical restatement of CAP: In a real distributed system, you always have P. The design decision is: when a partition occurs, do you prioritize C or A?
What Happens During a Partition
CP Systems: Consistency Over Availability
A CP system says: “When in doubt, refuse.” During a partition, rather than risk returning stale data, the system rejects or blocks requests on isolated nodes.
Characteristics:
- Guarantees linearizability (or sequential consistency)
- May return errors or timeouts during partitions
- Writes may be rejected until a quorum of nodes agrees
- Suitable for use cases where wrong data is worse than no data
Examples and how they enforce C:
Apache ZooKeeper uses a leader-based consensus protocol (ZAB — Zookeeper Atomic Broadcast). All writes go through the leader, and a majority quorum must acknowledge a write before it’s committed. If the leader is partitioned from a majority of nodes, writes stop. Reads from a minority partition may also be blocked or return stale data depending on configuration.
etcd (which backs Kubernetes) uses Raft consensus. Every write requires acknowledgment from a majority (quorum) of nodes. Under partition, the minority partition becomes read-only and refuses writes. The majority partition keeps serving. No inconsistency is possible — at the cost of the minority partition being unavailable.
HBase uses HDFS for storage and ZooKeeper for coordination. Under partition, regions may become unavailable rather than serve inconsistent data.
MongoDB (in its default configuration with Write Concern majority) also behaves as CP — a write is only acknowledged once a majority of replicas confirm it, and under partition, the minority replica set stops accepting writes.
AP Systems: Availability Over Consistency
An AP system says: “Keep serving, reconcile later.” Every node answers every request, even during partitions — but some nodes may return data that isn’t the latest write.
Characteristics:
- Always responds (no errors from availability perspective)
- May return stale, diverged, or conflicting data during partition
- Reconciliation (conflict resolution) happens post-partition via eventual consistency mechanisms
- Suitable for use cases where responding is more important than perfect accuracy
Examples and their AP mechanisms:
Apache Cassandra is the canonical AP system. It uses a decentralized, leaderless architecture where any node can accept writes. Reads and writes use a configurable consistency level (ONE, QUORUM, ALL). With ConsistencyLevel.ONE, a single node responds immediately — this is highly available but potentially stale. Cassandra uses last-write-wins (LWW) based on timestamps for conflict resolution and anti-entropy repair for eventual consistency.
Amazon DynamoDB defaults to eventual consistency for reads, offering a “strongly consistent” option that makes it behave more like CP (at higher latency cost). The eventual consistency path is AP.
CouchDB takes an “optimistic replication” approach — accept writes on any node, sync asynchronously, use application-defined conflict resolution.
Get Abhinav Thakur’s stories in your inbox
Join Medium for free to get updates from this writer.
DNS is the original AP system. Every DNS resolver caches records with a TTL. During a partition or update, different resolvers may return different IPs for the same hostname. DNS prioritizes availability and eventual consistency over real-time accuracy.
Real-World System Classification
Real Systems on the CAP Spectrum
Consistency Models: There’s a Whole Spectrum
One thing CAP theorem doesn’t tell you is how consistent or how available a system should be outside of a partition. In practice, consistency is not binary — there is a rich spectrum of models between “linearizable” and “eventual.”
Linearizability is the strongest model and what CAP’s “C” refers to. Eventual consistency is the weakest. Real systems often operate somewhere in the middle, tuned by workload requirements.
The “Tunable Consistency” Escape Hatch
Modern systems like Cassandra let you configure the consistency level per operation. This means a single system can behave like CP or AP depending on how you configure it:
The formula: if W + R > N (where W = write quorum, R = read quorum, N = replication factor), you get strong consistency, because reads and writes always overlap in at least one node. With N=3, W=2, R=2, you have 2+2 > 3 — strong consistency guaranteed.
This tunability means CAP should be thought of as a spectrum dial, not a binary toggle.
Beyond CAP: The PACELC Theorem
CAP theorem only talks about what happens during a partition. But partitions are rare. What about the normal, non-partition case? This is the gap that the PACELC theorem, proposed by Daniel Abadi in 2012, fills.
PACELC states:
If there is a Partition (P), a system must choose between Availability (A) and Consistency © — else (E), when the system is running normally, it must choose between Latency (L) and Consistency ©.
The insight: even without partitions, achieving consistency costs latency. To confirm a write is linearizable, you need acknowledgment from multiple nodes — that takes time. If you want low latency, you accept weaker consistency (like returning from a single node without waiting for replicas).
PACELC is a more complete model for everyday architectural decisions. Most systems aren’t partitioned most of the time, so the E→L/C tradeoff is the one you’re actually designing for.
CAP vs ACID vs BASE
CAP theorem, ACID, and BASE are often discussed together but they operate at different levels.
ACID (Atomicity, Consistency, Isolation, Durability) is a transaction model for single databases. It describes how a single database handles transactions. The “C” in ACID means the database enforces integrity constraints — it’s a different “C” from CAP.
BASE (Basically Available, Soft State, Eventually Consistent) is a philosophy for AP distributed systems, coined as the opposite of ACID:
- Basically Available: the system appears available most of the time, though some parts may be slow or degraded
- Soft State: data may be in an intermediate, inconsistent state (replicas not yet synchronized)
- Eventually Consistent: given no new writes, the system will converge to a consistent state
Neither ACID nor BASE is universally better. The choice depends on your domain. Financial transactions need ACID. A social media timeline counter can tolerate BASE.
Common Misconceptions About CAP
1. “CAP means you get to pick two properties forever.”
No. CAP says: during a partition, you must sacrifice either C or A. During normal operations, you can have both. The choice is about partition behavior, not a permanent architectural state.
2. “Partition Tolerance is optional.”
In a single-node system, yes. In any distributed system connected via a network, no. Network failures are not hypothetical — they’re inevitable. Every distributed system must be partition tolerant or it risks total failure.
3. “AP systems have no consistency.”
False. AP systems have eventual consistency — data will converge. Many also support partial consistency guarantees like read-your-writes or monotonic reads. Cassandra with QUORUM is often "consistent enough" for many workloads.
4. “CP systems are always available except during partitions.”
Mostly true but nuanced. CP systems can still go down for other reasons — bugs, exhausted resources, software failures. And during partitions, even CP systems must decide which partition “wins.” Minority partitions become unavailable, but the majority partition stays up.
5. “CAP theorem is the final word on distributed system trade-offs.”
No — it’s a starting point. It doesn’t model latency (PACELC does), doesn’t address partial failures, clock drift, Byzantine faults, or the nuances of different consistency models. It’s a useful mental model, not a complete specification.
CAP Decision Framework for Architects
Practical Guidance for Architects
1. Separate your data by consistency requirement.
Most large systems don’t use a single data store. The user authentication service (CP — wrong login is unacceptable) can be backed by etcd or a strongly consistent RDBMS, while the activity feed (AP — showing yesterday’s likes is fine) runs on Cassandra. Polyglot persistence lets you apply the right CAP profile to each domain.
2. Quantify the cost of inconsistency.
For AP systems, ask: what is the blast radius of serving stale data? If a shopping cart shows a price that’s 5 seconds old, the customer might get a slightly different total at checkout — recoverable. If a medical drug dosage system shows a value 5 seconds old — catastrophic. The answer determines whether AP is viable.
3. Model your conflict resolution strategy upfront.
AP systems that accept concurrent writes to the same record will produce conflicts. How will you resolve them? Options include: last-write-wins (LWW based on timestamp), application-level merge logic, CRDTs (Conflict-free Replicated Data Types), or user-facing conflict prompts. The strategy must be designed before you write the first line of code.
4. Don’t confuse CAP availability with operational availability (SLA).
CAP “availability” means every request gets a non-error response. This is different from “99.99% uptime SLA.” A CP system like ZooKeeper can have excellent uptime SLAs while still being “CAP unavailable” during partitions on minority nodes.
5. Measure partition probability in your environment.
In a well-managed single datacenter with quality networking hardware, partitions are rare but not zero. Across multiple availability zones or regions, network partitions are a regular operational occurrence. Your CAP strategy should be calibrated to your actual deployment topology.
6. Consider using CP for writes and AP for reads (CQRS integration).
A common pattern is to use a CP store for the authoritative write path (ensuring no double-booking, no lost updates) and project the data asynchronously into an AP read model (Cassandra or Elasticsearch) for high-throughput queries. This is CQRS — and it lets you have strong consistency where it matters without paying the latency cost on reads.
CAP in Multi-Region Deployments
Multi-region adds a new dimension to CAP reasoning. Cross-region replication introduces latencies of 50–200ms between nodes, making the “synchronous replication = consistency” approach extremely expensive.
Google Spanner is worth special mention. It uses GPS and atomic clocks (TrueTime) to bound clock uncertainty to ~7ms globally. This lets it commit transactions across regions with near-linearizable consistency — the closest thing to “have all three” that exists, at enormous engineering cost.
The CAP Theorem’s Limitations
Eric Brewer himself, in a 2012 retrospective, acknowledged the theorem’s limitations:
The theorem is binary. Real systems don’t have “yes/no” availability or consistency — they have degrees. A system might be 99.9% consistent (one stale read in a thousand) and still be practically acceptable. The binary framing oversimplifies.
Partition duration matters. A 100ms partition is very different from a 10-hour partition. During a brief network hiccup, a CP system might just introduce a short delay (acceptable). The theorem doesn’t model partition duration or recovery behavior.
Availability is undefined in the theorem. “Every request gets a response” — but within what time limit? A system that responds in 30 seconds is technically available per CAP but useless in practice. Latency is the missing variable.
The proof assumes asynchronous networks. In a synchronous network (bounded message delivery), you can build systems with all three properties — the proof breaks down. No real internet-scale system has a synchronous network, but local networks approximate it.
These limitations are why PACELC, Harvest/Yield framework, and other models have been proposed to supplement CAP.
Summary
CAP theorem is not a checklist — it is a lens. Once you truly internalize it, you stop asking “which database should I use?” and start asking “what does my system owe its users when the network lies to them?” That shift in thinking is what separates engineers who configure distributed systems from engineers who design them. Partitions will come — at 2 AM on a Friday, during your highest-traffic moment, at the worst possible time. The systems that survive gracefully are not the ones built on the fastest hardware or the trendiest stack, but the ones whose architects made a deliberate, eyes-open choice between consistency and availability long before the incident began. CAP theorem is that decision, written in advance.
Thank you for reading until the end. Before you go:
- Please consider clapping and following the writer! 👏
- Connect me on LinkedIn
