||This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: no explanation of CAP theorem and its importance (December 2015) (Learn how and when to remove this template message)|
||This article's introduction may be too long for the length of the article. (December 2015)|
In theoretical computer science, the CAP theorem, also named Brewer's theorem after computer scientist Eric Brewer, 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 (every request receives a response about whether it succeeded or failed)
- Partition tolerance (the system continues to operate despite arbitrary partitioning due to network failures)
In 2012 Brewer clarified some of his positions, including why the often-used "two out of three" concept can be misleading or misapplied, and the different definition of consistency used in CAP relative to the one used in ACID.
According to University of California, Berkeley computer scientist Eric Brewer, the theorem first appeared in autumn 1998. It was published as the CAP principle in 1999 and presented as a conjecture by 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, this reference does not offer a peer-reviewed formal proof - just an informal assertion on a blog posting.
Brewer’s 2012 article
- Consistency model
- Fallacies of Distributed Computing
- Paxos (computer science)
- Project management triangle
- Raft (computer science)
- Seth Gilbert and Nancy Lynch, “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
- Eric Brewer, “CAP twelve years later: How the "rules" have changed”, Computer, Volume 45, Issue 2 (2012), pg. 23-29.
- Armando Fox and Eric Brewer, “Harvest, Yield and Scalable Tolerant Systems”, Proc. 7th Workshop Hot Topics in Operating Systems (HotOS 99), IEEE CS, 1999, pg. 174-178.
- Eric Brewer, "Towards Robust Distributed Systems"
- Mark Burgess, "Deconstructing the `CAP theorem' for CM and DevOps"
- "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.
- "You can't sacrifice partition tolerance, by Codahale" Discusses practical implications of CAP Theorem in real world systems.
- "Trading Consistency for Availability in Distributed Systems", by Birman and Friedman. Formally states and proves a similar theorem to CAP, from April 1996.