Abstract
In distributed databases, the CAP theorem establishes that a distributed storage system can only ensure two out of three properties: strong data consistency (i.e., reads returning the most recent writes), availability, or partition tolerance. Modern distributed storage systems prioritize performance and availability over strong consistency and thus offer weaker consistency models such as causal consistency.
This paper explores several variations of causal consistency (CC) that guarantee state convergence among replicas, meaning that all distributed replicas converge towards the same consistent state. We investigate a log-based CC model, a commutativity-based CC model, and a global sequence protocol-based CC model. To facilitate our study of the relationships between these models, we use a common formalism to define them. We then show that the log-based CC model is the weakest, while the commutativity-based CC and the global sequence protocol-based CC models are incomparable. We also provide sufficient conditions for a given application program to be robust against one CC model versus another, meaning that the program has the same behavior when executed over databases implementing the two CC models.
This work is supported in part by the Agence National de Recherche project AdeCoDS (ANR-19-CE25-0007).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
Note that the reliance on one server can create a single point of failure, however, processes can adopt a Byzantine fault tolerance consensus approach to elect new process to play the role of server.
- 2.
We assume that \({t}_1\) is ordered before \({t}_2\) based on some mechanism like timestamps.
References
Abdulla, P.A., Arora, J., Atig, M.F., Krishna, S.N.: Verification of programs under the release-acquire semantics. In: McKinley, K.S., Fisher, K. (eds.) Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2019, Phoenix, AZ, USA, June 22–26, 2019, pp. 1117–1132. ACM (2019). https://doi.org/10.1145/3314221.3314649. https://doi.org/10.1145/3314221.3314649
Beillahi, S.M., Bouajjani, A., Enea, C.: Checking robustness against snapshot isolation. In: Dillig, I., Tasiran, S. (eds.) CAV 2019. LNCS, vol. 11562, pp. 286–304. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25543-5_17
Beillahi, S.M., Bouajjani, A., Enea, C.: Robustness against transactional causal consistency. In: Fokkink, W.J., van Glabbeek, R. (eds.) 30th International Conference on Concurrency Theory, CONCUR 2019, August 27–30, 2019, Amsterdam, the Netherlands. LIPIcs, vol. 140, pp. 30:1–30:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019). https://doi.org/10.4230/LIPIcs.CONCUR.2019.30
Beillahi, S.M., Bouajjani, A., Enea, C.: Checking robustness between weak transactional consistency models. In: ESOP 2021. LNCS, vol. 12648, pp. 87–117. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-72019-3_4
Bernardi, G., Gotsman, A.: Robustness against consistency models with atomic visibility. In: Desharnais, J., Jagadeesan, R. (eds.) 27th International Conference on Concurrency Theory, CONCUR 2016, August 23–26, 2016, Québec City, Canada. LIPIcs, vol. 59, pp. 7:1–7:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016). https://doi.org/10.4230/LIPIcs.CONCUR.2016.7
Bouajjani, A., Enea, C., Guerraoui, R., Hamza, J.: On verifying causal consistency. In: Castagna, G., Gordon, A.D. (eds.) Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL 2017, Paris, France, 18–20 January 2017, pp. 626–638. ACM (2017). https://doi.org/10.1145/3009837.3009888
Brutschy, L., Dimitrov, D.K., Müller, P., Vechev, M.T.: Serializability for eventual consistency: criterion, analysis, and applications. In: Castagna, G., Gordon, A.D. (eds.) Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL 2017, Paris, France, 18–20 January 2017, pp. 458–472. ACM (2017). https://doi.org/10.1145/3009837.3009895
Brutschy, L., Dimitrov, D.K., Müller, P., Vechev, M.T.: Static serializability analysis for causal consistency. In: Foster, J.S., Grossman, D. (eds.) Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2018, Philadelphia, PA, USA, 18–22 June 2018, pp. 90–104. ACM (2018). https://doi.org/10.1145/3192366.3192415
Burckhardt, S.: Principles of eventual consistency. Found. Trends Program. Lang. 1(1-2), 1–150 (2014). https://doi.org/10.1561/2500000011
Burckhardt, S., Gotsman, A., Yang, H., Zawirski, M.: Replicated data types: specification, verification, optimality. In: Jagannathan, S., Sewell, P. (eds.) The 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2014, San Diego, CA, USA, 20–21 January 2014, pp. 271–284. ACM (2014). https://doi.org/10.1145/2535838.2535848
Burckhardt, S., Leijen, D., Protzenko, J., Fähndrich, M.: Global sequence protocol: a robust abstraction for replicated shared state. In: Boyland, J.T. (ed.) 29th European Conference on Object-Oriented Programming, ECOOP 2015, 5–10 July 2015, Prague, Czech Republic. LIPIcs, vol. 37, pp. 568–590. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015). https://doi.org/10.4230/LIPIcs.ECOOP.2015.568
Cerone, A., Bernardi, G., Gotsman, A.: A framework for transactional consistency models with atomic visibility. In: Aceto, L., de Frutos-Escrig, D. (eds.) 26th International Conference on Concurrency Theory, CONCUR 2015, Madrid, Spain, September 1.4, 2015. LIPIcs, vol. 42, pp. 58–71. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015). https://doi.org/10.4230/LIPIcs.CONCUR.2015.58
Cerone, A., Gotsman, A.: Analysing snapshot isolation. J. ACM 65(2), 11:1–11:41 (2018). https://doi.org/10.1145/3152396
Gilbert, S., Lynch, N.A.: Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News 33(2), 51–59 (2002). https://doi.org/10.1145/564585.564601
Houshmand, F., Lesani, M.: Hamsaz: replication coordination analysis and synthesis. Proc. ACM Program. Lang. 3(POPL), 74:1–74:32 (2019). https://doi.org/10.1145/3290387
Kaki, G., Priya, S., Sivaramakrishnan, K.C., Jagannathan, S.: Mergeable replicated data types. Proc. ACM Program. Lang. 3(OOPSLA) 154, 1–154:29 (2019). https://doi.org/10.1145/3360580
Kleppmann, M., Mulligan, D.P., Gomes, V.B.F., Beresford, A.R.: A highly-available move operation for replicated trees. IEEE Trans. Parallel Distributed Syst. 33(7), 1711–1724 (2022). https://doi.org/10.1109/TPDS.2021.3118603
Lahav, O., Boker, U.: Decidable verification under a causally consistent shared memory. In: Donaldson, A.F., Torlak, E. (eds.) Proceedings of the 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI 2020, London, UK, 15–20 June 2020, pp. 211–226. ACM (2020). https://doi.org/10.1145/3385412.3385966
Lahav, O., Margalit, R.: Robustness against release/acquire semantics. In: McKinley, K.S., Fisher, K. (eds.) Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2019, Phoenix, AZ, USA, 22–26 June 2019, pp. 126–141. ACM (2019). https://doi.org/10.1145/3314221.3314604
Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21(7), 558–565 (1978). https://doi.org/10.1145/359545.359563
Li, C., Porto, D., Clement, A., Gehrke, J., Preguiça, N.M., Rodrigues, R.: Making geo-replicated systems fast as possible, consistent when necessary. In: Thekkath, C., Vahdat, A. (eds.) 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012, Hollywood, CA, USA, 8–10 October 2012, pp. 265–278. USENIX Association (2012), https://www.usenix.org/conference/osdi12/technical-sessions/presentation/li
Nagar, K., Jagannathan, S.: Automated detection of serializability violations under weak consistency. In: Schewe, S., Zhang, L. (eds.) 29th International Conference on Concurrency Theory, CONCUR 2018, 4–7 September, 2018, Beijing, China. LIPIcs, vol. 118, pp. 41:1–41:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018). https://doi.org/10.4230/LIPIcs.CONCUR.2018.41
Papadimitriou, C.H.: The serializability of concurrent database updates. J. ACM 26(4), 631–653 (1979). https://doi.org/10.1145/322154.322158
Perrin, M., Mostéfaoui, A., Jard, C.: Causal consistency: beyond memory. In: Asenjo, R., Harris, T. (eds.) Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016, Barcelona, Spain, 12–16 March 2016, pp. 26:1–26:12. ACM (2016). https://doi.org/10.1145/2851141.2851170, https://doi.org/10.1145/2851141.2851170
Preguiça, N.M., Baquero, C., Shapiro, M.: Conflict-free replicated data types (crdts). CoRR abs/1805.06358 (2018). http://arxiv.org/abs/1805.06358
Shapiro, M., Ardekani, M.S., Petri, G.: Consistency in 3d. In: Desharnais, J., Jagadeesan, R. (eds.) 27th International Conference on Concurrency Theory, CONCUR 2016, August 23–26, 2016, Québec City, Canada. LIPIcs, vol. 59, pp. 3:1–3:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016). https://doi.org/10.4230/LIPIcs.CONCUR.2016.3
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Beillahi, S.M., Bouajjani, A., Enea, C. (2023). Comparing Causal Convergence Consistency Models. In: Mohaisen, D., Wies, T. (eds) Networked Systems. NETYS 2023. Lecture Notes in Computer Science, vol 14067. Springer, Cham. https://doi.org/10.1007/978-3-031-37765-5_5
Download citation
DOI: https://doi.org/10.1007/978-3-031-37765-5_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-37764-8
Online ISBN: 978-3-031-37765-5
eBook Packages: Computer ScienceComputer Science (R0)