CAP Theorem

January 25, 2013

The CAP theorem or the Brewer’s theorem states that a distributed system can only guarantee two out of the three :

  • Consistency – results of earlier writes on a node are read by read operations on the node
  • Availability – a guarantee that every request receives a success/failure response
  • Partition – the system continues to operate despite a failure of a subsystem or some message loss

This is similar to the three constraints of project management where you can choose two constraints and the third gets decided : time, cost and scope.

Henry Robinson has given a shown a very good understanding of the concept on Quora .

An informal proof which helps the intuition from above :

             “The intuition behind this result is as follows: to be consistent, all nodes have to see the same set of updates in the same order. But if the network suffers a partition, updates in one partition might not make it to the other partition before a client reads from the out-of-date partition *after* having read from the up-to-date one. The only thing you can do to cope with this possibility is to stop serving requests from the out-of-date partition, but then the service is no longer 100% available. “

                “Since, until there is a failure, it is relatively easy to guarantee availability and consistency in well-behaved executions, so some systems gracefully degrade their consistency or availability guarantees only at the point of failure. “

After gaining this understanding, some notable points from InfoQ article on CAP

  • CAP prohibits only a tiny part of the design space: perfect availability and consistency in the presence of partitions, which are rare.
  • ACID properties focuss on consistency
  • BASE properties focus on availability

Relevant links

ACID is a set of properties that apply specifically to database transactions
The CAP theorem is a set of basic requirements that describe any distributed system (not just storage/database systems).