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. Availability is formal too. In Gilbert and Lynch’s definition, every request received by a non-failing node must result in a response, so the algorithm must eventually terminate even when the network is partitioned. The definition puts no bound on how long that takes, which is why it is a property of what happens to each request during a partition and not an uptime percentage or an SLA target. 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.

References

• Eric Brewer, CAP Twelve Years Later: How the Rules Have Changed (2012)
• Seth Gilbert and Nancy Lynch, Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services (2002)
• Daniel J. Abadi, Consistency Tradeoffs in Modern Distributed Database System Design (2012)