2
$\begingroup$

This example

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.

$\endgroup$
2
  • $\begingroup$ This question might be too broad. (Any votes?) "Here's something I read, I'm failing to comprehend anything here" might be too open-ended to admit a good answer. It's hard to know what you do and don't understand, and we probably can't explain everything in one answer. Our site works best with narrowly focused questions that ask about one specific thing that you don't understand. Part of our mission is to build up an archive of high-quality questions and answers that will be useful to others, so ideally it would be one conceptual aspect that might be useful to others in the future as well. $\endgroup$
    – D.W.
    Commented Aug 20, 2021 at 18:15
  • $\begingroup$ If anyone is familiar with Colouris's definitions, they might be able to answer. At the moment, my first impression is that Colouris's definition of linearizability differs from the standard notion, e.g. based on linearization points en.wikipedia.org/wiki/Linearizability#Linearization_points $\endgroup$ Commented Aug 27, 2021 at 13:34

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.