How causal consistency is different to sequential consistency?

Question

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.

Answer 1

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.