:CAP theorem

No distributed system is safe from network failures, thus network partitioning generally has to be tolerated.{{cite report|last1=Kleppmann |first1=Martin |title=A Critique of the CAP Theorem |date=2015-09-18 |publisher=Apollo - University of Cambridge Repository |doi=10.17863/CAM.13083 |url=https://www.repository.cam.ac.uk/handle/1810/267054 |access-date=24 November 2019|bibcode=2015arXiv150905393K |arxiv=1509.05393 |s2cid=1991487 }}{{cite web |last1=Martin |first1=Kleppmann |title=Please stop calling databases CP or AP |url=https://martin.kleppmann.com/2015/05/11/please-stop-calling-databases-cp-or-ap.html |website=Martin Kleppmann's Blog |access-date=24 November 2019}} 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.

In the absence of a network partition, both availability and consistency can be satisfied.{{Cite web|url=http://dbmsmusings.blogspot.com/2010/04/problems-with-cap-and-yahoos-little.html|title=DBMS Musings: Problems with CAP, and Yahoo's little known NoSQL system|last=Abadi|first=Daniel|date=2010-04-23|website=DBMS Musings|access-date=2018-01-23}}

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.

Some cloud services choose strong consistency but use worldwide private fiber networks and GPS clock synchronization to minimize the frequency of network partitions{{citation needed|date=November 2024}}. Finally, consistent shared-nothing architectures may use techniques such as geographic sharding to maintain availability of data owned by the queried node, but without being available for arbitrary requests during a network partition{{citation needed|date=November 2024}}.

According to computer scientist Eric Brewer of the University of California, Berkeley, the theorem first appeared in autumn 1998.{{cite journal | last=Brewer | first=Eric | title=CAP twelve years later: How the "rules" have changed | journal=Computer | publisher=Institute of Electrical and Electronics Engineers (IEEE) | volume=45 | issue=2 | year=2012 | issn=0018-9162 | doi=10.1109/mc.2012.37 | pages=23–29 | s2cid=890105 |url=http://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed}} It was published as the CAP principle in 1999{{cite conference |author1=Armando Fox |author2=Eric Brewer |title=Harvest, Yield and Scalable Tolerant Systems |conference=Proc. 7th Workshop Hot Topics in Operating Systems (HotOS 99) |publisher=IEEE CS |year=1999 |pages=174–178 |doi=10.1109/HOTOS.1999.798396}} and presented as a conjecture by Brewer at the 2000 Symposium on Principles of Distributed Computing (PODC).{{cite web |author=Eric Brewer |url=http://www.cs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf |title=Towards Robust Distributed Systems}} In 2002, Seth Gilbert and Nancy Lynch of MIT published a formal proof of Brewer's conjecture, rendering it a theorem.

In 2012, Brewer clarified some of his positions, including why the often-used "two out of three" concept can be somewhat misleading because system designers only need to sacrifice consistency or availability in the presence of partitions; partition management and recovery techniques exist. Brewer also noted the different definition of consistency used in the CAP theorem relative to the definition used in ACID.{{Cite book |last1=Carpenter |first1=Jeff |url=https://www.oreilly.com/library/view/cassandra-the-definitive/9781491933657/ |title=Cassandra: The Definitive Guide |last2=Hewitt |first2=Eben |date=July 2016 |publisher=O'Reilly Media |isbn=9781491933657 |edition=2nd |quote=In February 2012, Eric Brewer provided an updated perspective on his CAP theorem{{nbsp}}... Brewer now describes the “2 out of 3” axiom as somewhat misleading. He notes that designers only need sacrifice consistency or availability in the presence of partitions, and that advances in partition recovery techniques have made it possible for designers to achieve high levels of both consistency and availability.}}

A similar theorem stating the trade-off between consistency and availability in distributed systems was published by Birman and Friedman in 1996.{{cite web |author1=Ken Birman |author2=Roy Friedman |url=https://ecommons.cornell.edu/handle/1813/7235 |title=Trading Consistency for Availability in Distributed Systems |date=April 1996 |hdl=1813/7235}} Birman and Friedman's result restricted this lower bound to non-commuting operations.

The PACELC theorem, introduced in 2010, builds on CAP by stating that even in the absence of partitioning, there is another trade-off between latency and consistency. PACELC means, if partition (P) happens, the trade-off is between availability (A) and consistency (C); Else (E), the trade-off is between latency (L) and consistency (C). Some experts like Marc Brooker argue that the CAP theorem is particularly relevant in intermittently connected environments, such as those related to the Internet of Things (IoT) and mobile applications. In these contexts, devices may become partitioned due to challenging physical conditions, such as power outages or when entering confined spaces like elevators. For distributed systems, such as cloud applications, it is more appropriate to use the PACELC theorem, which is more comprehensive and considers trade-offs such as latency and consistency even in the absence of network partitions.{{Cite book |title=Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems |publisher=O'Reilly Media |isbn=978-1449373320}}

• Fallacies of distributed computing
• Lambda architecture (solution)
• PACELC theorem
• Paxos (computer science)
• Raft (computer science)
• Zooko's triangle
• Inconsistent triad
• Trilemma

{{reflist}}

{{Databases}}

{{DEFAULTSORT:Cap Theorem}}

Category:Distributed computing

Category:Database management systems