4 / 6 Consistency Models

Fifty Milliseconds Too Late

Three clients operate on one register x, initially 0. Times are milliseconds on a single wall clock the observer trusts; each row shows when the client sent the request and when it got its response.

client operation sent responded result
A write(x, 1) 0 40 ok
B read(x) 50 60 0
C read(x) 70 80 1

How should this history be classified?

A

Linearizable if B and C were talking to different replicas, and not linearizable if they shared one.

B

Sequentially consistent but not linearizable.

C

Linearizable, since a valid order exists in which B's read precedes A's write.

D

Neither, because B returned a value that a completed write had already replaced.