{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T02:10:06Z","timestamp":1750299006298,"version":"3.41.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"9","license":[{"start":{"date-parts":[[2025,5,7]],"date-time":"2025-05-07T00:00:00Z","timestamp":1746576000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2025,9,30]]},"abstract":"<jats:p>In geo-replicated distributed systems, data is redundantly stored across nodes at different geographical sites, increasing fault tolerance and ensuring low access latency by placing data closer to the end user.<\/jats:p>\n          <jats:p>With data being concurrently updated across sites, replicas should converge to a consistent view of the data, which leads toward adopting fine-tuned consistency models, namely causal consistency (CC). On the one hand, CC respects the causality between operations, resulting in intuitive outcomes for end users and programmers. On the other hand, it avoids the latency penalty of stronger consistency models and bypasses their availability constraints in the presence of network partitions. Furthermore, when coupled with Read-only transactions (ROTs) capable of extracting a unified view of the data, CC avoids the anomalies of weaker consistency models.<\/jats:p>\n          <jats:p>ROTs, however, cause additional coordination overhead compared to non-transactional reads. This overhead is particularly unwelcome considering the prevalence of read operations in real-world applications, and hence the impact of ROTs on the overall performance of read-heavy systems.<\/jats:p>\n          <jats:p>With this in mind, there has been a growing effort to optimize the latency and throughput of causally consistent ROTs and to understand how the design of existing systems impacts their performance.<\/jats:p>\n          <jats:p>In light of these recent developments, the present work surveys the state-of-the-art of causally consistent distributed systems, summarizing and comparing their core characteristics and tradeoffs and examining how their design decisions impact the performance of ROTs. To this end, it first defines some key concepts and presents two impossibility results concerning the properties of ROT algorithms. It then reviews several causally consistent systems with ROT support by identifying their recurring strategies to ensure causality and summarizing each of their designs and properties, stressing their implications on the performance of ROTs. It also surveys two architectural approaches to CC, which present progress toward a standard implementation for causally consistent systems. Finally, it discusses the open challenges identified in the literature.<\/jats:p>","DOI":"10.1145\/3731444","type":"journal-article","created":{"date-parts":[[2025,4,19]],"date-time":"2025-04-19T10:12:06Z","timestamp":1745057526000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Survey on the State of the Art of Causally Consistent Cloud Systems"],"prefix":"10.1145","volume":"57","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8777-1024","authenticated-orcid":false,"given":"Diana","family":"Freitas","sequence":"first","affiliation":[{"name":"University of Porto Faculty of Engineering, Porto, Portugal and Kevel, Durham, United States"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-9467-3236","authenticated-orcid":false,"given":"Paul","family":"deGrandis","sequence":"additional","affiliation":[{"name":"Kevel, Durham United States"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8842-6713","authenticated-orcid":false,"given":"Tiago","family":"Boldt Sousa","sequence":"additional","affiliation":[{"name":"INESC TEC, Porto, Portugal, Kevel, Durham, United States and University of Porto Faculty of Engineering, Porto, Portugal"}]}],"member":"320","published-online":{"date-parts":[[2025,5,7]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","unstructured":"1992. Network Time Protocol (Version 3) Specification Implementation and Analysis. RFC Editor. DOI:10.17487\/RFC1305","DOI":"10.17487\/RFC1305"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2012.33"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01784241"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2016.98"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465361"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465279"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212359"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/1267680.1267685"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.5555\/561724"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","unstructured":"Eric A. Brewer. 2000. Towards robust distributed systems (abstract). In Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing (PODC\u201900). Association for Computing Machinery Portland Oregon USA 7. DOI:10.1145\/343477.343502","DOI":"10.1145\/343477.343502"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2012.37"},{"key":"e_1_3_1_13_2","first-page":"49","volume-title":"Proceedings of the 2013 USENIX Annual Technical Conference","author":"Bronson Nathan","year":"2013","unstructured":"Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry Li, et\u00a0al. 2013. \\(\\lbrace\\) TAO \\(\\rbrace\\) : \\(\\lbrace\\) Facebook\u2019s \\(\\rbrace\\) distributed data store for the social graph. In Proceedings of the 2013 USENIX Annual Technical Conference. 49\u201360."},{"key":"e_1_3_1_14_2","first-page":"152","volume-title":"Proceedings of the PDP","author":"Brzezinski Jerzy","year":"2004","unstructured":"Jerzy Brzezinski, Cezary Sobaniec, and Dariusz Wawrzyniak. 2004. From session causality to causal consistency. In Proceedings of the PDP. 152\u2013158."},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.14778\/3538598.3538616"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/PRDC.2009.55"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236210"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2523616.2523628"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2670979.2670983"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/319702.319704"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3380787.3393676"},{"key":"e_1_3_1_23_2","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/978-3-319-14472-6_2","volume-title":"Proceedings of the Principles of Distributed Systems.","author":"Kulkarni Sandeep S.","year":"2014","unstructured":"Sandeep S. Kulkarni, Murat Demirbas, Deepak Madappa, Bharadwaj Avva, and Marcelo Leone. 2014. Logical physical clocks. In Proceedings of the Principles of Distributed Systems.Marcos K. Aguilera, Leonardo Querzoni, and Marc Shapiro (Eds.), Springer International Publishing, Cham, 17\u201332."},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/138873.138877"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043593"},{"key":"e_1_3_1_27_2","first-page":"313","volume-title":"Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation","author":"Lloyd Wyatt","year":"2013","unstructured":"Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen. 2013. Stronger semantics for low-latency geo-replicated storage. In Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation. USENIX Association, Lombard, IL, 313\u2013328. Retrieved from https:\/\/www.usenix.org\/conference\/nsdi13\/technical-sessions\/presentation\/lloyd"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2602649.2610533"},{"key":"e_1_3_1_29_2","first-page":"135","volume-title":"Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation. USENIX Association","author":"Lu Haonan","year":"2016","unstructured":"Haonan Lu, Christopher Hodsdon, Khiem Ngo, Shuai Mu, and Wyatt Lloyd. 2016. The SNOW theorem and latency-optimal read-only transactions. In Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation. USENIX Association, Savannah, GA, 135\u2013150. Retrieved from https:\/\/www.usenix.org\/conference\/osdi16\/technical-sessions\/presentation\/lu"},{"key":"e_1_3_1_30_2","unstructured":"Haonan Lu Shuai Mu Siddhartha Sen and Wyatt Lloyd. 2022. NCC: Natural concurrency control for strictly serializable datastores by avoiding the timestamp-inversion pitfall (extended version). https:\/\/arxiv.org\/abs\/2305.14270 2023."},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.5555\/3488766.3488785"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","unstructured":"Haonan Lu Kaushik Veeraraghavan Philippe Ajoux Jim Hunt Yee Jiun Song Wendy Tobagus Sanjeev Kumar and Wyatt Lloyd. 2015. Existential consistency: measuring and understanding consistency at Facebook. In Proceedings of the 25th Symposium on Operating Systems Principles (SOSP\u201915) Association for Computing Machinery Monterey California 295\u2013310. DOI:10.1145\/2815400.2815426","DOI":"10.1145\/2815400.2815426"},{"key":"e_1_3_1_33_2","unstructured":"Prince Mahajan Lorenzo Alvisi Mike Dahlin and others. 2011. Consistency availability and convergence. University of Texas at Austin Tech Report 11 (2011) 158."},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.5555\/3154630.3154668"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2903738"},{"key":"e_1_3_1_36_2","doi-asserted-by":"crossref","unstructured":"Douglas Stott Parker Gerald J. Popek Gerard Rudisin Alley Stoughton Bruce J. Walker Evelyn Walton Johanna M. Chow David A. Edwards Stephen Kiser and Charles S. Kline. 1983. Detection of -mutual inconsistency in distributed systems. IEEE Transactions on Software Engineering SE-9 (1983) 240\u2013247. Retrieved from https:\/\/api.semanticscholar.org\/CorpusID:2483222","DOI":"10.1109\/TSE.1983.236733"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/269005.266711"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/2.485846"},{"key":"e_1_3_1_39_2","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1007\/978-3-642-24550-3_29","volume-title":"Proceedings of the Stabilization, Safety, and Security of Distributed Systems.","author":"Shapiro Marc","year":"2011","unstructured":"Marc Shapiro, Nuno Pregui\u00e7a, Carlos Baquero, and Marek Zawirski. 2011. Conflict-free replicated data types. In Proceedings of the Stabilization, Safety, and Security of Distributed Systems.Xavier D\u00e9fago, Franck Petit, and Vincent Villain (Eds.), Springer, Berlin, 386\u2013400."},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2018.00014"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2019.00038"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2020.3026778"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/PDIS.1994.331722"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","unstructured":"Misha Tyulenev Andy Schwerin Asya Kamsky Randolph Tan Alyson Cabral and Jack Mulrow. 2019. Implementation of cluster-wide logical clock and causal consistency in MongoDB. In Proceedings of the 2019 International Conference on Management of Data (SIGMOD\u201919). Association for Computing Machinery Amsterdam Netherlands 636\u2013650. DOI:10.1145\/3299869.3314049","DOI":"10.1145\/3299869.3314049"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2009.02.019"},{"key":"e_1_3_1_46_2","volume-title":"Proceedings of the OSDI","author":"Renesse Robbert Van","year":"2004","unstructured":"Robbert Van Renesse and Fred B. Schneider. 2004. Chain replication for supporting high throughput and availability.. In Proceedings of the OSDI."},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-016-0508-7"},{"key":"e_1_3_1_48_2","volume-title":"Distributed Systems (3.03 ed.)","author":"Steen Maarten Van","year":"2017","unstructured":"Maarten Van Steen and Andrew S. Tanenbaum. 2017. Distributed Systems (3.03 ed.). Maarten van Steen Leiden, The Netherlands."},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/1435417.1435432"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/2814576.2814733"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1109\/QEST.2008.44"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3731444","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3731444","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:57:19Z","timestamp":1750298239000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3731444"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,7]]},"references-count":50,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2025,9,30]]}},"alternative-id":["10.1145\/3731444"],"URL":"https:\/\/doi.org\/10.1145\/3731444","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"type":"print","value":"0360-0300"},{"type":"electronic","value":"1557-7341"}],"subject":[],"published":{"date-parts":[[2025,5,7]]},"assertion":[{"value":"2023-06-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-12","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}