CAP theorem

AP systemavailability under partitionCAPnetwork partitions
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 data store to simultaneously provide more than two out of the following three guarantees:wikipedia
40 Related Articles

Eric Brewer (scientist)

Eric Brewer
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 data store to simultaneously provide more than two out of the following three guarantees: According to University of California, Berkeley computer scientist Eric Brewer, the theorem first appeared in autumn 1998.
He is known for formulating the CAP theorem about distributed network applications in the late 1990s.

Distributed data store

distributed data storagedata storedatabases
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 data store to simultaneously provide more than two out of the following three guarantees:
But the high-speed read/write access results in reduced consistency, as it is not possible to have both consistency, availability, and partition tolerance of the network, as it has been proven by the CAP theorem.

NoSQL

structured storagekey/value storenon-relational
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.
Many NoSQL stores compromise consistency (in the sense of the CAP theorem) in favor of availability, partition tolerance, and speed.

PACELC theorem

The PACELC theorem builds on CAP by stating that even in the absence of partitioning, another trade-off between latency and consistency occurs.
In theoretical computer science, the PACELC theorem is an extension to the CAP theorem.

Network partition

partition tolerancenetwork partitioningNetwork Partition for Optimization
Partition tolerance: The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes
The CAP Theorem is based on three trade-offs: Consistency, Availability, and Partition tolerance.

ACID (computer science)

ACIDACID transactionsAtomicity, consistency, isolation, durability
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. Note that consistency as defined in the CAP theorem is quite different from the consistency guaranteed in ACID database transactions.
CAP theorem

Consistency (database systems)

Consistencyinconsistentconsistent
Consistency: Every read receives the most recent write or an error
The CAP theorem is based on three trade-offs, one of which is "atomic consistency" (shortened to "consistency" for the acronym), about which the authors note, "Discussing atomic consistency is somewhat different than talking about an ACID database, as database consistency refers to transactions, while atomic consistency refers only to a property of a single request/response operation sequence. And it has a different meaning than the Atomic in ACID, as it subsumes the database notions of both Atomic and Consistent."

Eventual consistency

eventually consistentBASEeventually
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.
CAP theorem

Fallacies of distributed computing

The Eight Fallacies of Distributed Computing
Fallacies of distributed computing
CAP theorem

Trilemma

Trilemma russiense
Trilemma
The CAP theorem, covering guarantees provided by distributed systems, and Zooko's triangle concerning naming of participants in network protocols.

Theoretical computer science

theoretical computer scientisttheoreticalcomputer science
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 data store to simultaneously provide more than two out of the following three guarantees:

Database transaction

transactiontransactionstransactional
Note that consistency as defined in the CAP theorem is quite different from the consistency guaranteed in ACID database transactions.

Availability

mission capable rateavailablemission capable
Availability: Every request receives a (non-error) response – without the guarantee that it contains the most recent write

Relational database management system

RDBMSrelational database management systemsrelational database
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.

University of California, Berkeley

BerkeleyUC BerkeleyUniversity of California
According to University of California, Berkeley computer scientist Eric Brewer, the theorem first appeared in autumn 1998.

Conjecture

conjecturalconjecturesconjectured
It was published as the CAP principle in 1999 and presented as a conjecture by Brewer at the 2000 Symposium on Principles of Distributed Computing (PODC).

Symposium on Principles of Distributed Computing

PODC
It was published as the CAP principle in 1999 and presented as a conjecture by Brewer at the 2000 Symposium on Principles of Distributed Computing (PODC).

Nancy Lynch

LynchNancy A. Lynch
In 2002, Seth Gilbert and Nancy Lynch of MIT published a formal proof of Brewer's conjecture, rendering it a theorem.

Massachusetts Institute of Technology

MITMassachusetts Institute of Technology (MIT)M.I.T.
In 2002, Seth Gilbert and Nancy Lynch of MIT published a formal proof of Brewer's conjecture, rendering it a theorem.

Theorem

theoremspropositionconverse
In 2002, Seth Gilbert and Nancy Lynch of MIT published a formal proof of Brewer's conjecture, rendering it a theorem.

Project management triangle

bottom up estimateson trackproject triangle
Project management triangle

Riak

Riak implements the principles from Amazon's Dynamo paper with heavy influence from the CAP Theorem.