CAP theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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:[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 oft-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[edit]

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[edit]

See also[edit]

References[edit]

  1. ^ a b 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.
  2. ^ "Brewer's CAP Theorem", julianbrowne.com, Retrieved 02-Mar-2010
  3. ^ "Brewers CAP theorem on distributed systems", royans.net
  4. ^ a b Eric Brewer, “CAP twelve years later: How the "rules" have changed”, IEEE Explore, Volume 45, Issue 2 (2012), pg. 23-29.
  5. ^ 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.
  6. ^ Eric Brewer, "Towards Robust Distributed Systems"
  7. ^ Mark Burgess, "Deconstructing the `CAP theorem' for CM and DevOps"

External links[edit]