CAP Theorem

The CAP Theorem, proposed by Eric Brewer in 2000 and formally proven by Seth Gilbert and Nancy Lynch in 2002, states that it is impossible for a distributed data store to simultaneously provide more than two out of the following three guarantees:

1. The Three Guarantees

Consistency (C)

Every read receives the most recent write or an error. All nodes in the distributed system see the exact same data at the same time.

• If you update your profile picture on Server A, and someone reads your profile from Server B a millisecond later, they MUST see the new picture. If they see the old picture, the system is inconsistent.

Availability (A)

Every request receives a (non-error) response, without the guarantee that it contains the most recent write.

• Every request to the system will return a response, even if the data might be slightly stale. The system never refuses to respond.

Partition Tolerance (P)

The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes.

• In a real-world distributed system, network cables get cut, routers crash, and data centers lose connectivity. A partition-tolerant system keeps working even when some servers cannot communicate with each other.

2. Why Can You Only Pick Two?

In a real-world distributed system, network partitions will happen. Cables get cut by construction workers, switches fail, and data centers lose connectivity. Therefore, Partition Tolerance (P) is not optional—it is a requirement. You must choose P.

This forces you to choose between Consistency and Availability:

CP Systems (Consistency + Partition Tolerance)

When a network partition occurs, the system will refuse to respond (sacrificing Availability) rather than risk returning stale data (maintaining Consistency).

• Examples: MongoDB (in certain configurations), HBase, Redis.
• Use Case: Banking systems. It is better for a bank to temporarily refuse a transaction than to process it with incorrect balance data.

AP Systems (Availability + Partition Tolerance)

When a network partition occurs, the system will return whatever data it has (sacrificing Consistency) rather than going offline (maintaining Availability).

• Examples: Cassandra, DynamoDB, CouchDB.
• Use Case: Social media "Likes" count. It's acceptable if the like count is temporarily off by a few for some users, as long as the system never goes down.

3. PACELC Extension

The CAP theorem only describes behavior during network partitions. In 2012, Daniel Abadi proposed the PACELC theorem, which extends CAP:

If there is a Partition, how does the system trade off Availability and Consistency? Else (when the system is running normally, without partitions), how does the system trade off Latency and Consistency?

This is important because even when the network is perfectly healthy, the system must decide: Should a write operation wait for all replicas to confirm (high consistency, high latency)? Or should it return immediately after one replica confirms (low latency, risk of inconsistency)?