Causal consistency

Causal consistency is one of the consistency models used in the domain of the concurrent programming (e.g. in distributed shared memory, distributed transactions etc.).

A system provides causal consistency if memory operations that potentially are causally related are seen by every node of the system in the same order. Concurrent writes (i.e. ones that are not causally related) may be seen in different order by different nodes. This is weaker than sequential consistency, which requires that all nodes see all writes in the same order, but is stronger than PRAM consistency, which requires only writes done by a single node to be seen in the same order from every other node. Condition-writes that are potentially causally related must be seen by all processes in the same order. Concurrent writes may be seen in a different order on different machines.

When a node performs a read followed later by a write, even on a different variable, the first operation is said to be causally ordered before the second, because the value stored by the write may have been dependent upon the result of the read. Similarly, a read operation is causally ordered after the earlier write on the same variable that stored the data retrieved by the read. Also, even two write operations performed by the same node are defined to be causally ordered, in the order they were performed. Intuitively, after writing value v into variable x, a node knows that a read of x would give v, so a later write could be said to be (potentially) causally related to the earlier one. Finally, we force this causal order to be transitive: that is, we say that if operation A is (causally) ordered before B, and B is ordered before C, A is ordered before C.

Operations that are not causally related, even through other operations, are said to be concurrent.

External links

• Causal Memory: Definitions, Implementation and Programming (1994), a paper from the authors of the definition