sult about systems in general, this definition interprets
availability as a property of an algorithm, not as an ob-
served metric during system operation – i.e. they de-
fine a system as being “available” or “unavailable” stat-
ically, based on its algorithms, not its operational status
at some point in time.
One particular execution of the algorithm is avail-
able if every request in that execution eventually re-
ceives a response. Thus, an algorithm is “available” un-
der Gilbert and Lynch’s definition if all possible exe-
cutions of the algorithm are available. That is, the al-
gorithm must guarantee that requests always result in
responses, no matter what happens in the system (see
section 2.3.1).
Note that Gilbert and Lynch’s definition requires any
non-failed node to be able to generate valid responses,
even if that node is completely isolated from the other
nodes. This definition is at odds with Fox and Brewer’s
original proposal of CAP, which states that “data is con-
sidered highly available if a given consumer of the data
can always reach some replica” [24, emphasis original].
Many so-called highly available or fault-tolerant sys-
tems have very high uptime in practice, but are in fact
“unavailable” under Gilbert and Lynch’s definition [34]:
for example, in a system with an elected leader or pri-
mary node, if a client that cannot reach the leader due
to a network fault, the client cannot perform any writes,
even though it may be able to reach another replica.
2.1.2 No maximum latency
Note that Gilbert and Lynch’s definition of availability
does not specify any upper bound on operation latency:
it only requires requests to eventually return a response
within some unbounded but finite time. This is conve-
nient for proof purposes, but does not closely match our
intuitive notion of availability (in most situations, a ser-
vice that takes a week to respond might as well be con-
sidered unavailable).
This definition of availability is a pure liveness prop-
erty, not a safety property [5]: that is, at any point in
time, if the response has not yet arrived, there is still
hope that the availability property might still be ful-
filled, because the response may yet arrive – it is never
too late. This aspect of the definition will be impor-
tant in section 3, when we examine Gilbert and Lynch’s
proofs in more detail.
(In section 4 we will discuss a definition of availabil-
ity that takes latency into account.)
2.1.3 Failed nodes
Another noteworthy aspect of Gilbert and Lynch’s def-
inition of availability is the proviso of applying only to
non-failed nodes. This allows the aforementioned defi-
nition of a CA system as one that fails catastrophically
if a network partition occurs: if the partition causes all
nodes to fail, then the availability requirement does not
apply to any nodes, and thus it is trivially satisfied, even
if no node is able to respond to any requests. This defini-
tion is logically sound, but somewhat counter-intuitive.
2.2 Consistency
Consistency is also an overloaded word in data sys-
tems: consistency in the sense of ACID is a very differ-
ent property from consistency in CAP [17]. In the dis-
tributed systems literature, consistency is usually under-
stood as not one particular property, but as a spectrum of
models with varying strengths of guarantee. Examples
of such consistency models include linearizability [30],
sequential consistency [38], causal consistency [4] and
PRAM [42].
There is some similarity between consistency mod-
els and transaction isolation models such as serializ-
ability [15], snapshot isolation [14], repeatable read and
read committed [3, 27]. Both describe restrictions on
the values that operations may return, depending on
other (prior or concurrent) operations. The difference is
that transaction isolation models are usually formalized
assuming a single replica, and operate at the granular-
ity of transactions (each transaction may read or write
multiple objects). Consistency models assume multi-
ple replicas, but are usually defined in terms of single-
object operations (not grouped into transactions). Bailis
et al. [12] demonstrate a unified framework for reason-
ing about both distributed consistency and transaction
isolation in terms of CAP.
2.2.1 The C in CAP
Fox and Brewer [24] define the C in CAP as one-
copy serializability (1SR) [15], whereas Gilbert and
Lynch [25] define it as linearizability. Those defini-
tions are not identical, but fairly similar.
2
Both are
2
Linearizability is a recency guarantee, whereas 1SR is not. 1SR
requires isolated execution of multi-object transactions, which lin-
earizability does not. Both require coordination, in the sense of sec-
tion 4.4 [12].
3