Client-centric Consistency

Monotonic Reads + Monotonic Writes + Read Your Writes + Writes Follow Reads

Data-centric vs. Client-centric

• Data-centric consistency models aim at providing a system-wide consistent view on a data store.

  • An important assumption is that concurrent processes may be simultaneously updating the data store, and that it is necessary to provide consistency in the face of such concurrency.

• Client-centric consistency models provide guarantees for a single client concerning the consistency of accesses to a data store by that client.

  • No guarantees are given concerning concurrent accesses by different clients.

  • It assumes no simultaneous updates to the data store or they

    can be relatively easily resolved

Notations

• Let $x_i$ and $x_j$ be the versions of data item $x$.

• Version $x_i$ is the result of a series of write operations, which is denoted as the write set $WS(x_i)$.

• $WS(x_i;x_j)$ means $x_j$ follows from $x_i$ ($x_j$ is obtained from $x_i$ plus some write operations).

• $WS(x_i|x_j)$ means we do not know if $x_j$ follows from $x_i$.

Model 1: Monotonic Reads

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 once a process has seen a value of $x$, it will never see an older version of $x$.

• Use case: distributed email database

  • A user reads his email in San Francisco.

  • He later flies to New York and opens his mailbox again.

  • The messages that were in the mailbox in San Francisco

    will also be in the mailbox when it is opened in New York.

• Important: study the example in Textbook Section 7.3 Figure 7.16.

Model 2: Monotonic Writes

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

• Monotonic-write consistency guarantees that write operations by the same process are propagated in the correct order to all copies of the data store.

• If we have two successive operations $W_k(x_i)$ and $W_k(x_j)$ by process $P_k$, then, regardless where $W_k(x_j)$ takes place, we also have $WS(x_i;x_j)$.

• Use case: software library

  • Each update replaces one or more functions, leading to a next version.

  • Monotonic-write consistency guarantee that if an update is performed on a copy of the library, all preceding updates will be performed first.

  • The resulting library is indeed the most recent version and includes all updates that have led to previous versions of the library.

• Important: study the example in Textbook Section 7.3 Figure 7.17.

Model 3: Read Your Writes

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.

• Use case: Web documents

  • A user updates a Web document using an editor.

  • He then checks the result from a Web browser.

  • Read-your-writes consistency guarantees that the browser’s or the server’s cache is invalidated when the page is updated.

  • So he can see the updated file instead of cached copy of the original file.

• Important: study the example in Textbook Section 7.3 Figure 7.18.

Model 4: Writes Follow Reads

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.

• Use case: network newsgroup

  • A user first reads an article $A$.

  • Then she 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.

  • Users see a posting of a reaction to an article only after they have seen the original article.

• Important: study the example in Textbook Section 7.3 Figure 7.19.