CAP theorem
Encyclopedia
In theoretical computer science
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:
According to the theorem, a distributed system can satisfy any two of these guarantees at the same time, but not all three.
made by University of California, Berkeley
computer scientist Eric Brewer at the 2000 Symposium on Principles of Distributed Computing
(PODC). In 2002, Seth Gilbert and Nancy Lynch
of MIT published a formal proof of Brewer's conjecture, establishing it as a theorem
.
The CAP theorem as proved by Gilbert and Lynch is somewhat narrower than what Brewer had in mind. The theorem sets up a scenario in which a replicated service is presented with two conflicting requests that arrive at distinct locations at a time when a link between them is failed. The obligation to provide availability despite partitioning failures leads the services to respond; at least one of these responses will necessarily be inconsistent with what a service implementing a true one-copy replication semantic would have done. The researchers then go on to show that other forms of consistency are achievable, including a property they call t-eventual consistency. Thus the theorem doesn't rule out achieving consistency in a distributed system, and says nothing about the cloud per-se or about scalability.
In contrast, as Eric Brewer posed the question, CAP is often taken to preclude consistency for services running in the highly elastic first-tier of a modern cloud computing system. These services are typically required to be stateless or to maintain only soft-state (cached data), and must be responsive even if inner-tier services are temporarily inaccessible. CAP, in this sense, uses "A" to mean immediately responsive, and "P" to mean "even if a failure prevents the first-tier service from connecting to some needed resource". In effect, we sacrifice consistency to gain faster responses in a more scalable manner.
Notice that partitioning, per-se, doesn't really enter into this broader interpretation of CAP. Indeed, there is no CAP theorem for the scenario actually seen where symmetric availability during partitioning failures is not normally required. There are two reasons for this: first, cloud platforms
have redundant, highly available networks and normally don't experience such failures. Second, if one of these very rare partitioning events were to occur, it would very likely cut some small set of replicas off not just from other components of the cloud, but also from their external clients, obviating the need for availability.
CAP is often cited as a justification for using weaker consistency models. Popular among these is BASE
, an acronym for Basically Available Soft-State services with Eventual Consistency. Amazon's Dynamo key-value store is often cited as the best example of how BASE looks in practice. In summary, the BASE methodology is characterized by high availability for first-tier services, leaving some kind of background cleanup mechanism to resolve any problems created by optimistic actions that later turn out to have violated consistency.
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
the CAP theorem, also known as Brewer's theorem, states that it is impossible for a distributed computer system
Distributed computing
Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
to simultaneously provide all three of the following guarantees:
- Consistency (all nodes see the same data at the same time)
- AvailabilityAvailabilityIn telecommunications and reliability theory, the term availability has the following meanings:* The degree to which a system, subsystem, or equipment is in a specified operable and committable state at the start of a mission, when the mission is called for at an unknown, i.e., a random, time...
(a guarantee that every request receives a response about whether it was successful or failed) - 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.
History
The theorem began as a conjectureConjecture
A conjecture is a proposition that is unproven but is thought to be true and has not been disproven. Karl Popper pioneered the use of the term "conjecture" in scientific philosophy. Conjecture is contrasted by hypothesis , which is a testable statement based on accepted grounds...
made by University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
computer scientist Eric Brewer at the 2000 Symposium on Principles of Distributed Computing
Symposium on Principles of Distributed Computing
The Symposium on Principles of Distributed Computing is an academic conference in the field of distributed computing organised annually by the Association for Computing Machinery ....
(PODC). In 2002, Seth Gilbert and Nancy Lynch
Nancy Lynch
Nancy Ann Lynch is a professor at the Massachusetts Institute of Technology. She is the NEC Professor of Software Science and Engineering in the EECS department and heads the Theory of Distributed Systems research group at MIT's Computer Science and Artificial Intelligence Laboratory.She is the...
of MIT published a formal proof of Brewer's conjecture, establishing it as a theorem
Theorem
In mathematics, a theorem is a statement that has been proven on the basis of previously established statements, such as other theorems, and previously accepted statements, such as axioms...
.
The CAP theorem as proved by Gilbert and Lynch is somewhat narrower than what Brewer had in mind. The theorem sets up a scenario in which a replicated service is presented with two conflicting requests that arrive at distinct locations at a time when a link between them is failed. The obligation to provide availability despite partitioning failures leads the services to respond; at least one of these responses will necessarily be inconsistent with what a service implementing a true one-copy replication semantic would have done. The researchers then go on to show that other forms of consistency are achievable, including a property they call t-eventual consistency. Thus the theorem doesn't rule out achieving consistency in a distributed system, and says nothing about the cloud per-se or about scalability.
In contrast, as Eric Brewer posed the question, CAP is often taken to preclude consistency for services running in the highly elastic first-tier of a modern cloud computing system. These services are typically required to be stateless or to maintain only soft-state (cached data), and must be responsive even if inner-tier services are temporarily inaccessible. CAP, in this sense, uses "A" to mean immediately responsive, and "P" to mean "even if a failure prevents the first-tier service from connecting to some needed resource". In effect, we sacrifice consistency to gain faster responses in a more scalable manner.
Notice that partitioning, per-se, doesn't really enter into this broader interpretation of CAP. Indeed, there is no CAP theorem for the scenario actually seen where symmetric availability during partitioning failures is not normally required. There are two reasons for this: first, cloud platforms
have redundant, highly available networks and normally don't experience such failures. Second, if one of these very rare partitioning events were to occur, it would very likely cut some small set of replicas off not just from other components of the cloud, but also from their external clients, obviating the need for availability.
CAP is often cited as a justification for using weaker consistency models. Popular among these is BASE
Eventual consistency
Eventual consistency is one of the consistency models used in the domain of parallel programming, for example in distributed shared memory, distributed transactions, and optimistic replication, it means that given a sufficiently long period of time over which no changes are sent, all updates can be...
, an acronym for Basically Available Soft-State services with Eventual Consistency. Amazon's Dynamo key-value store is often cited as the best example of how BASE looks in practice. In summary, the BASE methodology is characterized by high availability for first-tier services, leaving some kind of background cleanup mechanism to resolve any problems created by optimistic actions that later turn out to have violated consistency.