CAP Theorem Explained: Consistency, Availability, Partition Tolerance

The CAP theorem is one of those computer science concepts that shows up in every distributed systems interview and architecture discussion — but is frequently misunderstood or oversimplified. More importantly, it describes a real trade-off that every engineer who builds on distributed databases must understand to make correct architecture decisions. This guide covers what CAP actually means, why the choice is forced, and how the databases you use every day navigate it.

What the CAP Theorem Actually Says

The CAP theorem, formalized by Eric Brewer in 2000 and proved by Gilbert and Lynch in 2002, states: a distributed data store can provide at most two of the following three guarantees — Consistency, Availability, and Partition Tolerance.

This is often taught as "pick two of three" — which is technically accurate but slightly misleading in practice. Network partitions are not optional. They happen. Therefore, every distributed system must be partition tolerant. The real trade-off is: when a network partition occurs, does the system choose consistency or availability?

The more accurate framing: "In the presence of a network partition, choose either Consistency or Availability."

Consistency: Every Read Gets the Latest Write

CAP consistency means: every read returns the most recent write or an error. After a write succeeds, any read from any node in the system immediately reflects that write. There is no case where you read stale data.

This is a strong guarantee. In a consistent system, if Node A writes "balance = $100" and Node B immediately reads "balance," it gets $100 — even if Node A and Node B are in different data centers. The system ensures this by refusing to serve reads until all nodes agree on the latest value, or by routing all reads to the primary node.

Note: CAP consistency is stricter than database ACID consistency. ACID consistency means data respects schema constraints and invariants. CAP consistency is specifically about whether distributed nodes agree on the latest value at any given moment.

Availability: Every Request Gets a Response

CAP availability means: every request receives a non-error response, though that response may not contain the most recent data.

A highly available system never refuses a read or write request due to a network partition or node failure. Every node that is up can serve requests independently. The trade-off is that during a network partition, different nodes may have different values for the same data — and the system returns whatever it has rather than refusing to answer.

Availability in CAP is different from uptime. A system can have 99.99% uptime but not be CAP-available if it sometimes returns errors or times out during partitions rather than returning potentially stale data.

Partition Tolerance: Surviving Network Failures

Partition tolerance means: the system continues to operate even when messages between nodes are lost or delayed.

A network partition is a communication failure between nodes. Messages between Node A and Node B are dropped, delayed, or corrupted. The two sides of the partition cannot synchronize state. This happens in production: a switch fails, a datacenter loses a network link, a misconfigured firewall starts dropping packets. Partitions are not rare edge cases in distributed systems — they are operational realities.

Because partitions are unavoidable, any distributed system that is worth building must tolerate them. The question is how it behaves during a partition.

Why You Can Only Choose Two

Here is the intuition for why consistency and availability conflict during a partition:

Suppose nodes A and B are partitioned — they cannot communicate. A client writes to Node A: "set x = 10." Node A cannot tell Node B about this write because the network is down. Now another client reads from Node B.

• If the system chooses Consistency: Node B must refuse the read (or return an error) because it knows it might be out of sync with Node A. The system sacrifices availability to maintain the guarantee that reads reflect the latest writes.
• If the system chooses Availability: Node B serves the read — but it might return the old value of x (before the write to Node A). The system stays up but may return stale data.

There is no third option that gives both during a partition. This is the mathematical constraint the theorem proves.

How Real Databases Navigate CAP

CP Systems (Consistency + Partition Tolerance)

HBase, Zookeeper, CockroachDB, Google Spanner, MongoDB (with strong consistency settings). These systems refuse to serve reads or accept writes during a partition if doing so would risk returning or storing inconsistent data. They stay consistent but may be unavailable to some clients during network failures.

AP Systems (Availability + Partition Tolerance)

Cassandra, DynamoDB, CouchDB, Riak. These systems stay up and serve requests during partitions, accepting that different nodes may temporarily have different values for the same data. They use eventual consistency to converge on the correct value once the partition heals.

Single-Node Databases

PostgreSQL, MySQL, and SQLite running on a single node do not face partition tolerance issues — all data is on one machine. In replicated configurations (PostgreSQL streaming replication, MySQL replica), the primary is typically CP: replicas may lag, but the primary always has consistent data, and the replica may refuse writes to maintain consistency.

Eventual Consistency Explained

Eventual consistency is the consistency model most AP systems use: if no new updates are made, eventually all reads will return the last written value.

In an eventually consistent system, after a write to Node A, it takes some time (milliseconds to seconds, depending on replication) for that write to propagate to Node B. During this window, reads from Node B may return the old value. This is called a "stale read." Once propagation is complete, all nodes return the new value.

For many applications, this is acceptable. A shopping cart that takes 100ms to show the latest item count is fine. A social media feed that shows a post a second after it was published is fine. But a bank balance that shows $1000 when the actual balance is $0 (after a withdrawal that has not yet propagated) is not fine. For financial transactions, inventory depletion, and any operation where stale reads could cause harm, eventual consistency is the wrong model.

PACELC: A Better Model for the Real World

The PACELC theorem, proposed by Daniel Abadi in 2012, extends CAP by adding the trade-off that exists even when there is no partition: Latency vs. Consistency.

PACELC: In case of network Partition (P), choose Availability (A) or Consistency (C). Else (E), when the network is healthy, choose Latency (L) or Consistency (C).

This captures a real-world reality: even without a partition, a strongly consistent write must wait for acknowledgment from multiple replicas before returning success. This adds latency. An eventually consistent write returns success as soon as the local node acknowledges, with replication happening asynchronously — lower latency, but the read from another node might not yet reflect the write.

PACELC classifications for common databases:

• Cassandra: PA/EL — Available during partitions, Low latency (eventual consistency) without partitions
• DynamoDB (default): PA/EL — same
• CockroachDB: PC/EC — Consistent during partitions, Consistent without (higher latency writes)
• Google Spanner: PC/EC — Consistent both cases, uses TrueTime for global consistency
• MongoDB: Configurable — can be PA/EL or PC/EC depending on write concern settings

Frequently Asked Questions

What does the CAP theorem say?

A distributed data store can guarantee at most two of: Consistency (every read returns the latest write or an error), Availability (every request gets a non-error response), and Partition Tolerance (the system works despite network failures). Since network partitions are unavoidable, the real choice is: during a partition, sacrifice consistency or availability?

What is eventual consistency?

Eventual consistency guarantees that if no new updates are made, all reads will eventually return the last written value. In the interim, different nodes may return different values. Cassandra, DynamoDB, and CouchDB use eventual consistency by default to prioritize availability — conflicts are resolved when the partition heals.

Is PostgreSQL CP or AP?

PostgreSQL as a single-node database does not face partition issues. In multi-node configurations, PostgreSQL-based systems like CockroachDB are CP — they prioritize consistency over availability during partitions. Streaming replication replicas may become read-only during a primary failure, sacrificing write availability to maintain consistency.

What is the PACELC theorem?

PACELC extends CAP: during a Partition, choose Availability or Consistency. Else (no partition), choose Latency or Consistency. PACELC better captures the real trade-off: even with a healthy network, strongly consistent writes add latency (waiting for all replica acknowledgments), while eventually consistent writes are faster but may be stale on reads.

Note: The CAP theorem applies specifically to distributed data stores. Database vendor claims about CAP classification should be evaluated against actual default configuration behavior, not best-case settings.