technical/2020/05/23/consistency-models about josehu07.github.io HOT 2 OPEN

In strong consistency, what do you mean by x<y?

What would be a good running example to show the difference of all 4 models here?

from josehu07.github.io.

In strong consistency, what do you mean by x < y?

It means operation x is ordered before operation y. In the examples, I used characters a ~ h to name operations and used x to name a global variable, which might be a bit confusing. Say a < b, it means operation a is ordered before operation b.

What would be a good running example to show the difference of all 4 models here?

The 4 examples shown in figures should be sufficient to demonstrate the differences. Basically,

• Strong consistency (linearizability) means all nodes agree on the same global ordering of operations AND operations must respect the real-time property: if a read starts later (in terms of physical real-world time) after the finish of a write, it must see the effect of that write. In the example of 1), c must read out 1 because it starts after the ack of a; similarly for d after b. This is the common notion of "consistency".
• Sequential consistency means all nodes agree on the same global ordering, but that ordering might not respect the real-time property. In the example of 2), d actually starts after the ack of b but all nodes agree on an ordering that d happens before b, hence reading out 1. This could happen when a system acks a write earlier than the write has been accepted by a majority.
• Causal consistency means that nodes do not have to agree on the same global ordering. But for each node (or said client thread) itself, the ordering of operations issued by itself must be maintained in the final ordering of all operations it thinks. In other words, the final ordering of all ops it agrees on should be the original ordering of its own operations interleaved with other nodes' operations. This could happen when a system acks a write as soon as the local state has been changed and say a read just reads the local state.
• Eventual consistency means that even the operations issued by a single client thread can end up out-of-order -- even if a client thread issues and completes a Wx2 followed by a Rx, it could read out 1. This could happen when a system implements writes entirely async and acks a write immediately, say even earlier than the local state has been changed.

I will update the wording of the post a bit to try to state the differences clearer.

from josehu07.github.io.