ABSTRACT
In distributed systems where strong consistency is costly when not impossible, causal consistency provides a valuable abstraction to represent program executions as partial orders. In addition to the sequential program order of each computing entity, causal order also contains the semantic links between the events that affect the shared objects -- messages emission and reception in a communication channel, reads and writes on a shared register. Usual approaches based on semantic links are very difficult to adapt to other data types such as queues or counters because they require a specific analysis of causal dependencies for each data type. This paper presents a new approach to define causal consistency for any abstract data type based on sequential specifications. It explores, formalizes and studies the differences between three variations of causal consistency and highlights them in the light of PRAM, eventual consistency and sequential consistency: weak causal consistency, that captures the notion of causality preservation when focusing on convergence; causal convergence that mixes weak causal consistency and convergence; and causal consistency, that coincides with causal memory when applied to shared memory.
- Sarita V Adve and Kourosh Gharachorloo. Shared memory consistency models: A tutorial. computer, 29(12):66--76, 1996. Google ScholarDigital Library
- Mustaque Ahamad, Gil Neiger, James E Burns, Prince Kohli, and Phillip W Hutto. Causal memory: Definitions, implementation, and programming. Distributed Computing, 9(1):37--49, 1995.Google ScholarDigital Library
- Hagit Attiya and Jennifer L Welch. Sequential consistency versus linearizability. ACM Transactions on Computer Systems (TOCS), 12(2):91--122, 1994. Google ScholarDigital Library
- Kenneth P Birman and Thomas A Joseph. Reliable communication in the presence of failures. ACM Transactions on Computer Systems (TOCS), 5(1):47--76, 1987. Google ScholarDigital Library
- Hans-Juergen Boehm and Sarita V. Adve. Foundations of the C++ concurrency memory model. In Proc. of the ACM SIGPLAN 2008 Conf. on Programming Language Design and Implementation (PLDI08), Tucson, AZ, USA, June, pages 68--78, 2008. Google ScholarDigital Library
- Sebastian Burckhardt, Alexey Gotsman, Hongseok Yang, and Marek Zawirski. Replicated data types: specification, verification, optimality. In The 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '14, San Diego, CA, USA, January 20-21, 2014, pages 271--284, 2014. Google ScholarDigital Library
- Michael J Fischer, Nancy A Lynch, and Michael S Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), 32(2):374--382, 1985. Google ScholarDigital Library
- Pranav Gambhire and Ajay D Kshemkalyani. Reducing false causality in causal message ordering. In High Performance ComputingHiPC 2000, pages 61--72. Springer, 2000. Google ScholarDigital Library
- Seth Gilbert and Nancy Lynch. Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. ACM SIGACT News, 33(2):51--59, 2002. Google ScholarDigital Library
- Vassos Hadzilacos and Toueg Sam. Reliable Broadcast and Related Problems. In Distributed Systems (S. Mullender Ed.). ACM Press, 1993. Google ScholarDigital Library
- Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems (TOPLAS), 13(1):124--149, 1991. Google ScholarDigital Library
- Maurice Herlihy. Technical perspective - highly concurrent data structures. Communications of the ACM, 52(5):99, 2009. Google ScholarDigital Library
- Maurice P Herlihy and Jeannette M Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS), 12(3):463--492, 1990. Google ScholarDigital Library
- Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558--565, 1978. Google ScholarDigital Library
- Leslie Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. Computers, IEEE Transactions on, 100(9):690--691, 1979. Google ScholarDigital Library
- Richard J Lipton and Jonathan S Sandberg. PRAM: A scalable shared memory. Princeton University, Department of Computer Science, 1988.Google Scholar
- George H Mealy. A method for synthesizing sequential circuits. Bell System Technical Journal, 34(5):1045--1079, 1955.Google ScholarCross Ref
- Jayadev Misra. Axioms for memory access in asynchronous hardware systems. ACM Transactions on Programming Languages and Systems (TOPLAS), 8(1):142--153, 1986. Google ScholarDigital Library
- Matthieu Perrin, Achour Mostéfaoui, and Claude Jard. Update consistency for wait-free concurrent objects. In Proceedings of the 29th IEEE International Parallel and Distributed Processing Symposium. IEEE, 2015. Google ScholarDigital Library
- Michel Raynal, André Schiper, and Sam Toueg. The causal ordering abstraction and a simple way to implement it. Information processing letters, 39(6):343--350, 1991. Google ScholarDigital Library
- Jaroslav Sevcík, Viktor Vafeiadis, Francesco Zappa Nardelli, Suresh Jagannathan, and Peter Sewell. Relaxed-memory concurrency and verified compilation. In Proc. of the 38th ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, POPL 2011, Austin, TX, USA, January, pages 43--54, 2011. Google ScholarDigital Library
- Marc Shapiro, Nuno M. Preguiça, Carlos Baquero, and Marek Zawirski. Conflict-free replicated data types. In Stabilization, Safety, and Security of Distributed Systems - 13th International Symposium, SSS 2011, Grenoble, France, October 10-12, 2011. Proceedings, pages 386--400, 2011. Google ScholarDigital Library
- Chengzheng Sun, Xiaohua Jia, Yanchun Zhang, Yun Yang, and David Chen. Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems. ACM Transactions on Computer-Human Interaction (TOCHI), 5(1):63--108, 1998. Google ScholarDigital Library
- Douglas B Terry, Alan J Demers, Karin Petersen, Mike J Spreitzer, Marvin M Theimer, and Brent B Welch. Session guarantees for weakly consistent replicated data. In Parallel and Distributed Information Systems, 1994., Proceedings of the Third International Conference on, pages 140--149. IEEE, 1994. Google ScholarDigital Library
- Werner Vogels. Eventually consistent. Queue, 6(6):14--19, 2008. Google ScholarDigital Library
Index Terms
- Causal consistency: beyond memory
Recommendations
Bolt-on causal consistency
SIGMOD '13: Proceedings of the 2013 ACM SIGMOD International Conference on Management of DataWe consider the problem of separating consistency-related safety properties from availability and durability in distributed data stores via the application of a "bolt-on" shim layer that upgrades the safety of an underlying general-purpose data store. ...
Causal consistency: beyond memory
PPoPP '16In distributed systems where strong consistency is costly when not impossible, causal consistency provides a valuable abstraction to represent program executions as partial orders. In addition to the sequential program order of each computing entity, ...
Update Consistency for Wait-Free Concurrent Objects
IPDPS '15: Proceedings of the 2015 IEEE International Parallel and Distributed Processing SymposiumIn large scale systems such as the Internet, replicating data is an essential feature in order to provide availability and fault-tolerance. Attila and Welch proved that using strong consistency criteria such as atomicity is costly as each operation may ...
Comments