Sixteen year ago,
Eric Brewer introduced what is now known as the CAP theorem, which states that
for a web service it is impossible to guarantee consistency, availability, and
partition tolerance. The conjecture was
based on Brewer's experiences at Inktomi--a search engine company he cofounded,
and was published without proof. Gilbert
and Lynch presented one in their paper: "Brewer's
Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web
Services."

The paper is a good
theoretical read, and the proofs the authors present are very tractable. They
first begin by formalizing the concepts
of consistency (the authors use atomic in the paper), availability, and partition
tolerance. For a consistent service, there is a total order on all operations
such that each operation looks as if it were completed at a single instant. For
availability, every request received by a non-failing node in the system must
result in a response. Finally for partition tolerance the network is allowed to lose arbitrarily many messages
sent from one node to another.

The authors use
these definitions to present their first impossibility result:

"It is impossible in the asynchronous network model to implement a read/write data object that guarantees the following properties:

- Availability
- Atomic consistency

in all fair executions (including those in which messages are lost). "

They prove the
assertion by contradiction. The proof uses
two nodes/partitions in the system $A$ and $B$, where all the messages
between $A$ and $B$ are lost. The proof assumes two operations $\alpha$ and
$\beta$ that execute separately on $A$ and $B$, and are ordered such that
$\beta$ occurs after $\alpha$ has ended.
$\alpha$ executes a write on partition $A$, $\beta$ executes a read from
partition $B$ with all messages between $A$ and $B$ lost. Each operation on its
own returns consistent results, while combined together as a new operation
$\alpha+\beta$, return inconsistent data, proving the theorem.

The authors extend
the result through a similar method of argument to all types of executions,
since nodes $A$ and $B$ can't tell if the messages between them are lost in an
asynchronous network (without the concept of clocks or time). The authors
provide some example systems for asynchronous networks that provide two of the
three guarantees (C,A, and P).

For partially
synchronous systems, where every node has a clock, and all clocks increase at
the same rate, but are not synchronized, the authors present another
impossibility result:

"It is impossible in the partially synchronous network model to implement a read/write data object that guarantees the following properties:

in all executions (even those in which messages are lost)"

- Availability
- Atomic consistency

The proof is similar
to the original impossibility result, with execution $\beta$ sufficiently
delayed for the messages not to reach partition $B$.

The authors close by
providing a weaker consistency condition that allows stale data to be returned
when there are partitions through the use of a centralized node, and the formal
requirements it places on the quality of the stale data returned .

## No comments :

## Post a Comment