CAP Theorem

Consistency, Availability, Partition Tolerance

The CAP theorem, proved by Eric Brewer and formally by Gilbert and Lynch, states that a distributed system can guarantee at most two of three properties. Understanding what each property actually means is the prerequisite to understanding the theorem itself.

Consistency

Every read receives the most recent write, or an error. All nodes see the same data at the same time. A client can never read stale data.

This is linearizability, not ACID consistency. It means operations appear instantaneous and in a globally agreed order.

Example: You write x=2 to Node A. Any subsequent read from any node returns x=2.

Availability

Every request receives a response. Not necessarily the most recent data, but a response without error or timeout. The system never goes silent.

Availability in CAP is a strong guarantee: every non-failing node must respond to every request.

Example: Node B is isolated from Node A. A read from Node B still returns something (possibly stale).

Partition Tolerance

The system continues operating even when some nodes cannot communicate with others. Network splits, dropped packets, and node failures are all partition events.

In any distributed system running over a real network, partitions happen. Hardware fails. Cables are cut. Cloud availability zones lose connectivity.

Example: Node A and Node B cannot reach each other, but both keep running and responding.

Why you cannot have all three

The impossibility argument is straightforward. Consider two nodes, A and B, with a network link. You write x=2 to A. The link breaks before A can replicate to B. Now a client reads x from B.

The partition scenario

1Client writes x=2 to Node A. Acknowledged.

2Network link between A and B breaks (partition).

3Client reads x from Node B.

4aOption A: Node B returns x=1 (stale). Fast but wrong.

4bOption B: Node B returns an error or waits. Correct but unavailable.

Node B cannot return x=2 without contacting A, which is unreachable. There is no third option. This is why C and A are mutually exclusive during a partition.

Partition tolerance is not a choice. In any system running over a real network, partitions happen. If you choose to drop P, your system must halt completely during any partition. No real production system can afford that. The actual choice is always: during a partition, sacrifice C or sacrifice A?

Simulating a Network Partition

The simulator below shows two database nodes with a shared variable x. Use it to explore how CP and AP systems behave differently when the network link is severed.

Start by writing a few values with the network connected. Then partition the network and try writing again. Switch between CP and AP modes to see the different responses. Finally, heal the network to watch AP reconciliation happen.

Network Partition SimulatorConnected

Node A

x = 1

linked

Node B

x = 1

Try writing a value, then partition the network...

CPConsistency over Availability

Writes are rejected during a partition. Every read returns the latest confirmed value. No client ever sees stale data. The cost: your service is partially unavailable while the partition lasts.

Real systems: Zookeeper, etcd, HBase, Redis (Sentinel mode), MongoDB (primary-only reads)

APAvailability over Consistency

Writes succeed on any reachable node. The system always responds. The cost: nodes diverge during a partition, and stale data is served to clients until the network heals and reconciliation runs.

Real systems: Cassandra, CouchDB, DynamoDB (eventual), Riak, DNS

Reconciliation in AP systems

When the partition heals, AP systems must reconcile diverged state. Different systems use different strategies to resolve conflicts between nodes that both accepted writes.

Last-write-wins (LWW)

Each write is timestamped. The write with the highest timestamp wins. Simple but requires synchronized clocks. Clock skew can cause newer writes to be discarded.

Used by: Cassandra (default), DynamoDB

Vector clocks

Each write carries a vector of version numbers, one per node. Conflicts are detected by comparing vectors. The application or user resolves genuine conflicts.

Used by: Riak, Amazon Dynamo (original)

CRDTs (Conflict-free Replicated Data Types)

Data structures designed so concurrent updates always merge without conflict. A counter that only increments, a set that only adds: these can merge automatically.

Used by: Riak (counters, sets), Redis (some structures)

Multi-version concurrency control (MVCC)

Every write creates a new version. Diverged branches are preserved as multiple versions. The application can see the conflict and resolve it explicitly.

Used by: CouchDB, PostgreSQL (for ACID isolation)

CP vs AP: Real Systems and Consistency Models

Consistency is not binary. Between "all nodes agree on everything instantly" and "nodes may disagree indefinitely" lies a spectrum of models, each offering different trade-offs between correctness and performance.

The consistency spectrum

LinearizableStrong consistencyHighest latency

Operations appear instantaneous and globally ordered. Any read after a write returns that write's value, from any node.

Examples: etcd, Zookeeper, Spanner, CockroachDB

Sequential consistencyHigh latency

Operations appear in the same order on all nodes, but the order may lag real time. Writes are globally ordered, just not necessarily in wall-clock order.

Examples: Some Redis configurations

Causal consistencyMedium latency

Causally related operations are seen in order. If you write A and then B in response to A, any node that sees B will also have seen A. Unrelated operations may be reordered.

Examples: MongoDB (causal sessions), COPS

Eventual consistencyBASELowest latency

Given no new writes, all nodes will eventually converge to the same value. No ordering guarantee. Reads may return stale data during the convergence window.

Examples: Cassandra, DynamoDB, CouchDB, DNS

Where real systems sit

System	CAP	Behavior during partition
Zookeeper	CP	Raft consensus. Rejects reads/writes during leader election (30-60s). Used for coordination, not storage.
etcd	CP	Raft consensus. Guarantees linearizable reads. Unavailable when quorum is lost.
HBase	CP	HDFS-backed. Strong consistency via HDFS semantics. Unavailable when HMaster is down.
MongoDB	CP	Primary-only writes by default. Read concern majority gives linearizable reads. No primary = no writes.
Redis Sentinel	CP	Primary fails: 10-30s election. During election: no writes. Read replicas may lag.
Cassandra	AP	Tunable consistency (ONE to ALL). Default is eventual. Always writable, always readable.
CouchDB	AP	MVCC-based. Multi-master replication. Conflict resolution is explicit.
DynamoDB	AP	Eventually consistent by default. Strongly consistent reads available at 2x the read cost.
Riak	AP	Vector clocks, last-write-wins, or CRDT conflict resolution. Designed for availability.
DNS	AP	Returns cached responses even when authoritative servers are unreachable. TTL governs staleness.

Most modern databases offer tunable consistency. Cassandra lets you set consistency per operation (ONE, QUORUM, ALL). DynamoDB lets you request strongly consistent reads. MongoDB lets you set read concern and write concern per query. In practice, you mix consistency levels within a single application: strong consistency for payments, eventual consistency for analytics.

Beyond CAP: PACELC and Practical Guidance

CAP is often misapplied because it only applies during network partitions, which are relatively rare events. Most of the time, your distributed system is operating normally with all nodes connected. During normal operation, there is a different fundamental trade-off: consistency versus latency.

The PACELC model

PACELC extends CAP to cover both cases. During a Partition (P), you choose Availability (A) or Consistency (C). Else (E), during normal operation, you choose Latency (L) or Consistency (C).

PACELC framework

During a Partition (P)

Same as CAP: choose between Availability (A) or Consistency (C). Most systems must sacrifice one when nodes cannot communicate.

PA: serve stalePC: reject writes

Else: during Normal Operation (E)

Even without partitions, replicating writes to multiple nodes takes time. Choose: respond fast with possibly stale data, or wait for confirmation.

EL: fast, may lagEC: slow, always fresh

System	PACELC	Trade-off in plain terms
DynamoDB	PA/EL	Chooses availability during partitions. Normally favors low latency over strong consistency.
Cassandra	PA/EL	Always available. Tunable consistency but defaults to low latency.
Spanner	PC/EC	Chooses consistency during partitions. TrueTime protocol achieves external consistency globally.
CockroachDB	PC/EC	Serializable transactions with global consistency. Latency trades for correctness.
MongoDB (majority)	PC/EC	With majority read/write concern, strongly consistent. Latency cost on each write.
Riak	PA/EL	Designed for availability. Multi-master replication. Eventual consistency by design.

Practical guidance

✓

Use strong consistency for writes that matter

Financial transactions, inventory updates, authentication state. The cost is latency, not correctness. Pay it where it counts.

✓

Use eventual consistency for reads that tolerate lag

Analytics dashboards, activity feeds, recommendation counters. A like count that is 2 seconds stale is not a problem.

✓

Do not treat CAP as the only model

PACELC reminds you the latency-consistency trade-off exists at all times, not just during the rare partition event. Most performance problems are PACELC problems.

✓

Tune consistency per operation, not per system

Cassandra, DynamoDB, and MongoDB all support per-request consistency levels. Use QUORUM for writes, ONE for non-critical reads. Mix within the same application.