CAP theorem

In database theory, the CAP theorem, also named Brewer's theorem after computer scientist Eric Brewer, states that any distributed data store can provide only two of the following three guarantees:[1][2][3]

Consistency
Every read receives the most recent write or an error. Note that consistency as defined in the CAP theorem is quite different from the consistency guaranteed in ACID database transactions.[4]
Availability
Every request received by a non-failing node in the system must result in a response. This is the definition of availability in CAP theorem as defined by Gilbert and Lynch.[1] Note that availability as defined in CAP theorem is different from high availability in software architecture.[5]
Partition tolerance
The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes.

When a network partition failure happens, it must be decided whether to do one of the following:

  • cancel the operation and thus decrease the availability but ensure consistency
  • proceed with the operation and thus provide availability but risk inconsistency. Note this doesn't necessarily mean that system is highly available to its users. [6]
CAP theorem Euler diagram

Thus, if there is a network partition, one has to choose between consistency or availability.

  1. ^ a b Gilbert, Seth; Lynch, Nancy (2002). "Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services". ACM SIGACT News. 33 (2). Association for Computing Machinery (ACM): 51–59. doi:10.1145/564585.564601. ISSN 0163-5700. S2CID 15892169.
  2. ^ "Brewer's CAP Theorem". julianbrowne.com. 2009-01-11.
  3. ^ "Brewers CAP Theorem on distributed systems". royans.net. 2010-02-14.
  4. ^ Liochon, Nicolas. "The confusing CAP and ACID wording". This long run. Retrieved 1 February 2019.
  5. ^ Fowler, Adam (2015). NoSQL For Dummies. For Dummies. ISBN 978-8126554904.
  6. ^ Fowler, Adam (2015). NoSQL For Dummies. For Dummies. ISBN 978-8126554904.