Consistency Models

Distributed Systems. Don’t Be a Distributed Disaster

Why Consistency?

So far we created replicas/shared data for fault tolerance.
But to ensure if a request response gets most up to date data or to ensure that system acts like a single machine we need consistency amongst the machines.

Linearizability

Total Order + Real Time Order.

Here all the process see the latest data and hence the ordering as a whole is ensured.
All the operations see the latest data written and maintain real time ordering.
If 2 operations are overlapping with each other then they can be ordered anyway. Raft gives Linearizability.

Example 1:

In Example1 R should always read 2.

Example 2:

In Example 2 R is overlapping with w1 and w2 hence it could be put in any of the slots between w(1) and w(2)
_ W(1) _ W(2) _
R W(1) _ W(2) _ 
_ W(1) R W(2) _
_  W(1) _ W(2) R 

So it can return 1 or 2 

Sequential Consistency

Total Order + Process Order.

Appears to be a single machine.
Total order means if an order is defined you cannot jumble it. But since it maintains total order once you make following order w(2), w(1) then you cannot make w(1), w(2). Essentially we have to ensure there exists a total order and process wise ordering is maintained

Example 3:

In Example 3: w(2) should come before R1=1 since they both belong to the same process. 
Now in the above example in order R1 to read 1 w(1) should come before R1
And since w(2) and R1=1 are in same process 

Correct sequence will be: 
 w(2) w(1) R1=1

Causal+ Consistency

Partial Order + Eventual.
Here ‘+’ means — eventually data will be consistent.

This uses Lamport logical clock to order operations. Hence 2 operations which are parallel cannot e ordered.
Causal+ syncs data eventually but maintains partial order. Hence the sync order will be A then B and not B then A. Bayou provides Causal+ consistency.

Example 4:

Example 5:

In Example 5: 
W(x=1) and W(x=2) are causally related. 
Hence correct reading order of operations will be:
r(x) = 1, r(x) = 2

Example 6:

In Example 6: W(2) and W(3) are concurrent hence following reads are possible:  
r(x) = 3, r(x) = 2
Or
r(x) = 2, r(x) = 3

Reference:
https://www.cs.princeton.edu/courses/archive/fall22/cos418/docs/precept_08_consistency.pdf
https://www.cs.princeton.edu/courses/archive/fall22/cos418/docs/L15-cops.pdf
https://www.youtube.com/watch?v=YmhmsHE7be4
https://www.youtube.com/watch?v=noUNH3jDLC0