{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T21:15:44Z","timestamp":1773868544539,"version":"3.50.1"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T00:00:00Z","timestamp":1634256000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","award":["UIDB\/04516\/2020,PTDC\/CCI-INF\/32081\/2017,LISBOA-01-0145-FEDER-032662\/PTDC\/CCI-INF\/32662\/2017"],"award-info":[{"award-number":["UIDB\/04516\/2020,PTDC\/CCI-INF\/32081\/2017,LISBOA-01-0145-FEDER-032662\/PTDC\/CCI-INF\/32662\/2017"]}]},{"DOI":"10.13039\/501100003130","name":"Fonds Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["1S98519N"],"award-info":[{"award-number":["1S98519N"]}],"id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2021,10,20]]},"abstract":"<jats:p>To ease the development of geo-distributed applications, replicated data types (RDTs) offer a familiar programming interface while ensuring state convergence, low latency, and high availability. However, RDTs are still designed exclusively by experts using ad-hoc solutions that are error-prone and result in brittle systems. Recent works statically detect conflicting operations on existing data types and coordinate those at runtime to guarantee convergence and preserve application invariants. However, these approaches are too conservative, imposing coordination on a large number of operations. In this work, we propose a principled approach to design and implement efficient RDTs taking into account application invariants. Developers extend sequential data types with a distributed specification, which together form an RDT. We statically analyze the specification to detect conflicts and unravel their cause. This information is then used at runtime to serialize concurrent operations safely and efficiently. Our approach derives a correct RDT from any sequential data type without changes to the data type's implementation and with minimal coordination. We implement our approach in Scala and develop an extensive portfolio of RDTs. The evaluation shows that our approach provides performance similar to conflict-free replicated data types for commutative operations, and considerably improves the performance of non-commutative operations, compared to existing solutions.<\/jats:p>","DOI":"10.1145\/3485484","type":"journal-article","created":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T19:18:28Z","timestamp":1634325508000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["ECROs: building global scale systems from sequential code"],"prefix":"10.1145","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5469-1001","authenticated-orcid":false,"given":"Kevin","family":"De Porre","sequence":"first","affiliation":[{"name":"Vrije Universiteit Brussel, Belgium"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3680-7634","authenticated-orcid":false,"given":"Carla","family":"Ferreira","sequence":"additional","affiliation":[{"name":"NOVA School of Science and Technology, Portugal"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1513-1527","authenticated-orcid":false,"given":"Nuno","family":"Pregui\u00e7a","sequence":"additional","affiliation":[{"name":"NOVA School of Science and Technology, Portugal"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9966-6421","authenticated-orcid":false,"given":"Elisa","family":"Gonzalez Boix","sequence":"additional","affiliation":[{"name":"Vrije Universiteit Brussel, Belgium"}]}],"member":"320","published-online":{"date-parts":[[2021,10,15]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26850-7_5"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735508.2735509"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3297753.3297760"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741972"},{"key":"e_1_2_2_5_1","volume-title":"Pure Operation-Based Replicated Data Types. CoRR, abs\/1710.04469","author":"Baquero Carlos","year":"2017","unstructured":"Carlos Baquero , Paulo S. Almeida , and Ali Shoker . 2017. Pure Operation-Based Replicated Data Types. CoRR, abs\/1710.04469 ( 2017 ), arxiv:1710.04469. Carlos Baquero, Paulo S. Almeida, and Ali Shoker. 2017. Pure Operation-Based Replicated Data Types. CoRR, abs\/1710.04469 (2017), arxiv:1710.04469."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2012.37"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/343477.343502"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31057-7_14"},{"key":"e_1_2_2_9_1","unstructured":"Emmanuel Cecchet and Julie Marguerite. 2009. RUBiS: Rice University Bidding System. http:\/\/rubis.ow2.org\/  Emmanuel Cecchet and Julie Marguerite. 2009. RUBiS: Rice University Bidding System. http:\/\/rubis.ow2.org\/"},{"key":"e_1_2_2_10_1","unstructured":"Kevin De Porre Carla Ferreira Nuno Pregui\u00e7a and Elisa Gonzalez Boix. 2021. ECROs: Building Global Scale Systems from Sequential Code (Appendix). http:\/\/soft.vub.ac.be\/Publications\/2021\/vub-tr-soft-21-09-appendix.pdf  Kevin De Porre Carla Ferreira Nuno Pregui\u00e7a and Elisa Gonzalez Boix. 2021. ECROs: Building Global Scale Systems from Sequential Code (Appendix). http:\/\/soft.vub.ac.be\/Publications\/2021\/vub-tr-soft-21-09-appendix.pdf"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3358502.3361271"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-22496-7_3"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2020.05.010"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594322"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837625"},{"key":"e_1_2_2_16_1","volume-title":"Incremental Consistency Guarantees for Replicated Objects. In 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016","author":"Guerraoui Rachid","year":"2016","unstructured":"Rachid Guerraoui , Matej Pavlovic , and Dragos-Adrian Seredinschi . 2016 . Incremental Consistency Guarantees for Replicated Objects. In 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016 , Savannah, GA, USA , November 2-4, 2016. USENIX Association, 169\u2013184. isbn:978-1-931971-33-1 https:\/\/www.usenix.org\/conference\/osdi16\/technical-sessions\/presentation\/guerraoui Rachid Guerraoui, Matej Pavlovic, and Dragos-Adrian Seredinschi. 2016. Incremental Consistency Guarantees for Replicated Objects. In 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016, Savannah, GA, USA, November 2-4, 2016. USENIX Association, 169\u2013184. isbn:978-1-931971-33-1 https:\/\/www.usenix.org\/conference\/osdi16\/technical-sessions\/presentation\/guerraoui"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2987550.2987559"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290387"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276534"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360580"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/383962.384020"},{"key":"e_1_2_2_22_1","volume-title":"A Critique of the CAP Theorem. ArXiv, abs\/1509.05393","author":"Kleppmann Martin","year":"2015","unstructured":"Martin Kleppmann . 2015. A Critique of the CAP Theorem. ArXiv, abs\/1509.05393 ( 2015 ). Martin Kleppmann. 2015. A Critique of the CAP Theorem. ArXiv, abs\/1509.05393 (2015)."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2697382"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428256"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993562"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_2_2_27_1","volume-title":"Automating the Choice of Consistency Levels in Replicated Systems. In 2014 USENIX Annual Technical Conference, USENIX ATC \u201914","author":"Li Cheng","year":"2014","unstructured":"Cheng Li , Jo\u00e3o Leit\u00e3o , Allen Clement , Nuno M. Pregui\u00e7a , Rodrigo Rodrigues , and Viktor Vafeiadis . 2014 . Automating the Choice of Consistency Levels in Replicated Systems. In 2014 USENIX Annual Technical Conference, USENIX ATC \u201914 , Philadelphia, PA, USA , June 19-20, 2014. USENIX Association, 281\u2013292. isbn:978-1-931971-10-2 https:\/\/www.usenix.org\/conference\/atc14\/technical-sessions\/presentation\/li_cheng_2 Cheng Li, Jo\u00e3o Leit\u00e3o, Allen Clement, Nuno M. Pregui\u00e7a, Rodrigo Rodrigues, and Viktor Vafeiadis. 2014. Automating the Choice of Consistency Levels in Replicated Systems. In 2014 USENIX Annual Technical Conference, USENIX ATC \u201914, Philadelphia, PA, USA, June 19-20, 2014. USENIX Association, 281\u2013292. isbn:978-1-931971-10-2 https:\/\/www.usenix.org\/conference\/atc14\/technical-sessions\/presentation\/li_cheng_2"},{"key":"e_1_2_2_28_1","volume-title":"10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012","author":"Li Cheng","year":"2012","unstructured":"Cheng Li , Daniel Porto , Allen Clement , Johannes Gehrke , Nuno M. Pregui\u00e7a , and Rodrigo Rodrigues . 2012 . Making Geo-Replicated Systems Fast as Possible, Consistent when Necessary . In 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012 , Hollywood, CA, USA , October 8-10, 2012. USENIX Association, 265\u2013278. isbn:978-1-931971-96-6 https:\/\/www.usenix.org\/conference\/osdi12\/technical-sessions\/presentation\/li Cheng Li, Daniel Porto, Allen Clement, Johannes Gehrke, Nuno M. Pregui\u00e7a, and Rodrigo Rodrigues. 2012. Making Geo-Replicated Systems Fast as Possible, Consistent when Necessary. In 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012, Hollywood, CA, USA, October 8-10, 2012. USENIX Association, 265\u2013278. isbn:978-1-931971-96-6 https:\/\/www.usenix.org\/conference\/osdi12\/technical-sessions\/presentation\/li"},{"key":"e_1_2_2_29_1","volume-title":"2018 USENIX Annual Technical Conference, USENIX ATC 2018","author":"Li Cheng","year":"2018","unstructured":"Cheng Li , Nuno M. Pregui\u00e7a , and Rodrigo Rodrigues . 2018 . Fine-grained consistency for geo-replicated systems . In 2018 USENIX Annual Technical Conference, USENIX ATC 2018 , Boston, MA, USA , July 11-13, 2018. USENIX Association, 359\u2013372. https:\/\/www.usenix.org\/conference\/atc18\/presentation\/li-cheng Cheng Li, Nuno M. Pregui\u00e7a, and Rodrigo Rodrigues. 2018. Fine-grained consistency for geo-replicated systems. In 2018 USENIX Annual Technical Conference, USENIX ATC 2018, Boston, MA, USA, July 11-13, 2018. USENIX Association, 359\u2013372. https:\/\/www.usenix.org\/conference\/atc18\/presentation\/li-cheng"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-53288-8_16"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2790449.2790525"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192375"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SNAPL.2019.11"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276954.3276957"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-44914-8_20"},{"key":"e_1_2_2_36_1","unstructured":"OpenJDK. [n. d.]. JMH - OpenJDK. https:\/\/openjdk.java.net\/projects\/code-tools\/jmh\/ Accessed: 13-05-2020.  OpenJDK. [n. d.]. JMH - OpenJDK. https:\/\/openjdk.java.net\/projects\/code-tools\/jmh\/ Accessed: 13-05-2020."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1187436.1210590"},{"key":"e_1_2_2_38_1","unstructured":"Julien Ponge. July 2014. Avoiding Benchmarking Pitfalls on the JVM. https:\/\/www.oracle.com\/technical-resources\/articles\/java\/architect-benchmarking.html Accessed: 13-05-2020.  Julien Ponge. July 2014. Avoiding Benchmarking Pitfalls on the JVM. https:\/\/www.oracle.com\/technical-resources\/articles\/java\/architect-benchmarking.html Accessed: 13-05-2020."},{"key":"e_1_2_2_39_1","volume-title":"A comprehensive study of Convergent and Commutative Replicated Data Types. Inria \u2013 Centre Paris-Rocquencourt","author":"Shapiro Marc","unstructured":"Marc Shapiro , Nuno Pregui\u00e7a , Carlos Baquero , and Marek Zawirski . 2011. A comprehensive study of Convergent and Commutative Replicated Data Types. Inria \u2013 Centre Paris-Rocquencourt ; INRIA , 50. Marc Shapiro, Nuno Pregui\u00e7a, Carlos Baquero, and Marek Zawirski. 2011. A comprehensive study of Convergent and Commutative Replicated Data Types. Inria \u2013 Centre Paris-Rocquencourt ; INRIA, 50."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24550-3_29"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2737981"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3358499.3361222"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/224056.224070"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1435417.1435432"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314617"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3408976"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2957319.2957377"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3281366.3281372"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jlamp.2020.100561"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485484","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485484","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:39Z","timestamp":1750191519000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485484"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,15]]},"references-count":49,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2021,10,20]]}},"alternative-id":["10.1145\/3485484"],"URL":"https:\/\/doi.org\/10.1145\/3485484","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,15]]},"assertion":[{"value":"2021-10-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}