Causal consistency
Causal consistency is known as one of the main weak memory consistency models that can be used to assign consistency restrictions to all memory accesses for distributed implementations of data structures in the domain of concurrent programming. For example, in distributed shared memory and distributed transactions.
Other stronger consistency models like sequential consistency and linearizability have downsides such as: they take too long and require more space; also in terms of implementation, they are unattainable in some situations. Due to those reasons, causal consistency was proposed in the nineties [1] as a weaker consistency model in order to improve the performance and gain in efficiency when defining the semantics of memory accesses in shared memory models. In causality, distributed executions are represented as partial orders 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 in the system and guarantees that each process can observe those causally related operations in common causal order. In other words, all processes in the system agree on the order of the causally related operations. [1] For instance, If there is an operation or event A that causes another operation B, then causal consistency provides an assurance that each other process of the system observes operation A before observing operation B. Therefore, causally related operations and concurrent operations are distinguishable in the causal consistency model. In more detail, if one write operation influences another write operation, then these two operations are causally related, one relies on the other. Concurrent operations are the ones that are unrelated by causality or causally independent. In particular, concurrent writes are independent operations, no one causes or influences the other. [3]
Thus, a system provides causal consistency if this following condition holds: write operations that are related by potential causality are seen by each process of the system in common order. Also, concurrent writes can occur in any order and can be seen in different orders by the processes in the system. [3]
Subsequently, causal consistency model is weaker than sequential consistency, which expects all processes to observe not just causally related writes but all write operations in common order. [4] However, causal consistency is stronger than PRAM consistency, which requires only the write operations that are done by a single process to be observed in common order by each other process. [5] Hence, it follows that when a system is sequentially consistent, it is also causally consistent. Additionally, It is obvious that causal consistency implies PRAM consistency, but not vice versa.
Example
Here is an example of causal consistency as mentioned in reference [6]: [6]
Causal relations are respected in the following event sequence :
| 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 is obvious that the write operation W(x)2 is caused by an earlier write W(x)1, and it means that these two writes W(x)1 and W(x)2 are causally related as process P2 observes, reads, the earlier write W(x)1 that is done by process P1. Thus, every other process observes W(x)1 first before observing W(x)2. Also, another thing to notice is that the two write operations W(x)2 and W(x)3, with no intervening read operations, are concurrent since processes P3 and P4 observe, read, them in different orders.
Guarantees
In fact, there are four different session guarantees that are ensured and guaranteed by the causal consistency model. Those guarantees are summarized below as defined by Terry et. al: [7]
- Read Your Writes : this means that preceding write operations are indicated and reflected by the following read operations.
- Monotonic Reads: this implies that an up-to-date increasing set of write operations is guaranteed to be indicated by later read operations.
- Writes Follow Reads: this provides an assurance that write operations follow and come after reads by which they are influenced.
- Monotonic Writes: this guarantees that write operations must go after other writes that reasonably should precede them.
Implementation
In brief, the implementation of causal consistency relies on a critical observation to see which write operations are seen by which processes. In other words, in order to implement the causal consistency model, it is important to build and maintain a dependency graph for memory accesses showing the causal relationships between the operations.
On the other hand, causal consistency is a useful consistency model to solve many problems which cannot be solved by other consistency criteria in distributed systems. For instance, in distributed databases, ordering operations problem cannot be solved by eventual consistency, but causal consistency can solve that. [8] The causal consistency provides an assurance that every process observes operations in the same causal order, and this shows why the causal consistency is stronger than eventual consistency. Also, causal consistency can be developed for all abstract data types such as queues or counters. [9]
References
- 1 2 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.
- ↑ Elbushra, M. M., & Lindström, J. (2015). Causal Consistent Databases. Open Journal of Databases (OJDB), 2(1), 17-35.
- ↑ 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.