CAP Theorem

The CAP theorem states that a distributed data system cannot simultaneously provide perfect consistency and perfect availability when the network is partitioned. It is the most cited result in this area, and the most misapplied.

The misapplication comes from the popular “pick two of three” summary, which Eric Brewer — who stated the conjecture — described as misleading in a 2012 retrospective, on the grounds that it oversimplifies the tensions between the properties. The theorem does not offer a menu. It rules out one specific combination in one specific circumstance.

Two clarifications make it usable. The consistency in question is strong: the formal proof by Gilbert and Lynch used atomic, or linearizable, consistency — as Daniel Abadi’s later paper restates — not “the data is eventually right.” And partitions are not a design option you can decline. A system that runs on a network will experience them, so “choosing CA” is not a choice, merely an unstated assumption.

Brewer’s more practical reframing is the part worth carrying into a design review. A partition is, pragmatically, a time bound on communication: the essence of CAP arrives at a timeout, when a program must make what he calls the partition decision — cancel the operation and reduce availability, or proceed and risk inconsistency.

Read that way, CAP is a tool for one moment rather than a taxonomy of databases. The useful questions become: what does this system do at that timeout, is the answer the same for every operation, and who decided?

What CAP omits — the trade-off that applies when there is no partition at all — is the subject of PACELC, and both are worked through in Replication, Consistency, and Time.