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.
The proof of the CAP theorem by Gilbert and Lynch is a bit narrower than what 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 t-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.
Notice that partitioning, per se, doesn't really enter into this broader interpretation of CAP. Indeed, there is no CAP theorem for the scenario actually seen where symmetric availability during partitioning failures is not normally required. There are two reasons for this: first, cloud platforms have redundant, highly available networks and normally don't experience such failures. Second, if one of these very rare partitioning events were to occur, it would very likely cut some small set of replicas off not just from other components of the cloud, but also from their external clients, obviating the need for availability.
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.
See also 
- 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"
- "Problems with CAP, and Yahoo's little known NoSQL system" by Daniel Abadi
- "CAP equivalent for analytics"
- "Consistency Models in Non-Relational Databases" by Guy Harrison : A good explanation of CAP Theorem, Eventual consistency and how consistency problems can be handled in distributed environments.
- "A Simple introduction to CAP theorem"
- "Returning Transactions to Distributed Data Stores" Discusses the CAP Theorem as it applies to NoSQL systems.