In theoretical computer science, the CAP theorem, also known as Brewer's theorem, states that it is impossible for a distributed computer system to simultaneously provide all three of the following guarantees:
- Consistency (all nodes see the same data at the same time)
- Availability (a guarantee that every request receives a response about whether it was successful or failed)
- Partition tolerance (the system continues to operate despite arbitrary message loss or failure of part of the system)
According to the theorem, a distributed system cannot satisfy all three of these guarantees at the same time. In May 2012 Brewer clarified some of his positions on why the oft-used "two out of three" concept can be misleading or misapplied.
The theorem began as a conjecture made by University of California, Berkeley computer scientist Eric Brewer at the 2000 Symposium on Principles of Distributed Computing (PODC). In 2002, Seth Gilbert and Nancy Lynch of MIT published a formal proof of Brewer's conjecture, rendering it a theorem. This last claim has been criticized however.
The proof of the CAP theorem by Gilbert and Lynch is a bit narrower than that which Brewer had in mind. The theorem sets up a scenario in which a replicated service is presented with two conflicting requests arriving at distinct locations on a time when a link between them is failed. The obligation to provide availability despite partitioning failures leads the services to respond; at least one of these responses shall necessarily be inconsistent with what a service implementing a true one-copy replication semantic would have done. The researchers then go on to show that other forms of consistency are achievable, including a property they call eventual consistency. Thus the theorem doesn't rule out achieving consistency in a distributed system, and says nothing about cloud computing per se or about scalability.
In contrast, Eric Brewer posited that CAP is often taken to preclude consistency for services running in the highly elastic first tier of a modern cloud computing system. These services are typically required to be stateless or to maintain only soft-state (cached data), and must be responsive even if inner-tier services are temporarily inaccessible. CAP, in this sense, uses "A" to mean immediately responsive, and "P" to mean "even if a failure prevents the first-tier service from connecting to some needed resource". In effect, we sacrifice consistency to gain faster responses in a more scalable manner.
CAP is often considered a justification for using weaker consistency models. Popular among these is BASE, an acronym for Basically Available Soft-state services with Eventual-consistency. In summary, the BASE methodology is characterized by high availability for first-tier services, leaving some kind of background cleanup mechanism to resolve any problems created by optimistic actions that later turn out to have violated consistency.[clarification needed]
- Nancy Lynch and Seth Gilbert, “Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services”, ACM SIGACT News, Volume 33 Issue 2 (2002), pg. 51-59.
- "Brewer's CAP Theorem", julianbrowne.com, Retrieved 02-Mar-2010
- "Brewers CAP theorem on distributed systems", royans.net
- CAP Twelve Years Later: How the "Rules" Have Changed
- Eric Brewer, "Towards Robust Distributed Systems"
- Mark Burgess, "Deconstructing the `CAP theorem' for CM and DevOps"
- "A plain english introduction to CAP Theorem" Explains CAP and eventual consistency using examples.
- "CAP equivalent for analytics" Expains the SVLC hypothesis, which concerns CAP-like trade-offs in analytics.
- "Consistency Models in Non-Relational Databases" Explains CAP Theorem and eventual consistency in distributed environments.
- "Problems with CAP, and Yahoo's little known NoSQL system" Discusses PACELC, an alternative to CAP.
- "Returning Transactions to Distributed Data Stores" Discusses the CAP Theorem as it applies to NoSQL systems.