0
$\begingroup$

I'm currently studying Sequential consistency vs linearizability:

I know that SC has to be consistent with the order of how the individual client issued them, and for linearizability, it's with the real-time ordering.

What I don't understand is:

"The interleaved sequence of operations meets the specification of a (single) correct copy of the objects. "

Which is the first property of both Sequential consistency and linearizability

For me, it sounds like that if 2 clients communicate with some system, the state of the objects should be the same on a single server and on a system with multiple replica managers RM.

But if that is true, how is this example SC:

Client 1:

SetBalance x in RM B to 1

Client 2:

getBalance y in RM A = 0 getBalance x in RM A = 0

Client 1:

SetBalance y in RM A to 2

But if the above example is true, that means my understanding of "The interleaved sequence..." is wrong. since that would imply that the second get balance of client 2 should be 1 ( but at the same time, that means that the system is linearizable since that follows real-time ordering).

So what does:

"The interleaved sequence of operations meets the specification of a (single) correct copy of the objects. "

Mean? and why is it used to determine the correctness of replication

$\endgroup$
0
$\begingroup$

A Sequential Consistent (SC) system should behave as if there is just a single copy of the data.

So lets try to determine a possible memory order for your scenario:

1:client2:read(y=0)
2:client2:read(x=0)
3:client1:write(x=1)
4:client1:write(y=2)

This is valid according to SC. Keep in mind that the real time order of requests, doesn't need to preserved. So perhaps the client2.read(x=1) happened later than the client1.write(x=1), it can be ordered in the memory order before the write.

Lets change the example a bit to make it more interesting:

1:client1:write(x=1)
2:client1:write(y=2)
3:client2:read(y=2)
4:client2:read(x=0)

This example isn't SC because the read of x=0, doesn't see the most recent write before it in the memory order. It should have seen x=1. And this is the consequence of the lack of coherence (so what you could get with replicas being out of sync).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.