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.
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.
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.
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.
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:
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With