Catalog My learning Blog
Distributed Systems Explained: CAP, Clocks and Replication · Phase 1 · Lesson 5 · 3 min read

CAP Theorem Explained with Examples

On this page
  1. The CAP theorem, stated carefully
  2. Common CAP theorem misconceptions
  3. CP and AP examples: etcd, PostgreSQL, Cassandra, MongoDB
  4. Choosing consistency or availability
  5. Check yourself

The CAP theorem, stated carefully

Eric Brewer conjectured it in 2000; Seth Gilbert and Nancy Lynch proved it in 2002. With precise definitions:

  • Consistency (C): linearizability. Every read returns the most recent completed write, as if there were one copy of the data (Day 8).
  • Availability (A): every request to a non-failed node gets a (non-error) response.
  • Partition tolerance (P): the system keeps operating even though messages between nodes are lost.

Theorem: when a partition happens, a system can't provide both C and A. A node cut off from the others must either refuse or delay requests (giving up A) or answer from what it has, which may be stale or conflict with the other side (giving up C).

When a partition separates two replicas, each side must either reject requests to stay consistent or keep answering and risk divergence.
When a partition separates two replicas, each side must either reject requests to stay consistent or keep answering and risk divergence.

Common CAP theorem misconceptions

"Pick two of three." Partitions aren't optional in a networked system; links fail, switches fail, cloud zones lose connectivity. You can't choose "CA" for a system spread across machines. The real choice is between C and A during a partition.

"CP systems are unavailable." Only the side of the partition without a quorum stops serving, and only for operations that need consistency. Most of the time there's no partition and CP systems are fully available.

"AP systems are inconsistent." They're eventually consistent: during a partition replicas can diverge, and they converge afterwards through repair and conflict resolution (Days 10 and 13).

"A means high availability." CAP's availability means every non-failed node answers. A CP system with three replicas and automatic failover can be highly available in the everyday sense while still being CP in the theorem's sense.

CP and AP examples: etcd, PostgreSQL, Cassandra, MongoDB

SystemDuring a partitionCategory
etcd, ZooKeeper, Consul (consensus stores)Minority side refuses writes and linearizable readsCP
PostgreSQL/MySQL with a single primaryWrites only where the primary is reachableCP for writes
Cassandra, Riak, Dynamo-style storesAll replicas keep accepting reads and writes; reconcile laterAP (tunable)
MongoDB with majority write concernMinority side can't elect a primary or accept majority writesCP

Many systems let you choose per operation. Cassandra's consistency levels (ONE versus QUORUM), MongoDB's read and write concerns, and DynamoDB's eventually versus strongly consistent reads all move individual operations between the two sides.

Choosing consistency or availability

Ask what a wrong answer costs compared with no answer:

  • A stale like count or recommendation: harmless. Prefer availability.
  • A double-sold seat, a negative bank balance, two users with the same username: costly. Prefer consistency.

Different data in the same application often makes different choices. And remember that CAP only describes behavior during a partition; tomorrow's PACELC covers the trade-off you face the rest of the time.

Check yourself

Partitions happen in any networked system, so it must decide how to behave during one; being "CA" only makes sense on a single node.

The two-node side still has a majority, so it can elect or keep a leader and continue serving reads and writes. The single node can't reach a majority, so it refuses writes and linearizable reads until the partition heals, which is the CP choice.

View counts can favor availability: a slightly wrong count for a minute hurts no one. Account balances or seat reservations should favor consistency, because two sides accepting conflicting writes means overdrafts or double bookings.

Linearizability: every read sees the latest completed write, as if there were one copy. It's a much stronger and narrower idea than the C in ACID.

Rarely. Many databases let you choose per operation or per configuration, such as Cassandra's consistency levels or MongoDB's read and write concerns, so the label describes defaults.