{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T02:15:22Z","timestamp":1775873722027,"version":"3.50.1"},"reference-count":87,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T00:00:00Z","timestamp":1730937600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Funds through the Portuguese funding agency, FCT - Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","award":["UIDB\/50014\/2020"],"award-info":[{"award-number":["UIDB\/50014\/2020"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2025,2,28]]},"abstract":"<jats:p>Conflict-free Replicated Data Types (CRDTs) allow optimistic replication in a principled way. Different replicas can proceed independently, being available even under network partitions and always converging deterministically: Replicas that have received the same updates will have equivalent state, even if received in different orders. After a historical tour of the evolution from sequential data types to CRDTs, we present in detail the two main approaches to CRDTs, operation-based and state-based, including two important variations, the pure operation-based and the delta-state based. Intended for prospective CRDT researchers and designers, this article provides solid coverage of the essential concepts, clarifying some misconceptions that frequently occur, but also presents some novel insights gained from considerable experience in designing both specific CRDTs and approaches to CRDTs.<\/jats:p>","DOI":"10.1145\/3695249","type":"journal-article","created":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T11:01:46Z","timestamp":1725879706000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Approaches to Conflict-free Replicated Data Types"],"prefix":"10.1145","volume":"57","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7000-0485","authenticated-orcid":false,"given":"Paulo S\u00e9rgio","family":"Almeida","sequence":"first","affiliation":[{"name":"Universidade do Minho, Braga, Portugal and INESC TEC, Porto, Portugal"}]}],"member":"320","published-online":{"date-parts":[[2024,11,7]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"2013. AntidoteDB: A planet scale highly available transactional database built on CRDT technology. Retrieved from https:\/\/github.com\/AntidoteDB\/antidote"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01784241"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-017-0322-2"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2017.08.003"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933090"},{"key":"e_1_3_2_7_2","article-title":"Composition in state-based replicated data types","volume":"123","author":"Baquero Carlos","year":"2017","unstructured":"Carlos Baquero, Paulo S\u00e9rgio Almeida, Alcino Cunha, and Carla Ferreira. 2017. Composition in state-based replicated data types. Bull. EATCS 123 (2017). Retrieved from http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/507","journal-title":"Bull. EATCS"},{"key":"e_1_3_2_8_2","volume-title":"Proceedings of the 14th IFIP WG 6.1 International Conference on Distributed Applications and Interoperable Systems (DAIS\u201914)","author":"Baquero Carlos","unstructured":"Carlos Baquero, Paulo S\u00e9rgio Almeida, and Ali Shoker. Making operation-based CRDTs operation-based. In Proceedings of the 14th IFIP WG 6.1 International Conference on Distributed Applications and Interoperable Systems (DAIS\u201914), Kostas Magoutis and Peter R. Pietzuch (Eds.)."},{"key":"e_1_3_2_9_2","unstructured":"Carlos Baquero Paulo S\u00e9rgio Almeida and Ali Shoker. 2017. Pure operation-based replicated data types. Retrieved from http:\/\/arxiv.org\/abs\/1710.04469"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","unstructured":"Michael A. Bender Alex Conway Mart\u00edn Farach-Colton William Kuszmaul and Guido Tagliavini. 2023. Iceberg hashing: Optimizing many hash-table criteria at once. J. ACM 70 6 (November 2023). DOI:10.1145\/3625817","DOI":"10.1145\/3625817"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33651-5_48"},{"key":"e_1_3_2_12_2","unstructured":"Annette Bieniusa Marek Zawirski Nuno M. Pregui\u00e7a Marc Shapiro Carlos Baquero Valter Balegas and S\u00e9rgio Duarte. 2012. An optimized conflict-free replicated set. Retrieved from http:\/\/arxiv.org\/abs\/1210.3368"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","unstructured":"Garrett Birkhoff. 1937. Rings of sets. Duke Mathematical Journal 3 3 (1937) 443\u2013454. DOI:10.1215\/S0012-7094-37-00334-X","DOI":"10.1215\/S0012-7094-37-00334-X"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1090\/coll\/025"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/7351.7478"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/128738.128742"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064210"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/343477.343502"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2596631.2596633"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1561\/2500000011"},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","unstructured":"Sebastian Burckhardt Alexey Gotsman and Hongseok Yang. 2013. Understanding Eventual Consistency. Microsoft Research. Retrieved from https:\/\/www.microsoft.com\/en-us\/research\/publication\/understanding-eventual-consistency\/","DOI":"10.1561\/9781601988591"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535848"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/6041.6042"},{"key":"e_1_3_2_24_2","first-page":"173","volume-title":"Proceedings of the 3rd USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201999)","author":"Castro Miguel","year":"1999","unstructured":"Miguel Castro and Barbara Liskov. 1999. Practical byzantine fault tolerance. In Proceedings of the 3rd USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201999), Margo I. Seltzer and Paul J. Leach (Eds.). USENIX Association, 173\u2013186. Retrieved from https:\/\/dl.acm.org\/citation.cfm?id=296824"},{"key":"e_1_3_2_25_2","unstructured":"Automerge contributors. 2019. Automerge: A JSON-like data structure (a CRDT) that can be modified concurrently by different users and merged again automatically. Retrieved from https:\/\/github.com\/automerge\/automerge"},{"key":"e_1_3_2_26_2","first-page":"557","volume-title":"Proceedings of the 24th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA\u201909)","author":"Cook William R.","year":"2009","unstructured":"William R. Cook. 2009. On understanding data abstraction, revisited. In Proceedings of the 24th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA\u201909), Shail Arora and Gary T. Leavens (Eds.). ACM, 557\u2013572. DOI:DOI:10.1145\/1640089.1640133"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/365813.365819"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294281"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/41840.41841"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/361179.361202"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66963"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3166089.3168733"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00022"},{"key":"e_1_3_2_34_2","first-page":"4:1\u20134:3","volume-title":"Proceedings of the 3rd International Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC@EuroSys\u201917)","author":"Enes Vitor","year":"2017","unstructured":"Vitor Enes, Carlos Baquero, Paulo S\u00e9rgio Almeida, and Jo\u00e3o Leit\u00e3o. 2017. Borrowing an identity for a distributed counter: Work in progress report. In Proceedings of the 3rd International Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC@EuroSys\u201917), Annette Bieniusa and Alexey Gotsman (Eds.). ACM, 4:1\u20134:3. DOI:DOI:10.1145\/3064889.3064894"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/564585.564601"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.5555\/167487"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/1832772.1832777"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/S12083-022-01404-6"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.5555\/540365"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_3_2_42_2","unstructured":"High Scalability. 2014. How League of Legends Scaled Chat to 70 million Players. Retrieved from https:\/\/highscalability.com\/how-league-of-legends-scaled-chat-to-70-million-players-it-t"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/363235.363259"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289507"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/355620.361161"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-010-0068-0_15"},{"key":"e_1_3_2_47_2","unstructured":"Kevin Jahns. 2023. Yjs: Shared data types for building collaborative software. Retrieved from https:\/\/github.com\/yjs\/yjs"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3301419.3323972"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3359591.3359737"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/1900160.1900176"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/138873.138877"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/361082.361093"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_3_2_54_2","volume-title":"Crash Recovery in a Distributed Data Storage System","author":"Lampson Butler W.","year":"1979","unstructured":"Butler W. Lampson and Howard E. Sturgis. 1979. Crash Recovery in a Distributed Data Storage System. Technical Report. Xerox Palo Alto Research Center."},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/1031607.1031683"},{"key":"e_1_3_2_56_2","unstructured":"Lightbend. 2015. Concurrent sharing of \u201cdata in motion\u201d across clusters with CRDTs in Akka Distributed Data. Retrieved from https:\/\/www.lightbend.com\/blog\/concurrent-sharing-of-data-in-motion-across-clusters-with-crdts-in-akka-distributed-data"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/800233.807045"},{"key":"e_1_3_2_58_2","volume-title":"Consistency, Availability, and Convergence","author":"Mahajan Prince","year":"2011","unstructured":"Prince Mahajan, Lorenzo Alvisi, and Mike Dahlin. 2011. Consistency, Availability, and Convergence. Technical Report UTCS TR-11-22. Department of Computer Science, The University of Texas at Austin."},{"key":"e_1_3_2_59_2","unstructured":"Juliane Marubayashi and Carlos Baquero. 2023. Making Causal Based CRDTs Scalable. Retrieved from https:\/\/inforum2023-ylfd.vercel.app\/Atas\/paper_366\/366-CM.pdf"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/2505305.2505309"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/2494266.2494278"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/215585.215706"},{"key":"e_1_3_2_63_2","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1145\/2957276.2957310","volume-title":"Proceedings of the 19th International Conference on Supporting Group Work","author":"Nicolaescu Petru","year":"2016","unstructured":"Petru Nicolaescu, Kevin Jahns, Michael Derntl, and Ralf Klamma. 2016. Near real-time peer-to-peer shared editing on extensible data types. In Proceedings of the 19th International Conference on Supporting Group Work, Stephan G. Lukosch, Aleksandra Sarcevic, Myriam Lewkowicz, and Michael J. Muller (Eds.). ACM, 39\u201349. DOI:DOI:10.1145\/2957276.2957310"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/960118.808391"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1109\/COLCOM.2006.361867"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/1180875.1180916"},{"key":"e_1_3_2_67_2","unstructured":"Michael Owen. 2015. Using Erlang Riak and the ORSWOT CRDT at bet365 for Scalability and Performance. Retrieved from https:\/\/www.erlang-factory.com\/euc2015\/michael-owen"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1983.236733"},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322188"},{"key":"e_1_3_2_70_2","unstructured":"Nuno M. Pregui\u00e7a Carlos Baquero Paulo S\u00e9rgio Almeida Victor Fonte and Ricardo Gon\u00e7alves. 2010. Dotted version vectors: Logical clocks for optimistic replication. Retrieved from http:\/\/arxiv.org\/abs\/1011.5808"},{"key":"e_1_3_2_71_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2009.20"},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.1109\/SRDSW.2014.33"},{"key":"e_1_3_2_73_2","unstructured":"Redis. 2022. Diving into Conflict-Free Replicated Data Types (CRDTs). Retrieved from https:\/\/redis.io\/blog\/diving-into-crdts"},{"key":"e_1_3_2_74_2","doi-asserted-by":"publisher","DOI":"10.1145\/240080.240305"},{"key":"e_1_3_2_75_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2010.12.006"},{"key":"e_1_3_2_76_2","doi-asserted-by":"publisher","DOI":"10.1145\/800265.810743"},{"key":"e_1_3_2_77_2","doi-asserted-by":"publisher","DOI":"10.1145\/1057977.1057980"},{"key":"e_1_3_2_78_2","first-page":"50","volume-title":"A Comprehensive Study of Convergent and Commutative Replicated Data Types","author":"Shapiro Marc","year":"2011","unstructured":"Marc Shapiro, Nuno Pregui\u00e7a, Carlos Baquero, and Marek Zawirski. 2011. A Comprehensive Study of Convergent and Commutative Replicated Data Types. Research Report RR-7506. Inria \u2013 Centre Paris-Rocquencourt; INRIA. 50 pages. Retrieved from https:\/\/inria.hal.science\/inria-00555588"},{"key":"e_1_3_2_79_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24550-3_29"},{"key":"e_1_3_2_80_2","unstructured":"SoundCloud. 2014. Roshi: A large-scale CRDT set implementation for timestamped events. Retrieved from https:\/\/github.com\/soundcloud\/roshi"},{"key":"e_1_3_2_81_2","doi-asserted-by":"publisher","DOI":"10.1109\/PDIS.1994.331722"},{"key":"e_1_3_2_82_2","doi-asserted-by":"publisher","DOI":"10.1145\/224056.224070"},{"key":"e_1_3_2_83_2","doi-asserted-by":"publisher","DOI":"10.1145\/2926965"},{"key":"e_1_3_2_84_2","doi-asserted-by":"publisher","DOI":"10.1145\/1435417.1435432"},{"key":"e_1_3_2_85_2","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1145\/3517209.3524084","volume-title":"Proceedings of the 9th Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC@EuroSys\u201922","author":"Weidner Matthew","year":"2022","unstructured":"Matthew Weidner and Paulo S\u00e9rgio Almeida. 2022. An oblivious observed-reset embeddable replicated counter. In Proceedings of the 9th Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC@EuroSys\u201922, Adriana Szekeres and K. C. Sivaramakrishnan (Eds.). ACM, 47\u201352. DOI:DOI:10.1145\/3517209.3524084"},{"key":"e_1_3_2_86_2","doi-asserted-by":"publisher","unstructured":"Matthew Weidner and Martin Kleppmann. 2023. The art of the fugue: Minimizing interleaving in collaborative text editing. DOI:DOI:10.48550\/ARXIV.2305.00583","DOI":"10.48550\/ARXIV.2305.00583"},{"key":"e_1_3_2_87_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2009.75"},{"key":"e_1_3_2_88_2","doi-asserted-by":"publisher","DOI":"10.1145\/365696.365702"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695249","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3695249","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:58:11Z","timestamp":1750294691000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695249"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,7]]},"references-count":87,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,2,28]]}},"alternative-id":["10.1145\/3695249"],"URL":"https:\/\/doi.org\/10.1145\/3695249","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"value":"0360-0300","type":"print"},{"value":"1557-7341","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,7]]},"assertion":[{"value":"2023-10-27","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-02","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}