Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How causal consistency is different to sequential consistency?

I understand that in sequential consistency all processes have to be processed sequentially. For example:

Process 1     Process 2
x = 1         z = 5
y = 2         p = 3

So, we can get x=1, z=5, y=2, p=3 or z=5, p=3, x=1, y=2. But what matters is that p can only be executed once z is executed etc, correct?

What about causal consistency? I don't see any difference there. Any sketches, or code in JAVA or C would be great. Thank you.

like image 919
good_evening Avatar asked Jun 04 '13 23:06

good_evening


People also ask

Why do you think causal consistency is weaker than sequential consistency?

Different processes may observe concurrent writes in different orders. The Causal Consistency model is weaker than sequential consistency, which ensures that all processes observe all write operations in common order, whether causally related or not.

What is causal consistency in distributed systems?

Causal consistency [1] is one of the consistency criteria that can be used on distributed databases as consistency criteria. Distributed database provides causal consistency if read and write operations that are causally related are seen by every node of the distributed system in the same order.

What is meant by sequential consistency?

Sequential consistency is a strong safety property for concurrent systems. Informally, sequential consistency implies that operations appear to take place in some total order, and that that order is consistent with the order of operations on each individual process.


1 Answers

In sequential consistency all of the memory operations appear to all nodes to have appeared in some order.

So in your example processes 1, 2, and 3 would all see the memory operations in the same order. (There are 6 possible orders for the 4 operations, but all the processes would agree on what that order is.)

In causal consistency processes 1, 2 and 3 could all observe those writes to occur in different orders. There are two rules:

  1. Everyone agrees that process i's writes happened in the same order that process i did them.
  2. If any process, i, does a read of a location x and gets a value that was written by a different process, j, then all the threads agree that process j's write to location x preceded process i's read of location x.

Since, in your original example there are no read operations then it is possible, for example, for process 1 to believe that the writes happened in the order x=1, y=2, z=5, p=3 while process 2 believes that the writes happened in the order z=5, p=3, x=1, y=2 and process 3 believes that they happened in order z=5, x=1, p=3, y=2.

The paper that the Wikipedia page points to gives some examples that are more interesting (involve reads).

Causal memory by itself seems not very useful. Later in the paper they show how to implement something kind of like a barrier with a causal memory (and a helper process), but mention that there doesn't seem to be any convenient way to implement a critical section.

So they end up doing what weakly consistent or release consistent memories do, and adding a synchronization primitive, which needs to be sequentially consistent.

like image 135
Wandering Logic Avatar answered Nov 06 '22 11:11

Wandering Logic