Introduction to Distributed System ITec3102

CHAPTER V: CLIENT-CENTRIC CONSISTENCY MODELS

Client‐centric consistency provides guarantees for a single client concerning the consistency of
accesses to a data store by that client.

1. Monotonic reads

The first client-centric consistency model is that of monotonic reads. A data store is said to
provide monotonic-read consistency if the following condition holds:

If a process reads the value of a data item x, any successive read operation on x by that process
will always return that same value or a more recent value.

In other words, monotonic-read consistency guarantees that if a process has seen a value of x at
time t, it will never see an older version of x at a later time. As an example where monotonic
reads are useful, consider a distributed email database. In such a database, each user's mailbox
may be distributed and replicated across multiple machines. Mail can be inserted in a mailbox at
any location. However, updates are propagated in a lazy (i.e., on demand) fashion. Only
when a copy needs certain data for consistency are those data propagated to that
copy. Suppose a user reads his mail in San Francisco. Assume that only reading
mail does not affect the mailbox, that is, messages are not removed, stored in
subdirectories, or even tagged as having already been read, and so on. When the
user later flies to New York and opens his mailbox again, monotonic-read consistency
guarantees that the messages that were in the mailbox in San Francisco will
also be in the mailbox when it is opened in New York. Using a notation similar to that for data-
centric consistency models, monotonic-read consistency can be graphically represented as shown
in Fig. 1. Along the vertical axis, two different local copies of the data store are shown, L I
and L 2. Time is shown along the horizontal axis as before. In all cases, we are interested in the
operations carried out by a single process P. These specific operations are shown in boldface are
connected by a dashed line representing the order in which they are carried out by P.

Figure 1. The read operations performed by a single process P at two different local copies of the
same data store. (a) A monotonic-read consistent data store. (b) A data store that does not
provide monotonic reads.

2. Monotonic Writes
Page 1 of 4
Introduction to Distributed System ITec3102

In many situations, it is important that write operations are propagated in the

correct order to all copies of the data store. This property is expressed in monotonic-write
consistency. In a monotonic-write consistent store, the following condition holds:

A write operation by a process on a data item x is completed before any successive write
operation on X by the same process.

Thus completing a write operation means that the copy on which a successive operation is
performed reflects the effect of a previous write operation by the same process, no matter where
that operation was initiated. In other words, a write operation on a copy of item x is performed
only if that copy has been brought up to date by means of any preceding write operation, which
may have taken place on other copies of x. If need be, the new write must wait for old ones to
finish. Note that monotonic-write consistency resembles data-centric FIFO consistency. The
essence of FIFO consistency is that write operations by the same process are performed in the
correct order everywhere. This ordering constraint also applies to monotonic writes, except that
we are now considering consistency only for a single process instead of for a collection of
concurrent processes. Bringing a copy of x up to date need not be necessary when each write
operation completely overwrites the present value of x. However, write operations are
often performed on only part of the state of a data item. Consider, for example, a
software library. In many cases, updating such a library is done by replacing one
or more functions, leading to a next version. With monotonic-write consistency,
guarantees are given that if an update is performed on a copy of the library, all
preceding updates will be performed first. The resulting library will then indeed
become the most recent version and will include all updates that have led to previous versions of
the library.

Monotonic-write consistency is shown in Fig. 2. In Fig. 2(a), process P performs a write

operation on x at local copy L1, presented as the operation W(XI). Later, P performs another
write operation on x, but this time at L2, shown as W(X2). To ensure monotonic-write
consistency, it is necessary that the previous write operation at L1 has already been propagated to
L2. This explains operation W(Xl) at L2, and why it takes place before W(X2)·

Figure 2. The write operations performed by a single process P at two different local copies of
the same data store. (a) A monotonic-write consistent data store. (b) A data store that does not
provide monotonic-write consistency.

Page 2 of 4
Introduction to Distributed System ITec3102

In contrast, 2(b) shows a situation in which monotonic-write consistency is not guaranteed.

Compared to Fig. 2(a), what is missing is the propagation of W (x 1) to copy L 2. In other words,
no guarantees can be given that the copy of x on which the second write is being performed has
the same or more recent value at the time W (x I)completed at L I.

3. Read Your Writes

A client-centric consistency model that is closely related to monotonic reads is as follows. A data
store is said to provide read-your-writes consistency, if the following condition holds:

The effect of a write operation by a process on data item x will always be

seen by a successive read operation on x by the same process.

In other words, a write operation is always completed before a successive read operation by the
same process, no matter where that read operation takes place. The absence of read-your-writes
consistency is sometimes experienced when updating Web documents and subsequently viewing
the effects. Update operations frequently take place by means of a standard editor or word
processor, which saves the new version on a file system that is shared by the Web server. The
user's Web browser accesses that same file, possibly after requesting it from the
local Web server. However, once the file has been fetched, either the server or the
browser often caches a local copy for subsequent accesses. Consequently, when the Web page is
updated, the user will not see the effects if the browser or the server returns the cached copy
instead of the original file. Read-your-writes consistency can guarantee that if the editor and
browser are integrated into a single program, the cache is invalidated when the page is updated,
so that the updated file is fetched and displayed. Similar effects occur when updating passwords.
For example, to enter a digital library on the Web, it is often necessary to have an account with
an accompanying password. However, changing a password make take some time to come
into effect, with the result that the library may be inaccessible to the user for a few minutes. The
delay can be caused because a separate server is used to manage passwords and it may take some
time to subsequently propagate (encrypted) passwords to the various servers that constitute the
library. Fig.3(a) shows a data store that provides read-your-writes consistency.
d by the last write operation by process P, instead of its last read.

Figure 3 (a) A data store that provides read-your-writes consistency. (b) A data store that does
not. In Fig. 3(a), process P performed a write operation W(XI) and later a read operation at a
different local copy. Read-your-writes consistency guarantees that he effects of the write
operation can be seen by the succeeding read operation. This is expressed by WS(XI ;X2), which
Page 3 of 4
Introduction to Distributed System ITec3102

states that W(Xl) is part of WS(X2)' In contrast, in Fig. 3(b), W(Xl) has been left out of WS(X2),
meaning that the effects of the previous write operation by process P have not been propagated
to L2.

4. Writes Follow Reads

The last client-centric consistency model is one in which updates are propagated as the result of
previous read operations. A data store is said to provide writes-follow-reads consistency, if the
following holds.

A write operation by a process on a data item x following a previous read operation on x by the
same process is guaranteed to take place on the same or a more recent value of x that was read.

In other words, any successive write operation by a process on a data item x will
be performed on a copy of x that is up to date with the value most recently read by that process.
Writes-follow-reads consistency can be used to guarantee that users of a network newsgroup see
a posting of a reaction to an article only after they have seen the original article .To understand
the problem, assume that a user first reads an article A. Then, he reacts by posting a response B.
By requiring writes-follow-reads consistency, B will be written to any copy of the newsgroup
only after A has been written as well. Note that users who only read articles need
not require any specific client-centric consistency model. The writes-follows reads consistency
assures that reactions to articles are stored at a local copy only if the original is stored there as
well.

Figure 4. (a) A writes-follow-reads consistent data store. (b) A data store that does not provide
writes-follow-reads consistency. This consistency model is shown in Fig. 4. In Fig. 4(a), a
process reads x at local copy L 1. The write operations that led to the value just read, also appear
in the write set at L 2. where the same process later performs a write operation.
(Note that other processes at L2 see those write operations as well.) In contrast, no
guarantees are given that the operation performed at L2, as shown in Fig. 4(b),
are performed on a copy that is consistent with the one just read at L 1 .

Page 4 of 4