How is this example sequentially consistent but not linearizable?

Question

Background information that I know(But not understand with examples, I will be glad if you could explain it to me with examples)

A replicated service is said to be linearizable if for any executin there is some interleaving of operations that

1. Meets the specifications of a non replicated service

2. Matches the real time order of operations in actual execution.

A replicated service is said to be sequentially consistent if for any execution there is some interleaving of operations that

1. Meets the specifications of a non replicated service

2. Matches the program order of operations in actual execution.

Here is what is written in Colouris's distributed system book about the example I have shown in image-

This execution is possible under a naive replication strategy even if neither of the computers A or B fails but if update of x that client 1 made at B hasn't reached A when client 2 reads it. The real time criterion for linearizability is not satisfied, since $getBalance_A(x)\to 0$ occurs later than $setBalance_B(x,1)$: but the following interleaving satisfies both criteria for sequential consistency: $getBalance_A(y)\to 0$,$getBalance_A(x)\to 0$, $setBalance_B(x,1)$,$setBalance_A(y,2)$

I am failing to comprehend anything written here. I think it is mainly because of my failure to understand the example of linearizability and sequential consistency. Can you shed some light here and help me out here? I will be really grateful for any help.

Answer 1

The key difference between linearizability and sequential consistency is that linearizability needs to respect the real-time order (nobody should be able to prove the real-time order wasn't respected) and sequential consistency does not.

So when when client1 calls setBalance(x,1) and client2 later calls getBalance(x), it should return the value 1. But client2 returns the value 0; the value before setBalance(x,1) was called. So at least one of these methods isn't respecting the real-time order and hence the example is not linearizable.

So why is the example sequential consistent? Since the real time order doesn't need to be respected, the getBalance(x) and getBalance(y) can be skewed before the calls to setBalance(x,1) and setBalance(y,2). So for both client1 and client 2 the program order has not been violated.

Answer 2

I believe that it is obvious that linearizability is not satisfied here, because real time order of operations is not preserved. In linerizable system, once Client 1 set the balance, Client 2 must have been immediately seen this on his next read.

With sequential consistency it is a bit more tricky. For sequentially consistent system there is no requirements at all for mutual order of operations between different processes. That's why it is perfectly possible that write by client one on one replica is not reflected in the read from the second replica.

In this video, I explain the definitions of linearizability and sequential consistency and differences between them and I hope that after watching it you would be able to fully understand answer on your question.