For in-depth information on various Big Data technologies, check out my free e-book “Introduction to Big Data“.

In PODC 2000, Eric Brewer conjectured that a distributed shared-data system cannot simultaneously provide all three of the following desirable properties:

  • Consistency

All nodes see the same data at the same time. It is equivalent to having a single up-to-date copy of the data.

  • Availability

Every request received by a non-failing node in the system must result in a response. Even when severe network failures occur, every request must terminate.

  • Partition tolerance

The system continues to operate despite arbitrary message loss or failure of part of the system.

In 2002, Gilbert and Lynch proved this in the asynchronous and partially synchronous network models. Thus it is called the CAP Theorem now.

Firstly one should notice that the definition of consistency in CAP is different from the one in ACID (Atomicity, Consistency, Isolation, Durability). The consistency in ACID means that a transaction preserves all the database rules. On the other hand, the consistency in CAP refers only to single copy consistency, a strict subset of ACID consistency.

The CAP theorem attempted to justify the design formulation of “2 of 3” CAP properties, leaving three viable design options: CP, AP, and CA. However, CA is not really a coherent option in distributed computing because a system that is not Partition-tolerant will be forced to give up Consistency or Availability during a partition. Therefore, the theorem is generally interpreted as: during a network partition, a distributed system must choose either Consistency or Availability. Note that CAP should allow perfect C and A most of the time since partitions are rare. In fact, a simple centralized algorithm meets these requirements. In practice, it is common assuming that a single datacenter has no partitions within, and thus allows the designs for CA within a single site.

Furthermore, a distributed system may not be simply classified as CP or AP because the choice between C and A can occur many times within the same system at very fine granularity. Not only can subsystems make different choices, but the choice can change according to the operation or even the specific data or user involved.

In the CAP theorem, the three properties are treated as binary. For example, Gilbert and Lynch require 100% availability for simplicity. But the availability could be continuous from 0 to 100 percent in real world. The consistency can also have many levels, e.g. different C in CAP and ACID. Due to the latency, the system may also have disagreement about whether a partition exists. In practice, the essence of CAP takes place during a timeout, a period when the program must make the partition decision. Pragmatically a partition is a time bound on communication. Therefore, there is no global notion of a partition, since some nodes might detect a partition, and others might not.

Advertisements