CAP theorem

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

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 (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]


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, this reference does not offer a peer-reviewed formal proof - just an informal assertion on a blog posting.[7]

Brewer’s 2012 article[edit]

CAP Twelve Years Later: How the "Rules" Have Changed

See also[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",, Retrieved 02-Mar-2010
  3. ^ "Brewers CAP theorem on distributed systems",
  4. ^ a b Eric Brewer, “CAP twelve years later: How the "rules" have changed”, Computer, 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]