CAP Theorem Reading List

A short, opinionated path through the CAP literature, with citations rendered from the site’s bibliography.bib. Read in this order; each paper corrects a misunderstanding the previous one tends to leave behind.

The one-line version

CAP is not a menu of three where you pick two. Partitions happen whether you like it or not; the theorem is about what your system does while one is happening.

1. The conjecture

Brewer presented the idea as a keynote, not a proof, and framed it in terms of the trade-offs web services were already making in practice (Brewer, 2000). The original slides are informal; what later became “the CAP theorem” was a slogan first.

2. The proof, and the narrowing

Gilbert and Lynch turned the conjecture into a theorem by pinning down what “consistent” and “available” mean, and that is where the formal result becomes narrow: linearizable consistency plus every request receiving a response, in an asynchronous network (Gilbert & Lynch, 2002). Most production systems do not aim for either definition in full.

3. Twelve years later

Brewer revisited the theorem to push back on the “two out of three” reading. Partitions are rare, and systems can be consistent and available almost all of the time; the design question is detection, a sensible degraded mode, and recovery (E. Brewer, 2012).

4. The trade-off that applies even without partitions

Abadi’s PACELC adds the missing axis: when the network is fine, replicated systems still trade latency against consistency. Many “AP” databases are really “EL” ones that chose low latency (Abadi, 2012).

5. What you can keep under partition

Bailis and colleagues catalogue which transactional guarantees survive high availability and which cannot, a useful map for anyone choosing isolation levels in a distributed database (Bailis et al., 2013).

6. Why the vocabulary fails

Kleppmann’s critique argues that CAP’s definitions are too blunt for real engineering discussions and proposes talking about delay-sensitivity instead. If you read only one of these, read this one (Kleppmann, 2015).

7. How CP systems get consistency in practice

Raft is the consensus algorithm most of the CP databases on this site rely on. It was designed explicitly to be understandable, and the paper delivers on that (Ongaro & Ousterhout, 2014).

Where this connects on the site

• System Design/partition_tolerance_in_distributed_systems cites the same sources inline.
• System Design/cp_systems_design and System Design/ap_systems_design show the two choices under partition.

Abadi, D. (2012). Consistency Tradeoffs in Modern Distributed Database System Design: CAP Is Only Part of the Story. Computer, 45(2), 37–42.

Bailis, P., Davidson, A., Fekete, A., Ghodsi, A., Hellerstein, J. M., & Stoica, I. (2013). Highly Available Transactions: Virtues and Limitations. Proceedings of the VLDB Endowment, 7(3), 181–192.

Brewer, E. (2012). CAP Twelve Years Later: How the “Rules” Have Changed. Computer, 45(2), 23–29.

Brewer, E. A. (2000). Towards Robust Distributed Systems. Proceedings of the 19th Annual ACM Symposium on Principles of Distributed Computing (PODC).

Gilbert, S., & Lynch, N. (2002). Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services. ACM SIGACT News, 33(2), 51–59.

Kleppmann, M. (2015). A Critique of the CAP Theorem. arXiv Preprint arXiv:1509.05393.

Ongaro, D., & Ousterhout, J. (2014). In Search of an Understandable Consensus Algorithm. Proceedings of the 2014 USENIX Annual Technical Conference, 305–319.