What is the CAP theorem?

CAP names three properties that people want from a system that keeps copies of data on more than one machine.

• Consistency (C). Every read sees the most recent write, as if there were a single up-to-date copy of the data. Gilbert and Lynch formalise this as atomic, or linearizable, consistency: all operations appear to happen one at a time, in a single order.
• Availability (A). Every request received by a working machine gets a response. The definition puts no limit on how long the response takes, only that it eventually arrives.
• Partition tolerance (P). The system keeps operating when the network between its machines loses messages, including when it splits into groups that cannot reach each other.

Brewer presented the idea in a keynote at the Symposium on Principles of Distributed Computing (PODC) in July 2000. His slide put it simply: you can have at most two of these properties for any shared-data system. In 2002, Gilbert and Lynch turned the conjecture into a theorem with a formal proof.

The proof is short, and the intuition is shorter. Picture two servers holding copies of the same value, and cut the link between them.

A client writes a new value to the first server. A moment later, another client reads from the second server. The second server has not heard about the write, and cannot, because no messages are getting through. It has two options:

1. Answer with the value it has, which may be out of date. That keeps it available and gives up consistency.
2. Refuse to answer, or wait, until it can check with the other server. That keeps it consistent and gives up availability.

There is no third option. Gilbert and Lynch also show a subtler point: when a server cannot tell a lost message from a slow one, it cannot guarantee consistency even in runs where nothing was actually lost.

Brewer’s keynote gave examples of each choice. Systems that forfeit availability during a partition include distributed databases, distributed locking and majority protocols, which make minority partitions unavailable. Systems that forfeit consistency include DNS and web caching, which rely on expirations, conflict resolution and optimistic approaches.

The “two out of three” slogan stuck, but Brewer revisited it in 2012 and called it misleading. His reasons:

• Partitions are rare. When the network works, there is little reason to give up either consistency or availability. CAP only forbids having both perfectly while a partition lasts.
• The choice can be fine-grained. Different parts of a system, different operations, or even different users can make different choices.
• The properties are not on or off. Availability ranges from none to complete, there are many levels of consistency, and parts of a system can disagree about whether a partition exists at all.

Brewer also points out that, in practice, a partition is a time limit. When a request times out, the program must decide whether to cancel it, losing availability, or proceed, risking inconsistency.

Daniel Abadi adds that CAP says nothing about normal operation, where replicated systems face a different trade-off between consistency and latency. He proposes PACELC: if there is a partition (P), choose between availability (A) and consistency (C); else (E), choose between latency (L) and consistency (C). Martin Kleppmann goes further, arguing that inconsistencies and ambiguities in CAP’s definitions cast doubt on its usefulness for reasoning about trade-offs in practical systems.

For an app that works offline, CAP is not abstract. A phone with no connection is on one side of a partition, and the server is on the other. Brewer’s 2012 article names this case directly: disconnected operation, or offline mode, is a long partition. Systems that support it normally choose availability over consistency, and must then recover when the partition ends.

That is the trade an offline-first app makes. It lets people read and write their local copy, accepts that the copy may be stale or may diverge from others, and reconciles later. What happens to a write made offline? follows that path step by step.

Brewer’s advice is to manage partitions explicitly: detect them, enter a partition mode that may limit some operations, and run a recovery process when communication returns. The questions to answer in advance are which operations may proceed during the split, and how to repair any rules they broke.

His examples are practical. Duplicate keys can be allowed during a partition, because they are easy to detect and merge afterwards. An external action such as charging a credit card is better recorded as an intent and carried out after recovery. Data types designed to merge, such as CRDTs, let both sides keep working and converge automatically once they reconnect, though they cannot enforce a rule that spans both sides. How are sync conflicts resolved? covers the merge rules an app can choose.