Correctness of Linearizability vs Sequential consistency in replication 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:
&quot;The interleaved sequence of operations meets the specification of a (single) correct copy of the objects. &quot;
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 &quot;The interleaved sequence...&quot; 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:
&quot;The interleaved sequence of operations meets the specification of a (single) correct copy of the objects. &quot;
Mean? and why is it used to determine the correctness of replication
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).