Causal consistency
Encyclopedia
Causal consistency is one of the consistency model
s 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.
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.
Consistency model
In computer science, consistency models are used in distributed systems like distributed shared memory systems or distributed data stores . The system supports a given model, if operations on memory follow specific rules...
s used in the domain of the concurrent programming (e.g. in distributed shared memory
Distributed shared memory
Distributed Shared Memory , in Computer Architecture is a form of memory architecture where the memories can be addressed as one address space...
, 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
Sequential consistency
Sequential consistency is one of the consistency models used in the domain of concurrent programming . It was first defined as the property that requires that ".....
, which requires that all nodes see all writes in the same order, but is stronger than PRAM consistency
PRAM consistency
PRAM consistency also known as FIFO consistency, or Processor consistency.All processes see memory writes from one process in the order they were issued from the process....
, which requires only writes done by a single node to be seen in the same order from every other node.
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