CAP Theorem & PACELC

The theorem#

Formulated by Eric Brewer in 2000, the CAP theorem states that a distributed data system can only guarantee two out of three of the following at the same time, in the presence of a network partition:

• Consistency (C) — every read receives the most recent write, or an error. All nodes see the same data at the same time.
• Availability (A) — every request receives a (non-error) response, without guaranteeing it's the most recent write.
• Partition tolerance (P) — the system continues operating despite arbitrary network partitions (dropped or delayed messages between nodes).

Why "pick two" is actually "pick one"#

In any real distributed system spanning more than one machine, network partitions will happen — cables get cut, switches fail, regions lose connectivity. So partition tolerance (P) isn't really optional; it's a fact of distributed life. That leaves a genuine choice only between:

• CP (Consistency + Partition tolerance) — during a partition, the system refuses some requests (returns an error or times out) rather than risk returning stale/inconsistent data. Example: many configurations of MongoDB, HBase, and ZooKeeper.
• AP (Availability + Partition tolerance) — during a partition, the system keeps responding to every request, but different nodes might briefly disagree on the data ("eventual consistency"). Example: Cassandra, DynamoDB, most DNS systems.

There is no "CA" option in a truly distributed system — a single-node database is trivially CA, but that's not a distributed system at all.

A concrete example#

Imagine a distributed key-value store with 3 nodes, and a network partition splits node C off from nodes A and B.

Client writes X=5 to node A.
Network partition: node C can't hear from A or B.
Client reads X from node C.

CP system:  node C returns an error ("can't guarantee freshness right now")
AP system:  node C returns its last known value (maybe X=3, stale) — but responds

Neither answer is "wrong" — they represent different priorities. A banking ledger probably wants CP (never show a wrong balance). A social media "like" counter can tolerate AP (briefly stale is fine, availability matters more).

PACELC — CAP's more complete successor#

CAP only describes behaviour during a partition. Daniel Abadi's PACELC extends it to describe the normal, no-partition case too:

If Partitioned: choose between Availability and Consistency Else (normal operation): choose between Latency and Consistency

This matters because even when there's no partition, a strongly consistent system usually pays a latency cost (e.g., waiting for a quorum of replicas to acknowledge a write) that an eventually-consistent system doesn't.

Practical takeaway#

When designing (or discussing in an interview) any system with replicated or partitioned data, explicitly state:

1. What happens to reads/writes during a network partition?
2. What consistency guarantee do you actually need for this specific data? (A bank balance and a "view count" have very different requirements.)
3. What latency are you willing to trade for stronger consistency during normal operation?

Common mistakes#

• Treating CAP as "pick any 2 of 3" as if it were a menu — in practice, P is mandatory for any real distributed system, so the actual choice is CP vs AP.
• Applying the same consistency requirement to every piece of data in a system — most real systems mix strongly-consistent data (payments, inventory counts) with eventually-consistent data (view counts, recommendation caches).
• Forgetting PACELC — CAP alone says nothing about the far more common "no partition happening right now" case.

Interview questions#

Q: Why can't a real distributed system just be "CA"? Because network partitions are a physical inevitability once you have more than one node communicating over a network — a system that assumes partitions never happen isn't really accounting for distributed reality, and will simply behave unpredictably (not "CA") when one occurs.

Q: Give an example of a system that should favor CP, and one that should favor AP. A payments/ledger system should favor CP — an incorrect balance is worse than a temporary error. A social media "likes" counter or a DNS lookup should favor AP — briefly stale data is an acceptable trade for staying available.

Q: What does PACELC add that CAP doesn't cover? It explicitly addresses the consistency/latency trade-off during normal operation (no partition), which is a system's actual state the vast majority of the time — CAP only speaks to behaviour during a partition.