The CAP theorem

CAP stands for consistency, availability and partition tolerance. Brewer's keynote at the 2000 Principles of Distributed Computing conference (PODC) set consistency against availability under network partitions, with slides for forfeiting each of the three and a contrast between ACID databases (atomic, consistent, isolated, durable) and what he called BASE, basically available, soft state, eventually consistent. Gilbert and Lynch made it a theorem in 2002: with consistency defined as atomic (linearisable) reads and writes, availability as every request to a working node getting a response, and partitions as arbitrary message loss, no system in the asynchronous model can give all three. The useful reading is not 'pick two'. Partitions are not chosen, they happen, so the real choice is what each operation does while one is in progress.

Brewer said as much in 2012: the 'two of three' framing was always misleading. Partitions are rare, and when there is none a system can be both consistent and available. During a partition the choice can be made per operation, per data item, even per user, rather than once for the whole system. He proposes three steps: detect the partition, enter a partition mode that limits which operations proceed, and on recovery restore consistency and compensate for the mistakes made meanwhile. His example is a cash machine that allows withdrawals up to a limit while cut off from the bank, then reconciles. GitHub's 2018 incident shows the choice being made twice: availability by the failover tool during a 43-second partition, then consistency by the engineers for the next 24 hours.

Martin Kleppmann's 2015 critique argues that the formal theorem is narrow and its words are slippery. CAP's consistency means linearisability only, and CAP's availability is not the availability in a service agreement, so many real systems are neither C nor A in CAP's sense and the theorem says nothing about them. It is often read as proof that eventually consistent databases are more available than strongly consistent ones, which he shows needs more careful reasoning. He proposes thinking in terms of delay sensitivity instead: how each operation's latency responds to network delay. Gilbert and Lynch's own 2012 retrospective places CAP inside the older trade-off between safety and liveness. Use it as a reminder to design for partitions, not as a taxonomy of databases.