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]

Guarantees Definition
Consistency Every read receives the most recent write or an error
Availability Every request receives a response, without guarantee that it contains the most recent version of the information
Partition tolerance The system continues to operate despite an arbitrary number of messages being dropped by the network between nodes

In other words, the CAP Theorem states that in the presence of a network partition, one has to choose between consistency and availability. Note that consistency as defined in the CAP Theorem is quite different from the consistency guaranteed in ACID database transactions.

Explanation

No distributed system is safe from network failures, thus network partitioning generally has to be tolerated. In the presence of a partition, one is then left with two options: consistency or availability. When choosing consistency over availability, the system will return an error or a time out if particular information cannot be guaranteed to be up to date due to network partitioning. When choosing availability over consistency, the system will always process the query and try to return the most recent available version of the information, even if it cannot guarantee it is up to date due to network partitioning.[4]

In the absence of network failure -- that is, when the distributed system is running normally -- both availability and consistency can be satisfied.

CAP is frequently misunderstood as if one had to choose to abandon one of the three guarantees at all times. In fact, the choice is really between consistency and availability for when a partition happens only; at all other times, no trade-off has to be made.[5]

Database systems designed with traditional ACID guarantees in mind such as RDBMS choose consistency over availability, whereas systems designed around the BASE philosophy, common in the NoSQL movement for example, choose availability over consistency.[6]

The PACELC theorem builds on CAP by stating that even in the absence of partitioning, another trade-off between latency and consistency occurs.

History

According to University of California, Berkeley computer scientist Eric Brewer, the theorem first appeared in autumn 1998.[6] It was published as the CAP principle in 1999[7] and presented as a conjecture by Brewer at the 2000 Symposium on Principles of Distributed Computing (PODC).[8] 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.[9]

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.[6]

A similar theorem stating the trade-off between consistency and availability in distributed systems was published by Birman and Friedman in 1996.[10] The result of Birman and Friedman restricted this lower bound to non-commuting operations.

See also

References

  1. 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.
  2. ↑ "Brewer's CAP Theorem", julianbrowne.com, Retrieved 02-Mar-2010
  3. ↑ "Brewers CAP theorem on distributed systems", royans.net
  4. ↑ Greiner, Robert. "CAP Theorem: Revisited". robertgreiner.com. Retrieved 2016-09-02.
  5. ↑ "Better explaining the CAP Theorem - DZone Big Data". dzone.com. Retrieved 2016-09-02.
  6. 1 2 3 Eric Brewer, “CAP twelve years later: How the "rules" have changed”, Computer, Volume 45, Issue 2 (2012), pg. 23-29.
  7. ↑ 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.
  8. ↑ Eric Brewer, "Towards Robust Distributed Systems"
  9. ↑ Mark Burgess, "Deconstructing the `CAP theorem' for CM and DevOps"
  10. ↑ Ken Birman and Roy Friedman, "Trading Consistency for Availability in Distributed Systems", April 1996

External links

This article is issued from Wikipedia - version of the 11/19/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.