Causal consistency
Causal consistency is one of the main consistency models that can be used for distributed implementations of data structures in the domain of concurrent programming (e.g. in distributed shared memory, distributed transactions etc.).
Since other strong consistency criteria like linearizability and sequential consistency are costly, both in time and space, and impossible to implement in some situations, causal consistency was proposed in the nineties [1] as a weak consistency criteria in order to specify shared memory in a more efficient way. Also, causality represents a distributed execution as a partial order based on Lamport's concept of potential causality.[2]
Definition
Causal consistency can be defined as a model that captures the causal relationships between operations and guarantees that every process sees operations in that order. For instance, If event B is caused or influenced by an earlier event A, then causal consistency requires that every other process first see A, then see B. In other words, causal consistency distinguishes between events that are “causally related” and those that are not. Two events are causally related if one causes the other. Events that are causally unrelated are concurrent.[3]
Thus, a system provides causal consistency if this following condition holds: writes that are potentially causally related are seen by every process of the distributed system in the same order. Concurrent writes (i.e. ones that are not causally related) may be observed in different order by different processes.[3]
This is weaker than sequential consistency, which requires that all processes see all writes in the same order,[4] but is stronger than PRAM consistency, which requires only writes done by a single process to be seen in the same order by every other process.[5] Hence, it follows that when a system is sequentially consistent, it is also causally consistent. Additionally, It is clear that causal consistency implies PRAM consistency, but not vice versa.
Example
As an example of causal consistency, let's consider the following event sequence.[6]
| P1 : | W(x)1 | W(x)3 | |||
| P2 : | R(x)1 | W(x)2 | |||
| P3 : | R(x)1 | R(x)3 | R(x)2 | ||
| P4 : | R(x)1 | R(x)2 | R(x)3 |
It's clear that the W(x)2 is influenced by W(x)1 which means that these two writes,W(x)1and W(x)2, are causally related when P2 see the first write by P1. Also, another thing to note is that W(x)2 and W(x)3, without the intervening read, are concurrent since P3 and P4 see them in different orders.
Guarantees
In fact, causal consistency ensures some session guarantees as defined by Terry et. al:[7]
- Read Your Writes : read operations are guaranteed to indicate earlier writes.
- Monotonic Reads: successive reads are guaranteed to indicate an up-to-date increasing set of writes.
- Writes Follow Reads: guarantee that writes are reproduced after reads by which they are influenced.
- Monotonic Writes: guarantee that writes must follow writes that logically come before them.
Implementation
Causal consistency implementation demands observation of which processes have seen which writes. It effectively implies that it is important to construct and maintain a dependency graph expressing which operations are causally related.
On the other hand, causal consistency is considered as a useful model to solve many problems such as ordering operations, which cannot be solved in the eventual consistency. The causal consistency guarantees that every process sees operations in the same causal order, and this makes the causal consistency to be stronger than the eventual consistency. Additionally, causal consistency can be extend to all abstract data types such as queues or counters.[8]
References
- ↑ Ahamad, M., Neiger, G., Burns, J. E., Kohli, P., & Hutto, P. W. (1995). Causal memory: Definitions, implementation, and programming. Distributed Computing, 9(1), 37-49.
- ↑ Lamport, L. (1978). Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7), 558-565.Chicago
- 1 2 Gogia, R., Chhabra, P., & Kumari, R. (2014). Consistency Models in Distributed Shared Memory Systems.International Journal of Computer Science and Mobile Computing,196-201
- ↑ Lamport, L. (1979). How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE transactions on computers, 100(9), 690-691.
- ↑ Lipton, R. J., & Sandberg, J. S. (1988). PRAM: A scalable shared memory. Princeton University, Department of Computer Science.Chicago
- ↑ Mosberger, D. (1993). Memory consistency models. ACM SIGOPS Operating Systems Review, 27(1), 18-26.
- ↑ Terry, D. B., Demers, A. J., Petersen, K., Spreitzer, M. J., Theimer, M. M., & Welch, B. B. (1994, September). Session guarantees for weakly consistent replicated data. In Parallel and Distributed Information Systems, 1994., Proceedings of the Third International Conference on (pp. 140-149). IEEE.
- ↑ Perrin, M., Mostefaoui, A., & Jard, C. (2016, February). Causal consistency: beyond memory. In Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (p. 26). ACM.