CAP theoremFrom Wikipedia, the free encyclopedia

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]

Consistency (all nodes see the same data at the same time)

Availability (node failures do not prevent survivors from continuing to operate)

Partition tolerance (the system continues to operate despite arbitrary message loss)

According to the theorem, a distributed system can satisfy any two of these guarantees at the same time, but not all three.[3]

History

The theorem began as a conjecture made by University of California, Berkeley computer scientist Eric Brewer at the 2000 Symposium on Principles of Distributed Computing (PODC).[4] In 2002, Seth Gilbert and Nancy Lynch of MIT published a formal proof of Brewer's conjecture, establishing it as a theorem.[1]

References

[1] a b Nancy Lynch and Seth Gilbert, “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] Eric Brewer, "Towards Robust Distributed Systems"

External links

"Problems with CAP, and Yahoo's little known NoSQL system" by Daniel Abadi

"CAP equivalent for analytics"

P ≟ NP This theoretical computer science-related article is a stub. You can help Wikipedia by expanding it.