CAP theorem

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 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.

History

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.

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

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.

• 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”, 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"