Consistency Management in Cloud Storage Systems - Large Scale and Big Data: Processing and Management - page 327

four main cloud storage systems used by big cloud vendors in Section 10.4. To complete
our survey, we present different adaptive consistency approaches in Section 10.5 and
detail our approach Harmony in Section 10.6. A conclusion is provided in Section 10.7.

10.2 THE CAP THEOREM AND BEYOND

10.2.1 t he CAP t heorem
In his keynote speech [12], Brewer introduced what is known as the CAP theorem.
This theorem states that at most only two out of the three following properties can
be achieved simultaneously within a distributed system: Consistency, Availability,
and Partition Tolerance. The theorem was later proven by Gilbert and Lynch [13].
The three properties are important for most distributed applications such as web
applications. However, within the CAP theorem, one property needs to be forfeited,
thus introducing several tradeoffs. To better understand these tradeoffs, we will first
highlight the three properties and their importance in distributed systems.

10.2.1.1 Consistency
The consistency property guarantees that an operation or a transaction is performed
atomically and leaves the systems in a consistent state, or fails instead. This is
equivalent to the atomicity and consistency properties ( AC ) of the ACID (atomicity,
consistency, isolation, and Durability) semantics in relational database management
systems ( RDBMs ), where a common way to guarantee a strong level of consistency
is applying one-copy serializability.

10.2.1.2 Availability
In their CAP theorem proof [13], the authors define a distributed storage system as
continuously available if every request received by a nonfailing node must result in
a response. On the other hand, when introducing the original CAP theorem, Brewer
qualified a system to be available if almost all requests receive a response.

10.2.1.3 Partition Tolerance
In a system that is partition tolerant, the network is allowed to loose messages
between nodes from different components (datacenters for instance). When a net-
work partition appears, the network communication between two components
(racks, datacenters, etc.) is off and all the messages are lost. Since replicas may be
spread over different partitions in such a case, this property has a direct impact on
both consistency and availability.
The implications of the CAP theorem introduced challenging and fundamental
tradeoffs for distributed systems and service designers. Systems that are designed to
be deployed on single entities, such as an RDBM, aim to provide both availability
and consistency properties since partitions are not an issue. However, for distributed
systems that rely on networking, such as georeplicated systems, partition tolerance
is a must for a big majority of them. This in turn introduces, among other tradeoffs
derived from the CAP theorem, the Consistency vs. Availability as a major trade-
off. As shown in Figure 10.1, user requests can be served from different replicas in