In the last few chapters we copied data onto many machines (Database Replication) and split it across many machines (Database Sharding & Partitioning, Consistent Hashing). The moment data lives on more than one machine, the machines have to talk over a network, and networks fail. Cables get cut, switches reboot, cloud regions lose connectivity.
The CAP theorem tells us what a distributed system can and cannot promise when that happens, and PACELC extends it to the normal, healthy case. Together they give you the vocabulary to justify every database choice in a system design interview.
CAP theorem: when a network partition occurs, a distributed system that stores replicated data must choose between Consistency (every read sees the latest write) and Availability (every request gets a non-error response). It cannot guarantee both.
A Bit of History
2000: Eric Brewer presented the idea as a conjecture in his keynote at the ACM PODC conference.
2002: Seth Gilbert and Nancy Lynch (MIT) formally proved it, with precise definitions.
2010–2012: Daniel Abadi argued that CAP ignores the more common trade-off, latency, and proposed PACELC. Brewer's own 2012 article "CAP Twelve Years Later" explained why the popular "pick any two" summary is misleading.
The Three Properties, Precisely
C: Consistency
Every read returns the value of the most recent completed write (or an error). The whole system behaves as if there were a single copy of the data. Formally, Gilbert and Lynch defined it as linearizability, a guarantee we study in detail in Consistency Models.
A: Availability
Every request received by a non-failing node must eventually get a non-error response. Note how strong this is: not "most requests" and not "the system has 99.9% uptime", but every working node must answer.
P: Partition Tolerance
The system keeps working even if the network loses or delays arbitrarily many messages between nodes, splitting them into groups that cannot communicate.
Normal Partition
[Node 1] ◄──────► [Node 2] [Node 1] ✕ ✕ ✕ [Node 2]
▲ ▲ ▲ ▲
clients clients clients clients
(both nodes are alive; they just
cannot talk to each other)
A partition is not a crash. Both sides are running and receiving client requests; they simply cannot coordinate.
Why You Cannot Have All Three
The proof idea is short enough to explain on a whiteboard.
Two replicas, M (Mumbai) and D (Delhi), both store
x = 1.A partition cuts the link between them.
A client writes
x = 2to M. If the system is available, M must accept and acknowledge it, but it cannot tell D.Another client reads
xfrom D. If the system is available, D must answer, and the only value it has isx = 1, a stale value, so consistency is broken.To stay consistent, D (or M) would have to refuse or delay the request until the partition heals, breaking availability.
There is no clever trick around this: D cannot report a write it has no way of hearing about.
Simulation: Booking the Last Train Seat
Let us make it concrete with three replicas (Mumbai, Chennai, Delhi) and one seat left. The network splits into {Mumbai, Chennai} and {Delhi}. In CP mode, a node may only accept a booking if it can reach a majority of replicas (as Raft- or Paxos-based systems do). In AP mode, every node accepts bookings and the replicas are merged later.
SEATS = 1 # one seat left on the train
class Cluster:
def __init__(self, mode, nodes):
self.mode = mode # "CP" or "AP"
self.bookings = {n: [] for n in nodes} # each replica's copy
self.groups = [set(nodes)] # who can talk to whom
def partition(self, *groups):
self.groups = [set(g) for g in groups]
def reachable(self, node):
return next(g for g in self.groups if node in g)
def book(self, node, user):
group = self.reachable(node)
if self.mode == "CP" and len(group) <= len(self.bookings) // 2:
return f"{user} via {node}: ERROR - no majority, try again later"
if len(self.bookings[node]) >= SEATS:
return f"{user} via {node}: sold out"
for n in group: # replicate to every reachable copy
self.bookings[n].append(user)
return f"{user} via {node}: booked"
def heal(self):
merged = sorted({u for b in self.bookings.values() for u in b})
self.groups = [set(self.bookings)]
if len(merged) > SEATS:
return f"after heal: {len(merged)} bookings for {SEATS} seat -> {merged} (conflict!)"
return f"after heal: bookings = {merged}"
for mode in ("CP", "AP"):
c = Cluster(mode, ["Mumbai", "Chennai", "Delhi"])
c.partition(["Mumbai", "Chennai"], ["Delhi"])
print(f"--- {mode} ---")
print(c.book("Delhi", "Vikram")) # minority side
print(c.book("Mumbai", "Asha")) # majority side
print(c.heal())
Output:
--- CP ---
Vikram via Delhi: ERROR - no majority, try again later
Asha via Mumbai: booked
after heal: bookings = ['Asha']
--- AP ---
Vikram via Delhi: booked
Asha via Mumbai: booked
after heal: 2 bookings for 1 seat -> ['Asha', 'Vikram'] (conflict!)
Both outcomes are "correct" for their design:
CP: Vikram got an error (the system was unavailable to him), but the seat was never double-sold. Notice that the majority side kept working, so a CP system is not "down" during a partition; only the minority side refuses requests.
AP: everyone got an answer, but the seat was sold twice. After the partition heals, the application must resolve the conflict (refund one person, upgrade them, or apologise).
The "Pick Any Two" Myth
CAP is often drawn as a triangle where you pick two corners: CA, CP or AP. This is misleading.
Partitions are not a choice. In any system that communicates over a network, messages can be lost. You cannot "give up P" any more than you can give up gravity.
So the real choice is only made during a partition: stay consistent (and reject some requests) or stay available (and risk stale or conflicting data).
When there is no partition, you can have both C and A. CAP says nothing about the normal case.
"CA" really means "not distributed", for example a single-server PostgreSQL. It is consistent and available until that one server or its network fails.
Is there a network partition right now?
/ \
Yes No
| |
Choose: Consistency or CAP says nothing.
Availability (PACELC: choose Latency
(CP) (AP) or Consistency)
The choice is also not all-or-nothing. A system can make different choices for different data or operations (CP for payments, AP for the like counter), and the trade-off only applies to the requests affected by the partition.
CP vs AP Systems
| CP | AP | |
|---|---|---|
| During a partition | Minority side rejects or times out; no stale or conflicting data | Every reachable node answers; data may be stale; conflicts resolved later |
| Typical mechanisms | Single leader elected by majority, consensus (Raft, Paxos, Zab), majority quorums | Leaderless or multi-leader replication, hinted handoff, last-write-wins, CRDTs, read repair |
| Examples (default behaviour) | etcd, ZooKeeper, Consul, HBase, Google Spanner, CockroachDB, MongoDB with majority read/write concerns | Cassandra and ScyllaDB at low consistency levels, Riak, CouchDB, DNS, DynamoDB eventually consistent reads |
| Good for | Money, inventory, seat booking, leader election, configuration, locks | Likes, views, feeds, shopping carts, product catalogs, presence ("online") indicators |
Many Databases Are Tunable
Labels like "Cassandra is AP" describe a default configuration, not a law.
Cassandra: each query picks a consistency level.
ONEis fast and available;QUORUMreads plusQUORUMwrites satisfy R + W > N (from Database Replication), so a read sees the latest acknowledged write, but requests fail if a majority of replicas is unreachable.DynamoDB: reads are eventually consistent by default; you can request strongly consistent reads within a Region. Global tables can be created in multi-Region eventual consistency mode (MREC) or, since mid-2025, multi-Region strong consistency mode (MRSC).
MongoDB: write concern and read concern (and whether you read from secondaries) decide where you sit on the spectrum.
In an interview, always say "in this configuration" rather than labelling a product.
CAP Words That Mean Something Else
| Term | In CAP | Elsewhere |
|---|---|---|
| Consistency | Every read sees the latest write (linearizability) | In ACID: transactions keep the database valid according to its constraints |
| Availability | Every non-failing node returns a non-error response | In SLAs (see Latency, Throughput & Availability): the percentage of time the service is up, such as 99.99% |
A CP system can still have excellent SLA availability (Spanner advertises up to 99.999%), because partitions are rare and the majority side keeps serving. Brewer himself wrote in 2017 that Spanner is technically CP but "effectively CA" in practice, since Google's private network makes partitions extremely rare.
PACELC: What Happens When the Network Is Fine?
Partitions are rare. Most of the time the network works, yet distributed databases still make a trade-off on every single request: should a write wait for other replicas to confirm before answering?
PACELC: if there is a Partition (P), the system trades off Availability (A) against Consistency (C); Else (E), during normal operation, it trades off Latency (L) against Consistency (C).
P ──► A or C (rare: network partition)
if ─┤
E ──► L or C (always: normal operation)
Why Consistency Costs Latency
To be strongly consistent, a write must reach other replicas (often a majority) before it is acknowledged. That takes at least one network round trip, and physics sets a lower bound. Light in optical fibre travels at roughly 200,000 km/s:
from math import radians, sin, cos, asin, sqrt
def km(a, b):
(la1, lo1), (la2, lo2) = [(radians(x), radians(y)) for x, y in (a, b)]
h = sin((la2-la1)/2)**2 + cos(la1)*cos(la2)*sin((lo2-lo1)/2)**2
return 2*6371*asin(sqrt(h))
mumbai, delhi, ashburn = (19.076, 72.878), (28.614, 77.209), (39.044, -77.487)
FIBER = 200_000 # km/s, roughly 2/3 of c
for name, p in (("Mumbai-Delhi", delhi), ("Mumbai-Ashburn(US East)", ashburn)):
d = km(mumbai, p)
print(f"{name}: {d:,.0f} km, minimum RTT in fibre = {2*d/FIBER*1000:.1f} ms")
Output:
Mumbai-Delhi: 1,148 km, minimum RTT in fibre = 11.5 ms
Mumbai-Ashburn(US East): 12,854 km, minimum RTT in fibre = 128.5 ms
These are straight-line minimums; real cable routes are longer, so real round trips are higher. If every write must be confirmed by a replica in another continent, each write pays well over 100 ms. A system that answers from the local replica and replicates in the background (choosing L) is much faster but may serve stale data (giving up C).
PACELC Classification
| Class | Meaning | Examples (default settings) |
|---|---|---|
| PA/EL | Availability during partitions, low latency otherwise | Dynamo-style systems: Cassandra, Riak, ScyllaDB; DynamoDB with eventually consistent reads |
| PC/EC | Consistency always, paying with availability and latency | Spanner, CockroachDB, HBase, VoltDB, etcd/ZooKeeper |
| PA/EC | Consistent in normal operation, but stays available during partitions | MongoDB was placed here in Abadi's 2012 paper (behaviour depends heavily on read/write concern settings) |
| PC/EL | Low latency normally, but consistency during partitions | Yahoo PNUTS (Abadi's example) |
PACELC is arguably more useful than CAP in daily design work, because the ELC trade-off affects every request, while the PAC trade-off only applies during rare failures.
Applying CAP/PACELC in a Design Interview
Do not just say "I'll use an AP database". Decide per piece of data what the business can tolerate:
| Data | What is worse? | Choice |
|---|---|---|
| Bank balance, UPI payments | Showing a wrong balance or double-spending | CP / EC: reject during partition, accept extra latency |
| Train or movie seat booking | Selling one seat twice | CP for the booking step (the seat-map display can be AP) |
| Like counts, view counts | The feature being down | AP / EL: a count off by a few for a few seconds is fine |
| Shopping cart | Customer cannot add items | AP: merge carts after the partition (the original Dynamo use case) |
| Chat messages | Messages lost or reordered | Usually AP for delivery, with ordering kept per conversation |
| Service configuration, leader election | Two leaders at once | CP (etcd, ZooKeeper) |
A good answer sounds like: "Seat inventory needs linearizable updates, so I'll keep it in a CP store and accept that during a partition some booking requests fail with 'try again'. The seat map shown while browsing can be served from an AP cache, since slightly stale availability is acceptable and the final booking step re-checks."
Common Mistakes
"I'll choose a CA system." Not possible for a distributed system; partitions happen. Say what you do during a partition.
Thinking CP systems go completely down during a partition. Usually only the minority side stops serving; the majority side continues.
Confusing CAP consistency with ACID consistency, or CAP availability with SLA uptime.
Labelling a product permanently CP or AP without stating the configuration.
Forgetting latency. Even without any failures, strong consistency across regions costs a round trip per write: that is PACELC's ELC part.
Treating it as binary for the whole system. Different data in the same app can make different choices.
Interview Questions
1. State the CAP theorem correctly.
In a distributed data store, when a network partition occurs, the system cannot guarantee both consistency (linearizable reads of the latest write) and availability (every non-failing node returns a non-error response). It must sacrifice one of them for the affected requests.
2. Why is "pick any two" misleading?
Because partition tolerance is not optional in a networked system. The only real choice is between C and A while a partition is happening; when there is no partition, a system can provide both. A "CA" system is simply a non-distributed one.
3. Is Cassandra CP or AP?
It depends on the consistency levels used. With levels like ONE it behaves as AP (and PA/EL). With QUORUM reads and writes (R + W > N), reads see the latest acknowledged write, but requests fail when a quorum is unreachable, behaving more like CP for those operations.
4. What does PACELC add to CAP?
It says that even without a partition (Else), a replicated system must trade Latency against Consistency, because strong consistency requires waiting for other replicas. So systems are classified twice: PA or PC, and EL or EC.
5. Would you use a CP or AP store for a ticket booking system?
CP for the actual seat reservation, because double-selling a seat is unacceptable; some requests may fail during partitions and users retry. Browsing data such as seat maps and show listings can come from an AP store or cache, with a final consistent check at booking time.
6. Three replicas are split 2–1 by a partition. In a majority-quorum CP system, what happens on each side?
The 2-node side has a majority, so it can elect or keep a leader and keep serving reads and writes. The 1-node side cannot reach a majority, so it rejects writes (and linearizable reads) until the partition heals and it catches up.
Summary
CAP: during a network partition, a distributed system must choose consistency (reject some requests) or availability (risk stale or conflicting data).
Partitions are unavoidable, so "CA" is not an option for a distributed system; "pick any two" is a myth.
CP systems use majorities and consensus; the minority side stops serving. AP systems keep serving and reconcile later.
Many databases are tunable; always state the configuration.
PACELC: else (no partition), choose latency or consistency, because strong consistency costs a network round trip, which physics makes large across regions.
Decide per data type based on what the business can tolerate.
CAP tells you what you must give up when the network breaks. PACELC reminds you that you are already paying for consistency with latency when it does not.