CAP theorem
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:[1][2][3]
- Consistency (all nodes see the same data at the same time)
- Availability (a guarantee that 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.[4]
History
According to University of California, Berkeley computer scientist Eric Brewer, the theorem first appeared in autumn 1998.[4] It was published as the CAP principle in 1999[5] and presented as a conjecture by Brewer at the 2000 Symposium on Principles of Distributed Computing (PODC).[6] In 2002, Seth Gilbert and Nancy Lynch of MIT published a formal proof of Brewer's conjecture, rendering it a theorem.[1] This last claim has been criticized, however.[7]
Brewer’s 2012 article
CAP Twelve Years Later: How the "Rules" Have Changed
See also
- Consistency model
- Fallacies of Distributed Computing
- Paxos (computer science)
- Project management triangle
- Raft (computer science)
- Trilemma
References
- 1 2 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
- 1 2 Eric Brewer, “CAP twelve years later: How the "rules" have changed”, IEEE Explore, 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"
External links
- "A plain english introduction to CAP Theorem" Explains CAP and eventual consistency using examples.
- "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.