{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:11:09Z","timestamp":1779174669648,"version":"3.51.4"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,10]]},"abstract":"<jats:p>Conflict-free replicated data types (CRDTs) are highly available and performant data replication solutions for distributed applications. However, their eventual consistency guarantees are often insufficient for ensuring application correctness, especially in the presence of Byzantine failures. Naively applying traditional consensus and Byzantine fault tolerance (BFT) protocols to CRDT updates for stronger guarantees, while intuitive, negates the performance benefits of CRDTs.<\/jats:p>\n          <jats:p>\n            We introduce a novel programming model called\n            <jats:italic>reliable CRDTs<\/jats:italic>\n            that expands CRDTs with additional guarantees: users can query strongly or eventually consistent values, enforce a total order among selected operations, and define data-type level invariants while remaining operational in the presence of Byzantine failures. Reliable CRDTs enable the use of CRDTs in scenarios where strong consistency is needed while maintaining their performance advantages.\n          <\/jats:p>\n          <jats:p>\n            We present an implementation of reliable CRDTs named\n            <jats:italic>Janus.<\/jats:italic>\n            It enhances CRDTs with the aforementioned features by functioning as a middleware that facilitates CRDT communication and asynchronously runs a BFT consensus protocol. Our evaluation demonstrates that\n            <jats:italic>Janus<\/jats:italic>\n            achieves 21\u00d7 higher throughput than naively applying state-of-the-art BFT protocols such as HotStuff achieves, and it remains responsive even under heavy loads.\n          <\/jats:p>","DOI":"10.14778\/3705829.3705850","type":"journal-article","created":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T23:21:06Z","timestamp":1740784866000},"page":"349-362","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Making CRDTs Not So Eventual"],"prefix":"10.14778","volume":"18","author":[{"given":"Yunhao","family":"Mao","sequence":"first","affiliation":[{"name":"University of Toronto"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gengrui","family":"Zhang","sequence":"additional","affiliation":[{"name":"Concordia University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zongxin","family":"Liu","sequence":"additional","affiliation":[{"name":"University of Toronto"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pezhman","family":"Nasirifard","sequence":"additional","affiliation":[{"name":"Technical University of Munich"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sofia","family":"Tijanic","sequence":"additional","affiliation":[{"name":"University of Toronto"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hans-Arno","family":"Jacobsen","sequence":"additional","affiliation":[{"name":"University of Toronto"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,28]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Retrieved","year":"2024","unstructured":"2022. Antidote: A planet scale, highly available, transactional database built on CRDT technology. Retrieved August, 2024 from https:\/\/github.com\/AntidoteDB\/antidote"},{"key":"e_1_2_1_2_1","unstructured":"2023. MergeSharp. Retrieved August 2024 from https:\/\/github.com\/yunhaom94\/MergeSharp"},{"key":"e_1_2_1_3_1","unstructured":"2024. Sui. Retrieved August 2024 from https:\/\/github.com\/MystenLabs\/sui\/"},{"key":"e_1_2_1_4_1","volume-title":"Mohammad Hossein Moattar, and Mostafa Razavi Ghods","author":"Sharif Aldin Hesam Nejati","year":"2019","unstructured":"Hesam Nejati Sharif Aldin, Hossein Deldari, Mohammad Hossein Moattar, and Mostafa Razavi Ghods. 2019. Consistency models in distributed systems: A survey on definitions, disciplines, challenges and applications. (2019). arXiv:1902.03305 [cs.DC] https:\/\/arxiv.org\/abs\/1902.03305"},{"key":"e_1_2_1_5_1","volume-title":"International Conference on Networked Systems (NETYS","author":"Almeida Paulo S\u00e9rgio","year":"2015","unstructured":"Paulo S\u00e9rgio Almeida, Ali Shoker, and Carlos Baquero. 2015. Efficient state-based crdts by delta-mutation. In International Conference on Networked Systems (NETYS 2015). Springer, 62--76."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3190508.3190538"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735508.2735509"},{"key":"e_1_2_1_8_1","first-page":"5","article-title":"Eventual Consistency Today","volume":"56","author":"Bailis Peter","year":"2013","unstructured":"Peter Bailis and Ali Ghodsi. 2013. Eventual Consistency Today: Limitations, Extensions, and Beyond. Commun. ACM 56, 5 (May 2013), 55--63.","journal-title":"Limitations, Extensions, and Beyond. Commun. ACM"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465279"},{"key":"e_1_2_1_11_1","volume-title":"Extending Eventually Consistent Cloud Databases for Enforcing Numeric Invariants. In 34th Symposium on Reliable Distributed Systems (SRDS '15)","author":"Balegas Valter","year":"2015","unstructured":"Valter Balegas, Diogo Serra, S\u00e9rgio Duarte, Carla Ferreira, Marc Shapiro, Rodrigo Rodrigues, and Nuno Pregui\u00e7a. 2015. Extending Eventually Consistent Cloud Databases for Enforcing Numeric Invariants. In 34th Symposium on Reliable Distributed Systems (SRDS '15). IEEE, 31--36."},{"key":"e_1_2_1_12_1","volume-title":"Secure Conflict-Free Replicated Data Types. In International Conference on Distributed Computing and Networking 2021","author":"Barbosa Manuel","year":"2021","unstructured":"Manuel Barbosa, Bernardo Ferreira, Jo\u00e3o Marques, Bernardo Portela, and Nuno Pregui\u00e7a. 2021. Secure Conflict-Free Replicated Data Types. In International Conference on Distributed Computing and Networking 2021 (Nara, Japan) (ICDCN '21). ACM, 6--15."},{"key":"e_1_2_1_13_1","volume-title":"Concurrency Control and Recovery in Database Systems","author":"Bernstein Philip A.","unstructured":"Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman. 1987. Concurrency Control and Recovery in Database Systems. Addison-Wesley."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2012.37"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Lucas Brutschy Dimitar Dimitrov Peter M\u00fcller and Martin Vechev. 2017. Serializability for Eventual Consistency: Criterion Analysis and Applications (POPL '17). ACM 458--472.","DOI":"10.1145\/3009837.3009895"},{"key":"e_1_2_1_16_1","volume-title":"Introduction to cryptography","author":"Buchmann Johannes","unstructured":"Johannes Buchmann. 2004. Introduction to cryptography. Springer."},{"key":"e_1_2_1_17_1","volume-title":"Advances in Cryptology --- CRYPTO","author":"Cachin Christian","year":"2001","unstructured":"Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. 2001. Secure and Efficient Asynchronous Broadcast Protocols. In Advances in Cryptology --- CRYPTO 2001, Joe Kilian (Ed.). Springer Berlin Heidelberg, 524--541."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing","author":"Cachin Christian","year":"2000","unstructured":"Christian Cachin, Klaus Kursawe, and Victor Shoup. 2000. Random Oracles in Constantipole: Practical Asynchronous Byzantine Agreement Using Cryptography (Extended Abstract). In Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing (Portland, Oregon, USA) (PODC '00). ACM, 123--132."},{"key":"e_1_2_1_19_1","volume-title":"Distributed Systems: Concepts and Design","author":"Coulouris George","year":"2011","unstructured":"George Coulouris, Jean Dollimore, Tim Kindberg, and Gordon Blair. 2011. Distributed Systems: Concepts and Design (5th ed.). Addison-Wesley Publishing Company.","edition":"5"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3492321.3519594"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 1st ACM Conference on Advances in Financial Technologies","author":"G\u0105gol Adam","year":"2019","unstructured":"Adam G\u0105gol, Damian Le\u015bniak, Damian Straszak, and Micha\u0142 undefinedwiundefinedtek. 2019. Aleph: Efficient Atomic Broadcast in Asynchronous Networks with Byzantine Nodes. In Proceedings of the 1st ACM Conference on Advances in Financial Technologies (Zurich, Switzerland) (AFT '19). ACM, 214--228."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 3rd International Workshop on Distributed Infrastructure for the Common Good (Quebec","author":"Jannes Kristof","year":"2022","unstructured":"Kristof Jannes, Bert Lagaisse, and Wouter Joosen. 2022. Secure replication for client-centric data stores. In Proceedings of the 3rd International Workshop on Distributed Infrastructure for the Common Good (Quebec, Quebec City, Canada) (DICG '22). ACM, 31--36."},{"key":"e_1_2_1_23_1","volume-title":"Vegvisir: A Partition-Tolerant Blockchain for the Internet-of-Things. In 38th International Conference on Distributed Computing Systems","author":"Karlsson Kolbeinn","year":"2018","unstructured":"Kolbeinn Karlsson, Weitao Jiang, Stephen Wicker, Danny Adams, Edwin Ma, Robbert van Renesse, and Hakim Weatherspoon. 2018. Vegvisir: A Partition-Tolerant Blockchain for the Internet-of-Things. In 38th International Conference on Distributed Computing Systems (Vienna, Austria) (ICDCS 2018). IEEE, 1150--1158."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465084.3467905"},{"key":"e_1_2_1_25_1","unstructured":"Martin Kleppmann. 2016. Designing Data-Intensive Applications: The Big Ideas Behind Reliable Scalable and Maintainable Systems. O'Reilly."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517209.3524042"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687657"},{"key":"e_1_2_1_28_1","unstructured":"Leslie Lamport. 2019. Time clocks and the ordering of events in a distributed system. ACM 179--196."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Leslie Lamport Robert Shostak and Marshall Pease. 1982. The Byzantine Generals Problem. ACM 203--226.","DOI":"10.1145\/357172.357176"},{"key":"e_1_2_1_30_1","volume-title":"10th USENIX Symposium on Operating Systems Design and Implementation","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 (Hollywood, CA, USA) (OSDI '12). USENIX Association, 265--278."},{"key":"e_1_2_1_31_1","volume-title":"Stronger Semantics for Low-Latency Geo-Replicated Storage. In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI '13)","author":"Lloyd Wyatt","unstructured":"Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen. 2013. Stronger Semantics for Low-Latency Geo-Replicated Storage. In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI '13). USENIX Association, 313--328."},{"key":"e_1_2_1_32_1","unstructured":"Pedro Lopes Jo\u00e3o Sousa Valter Balegas Carla Ferreira S\u00e9gio Duarte Annette Bieniusa Rodrigo Rodrigues and Nuno Pregui\u00e7a. 2019. Antidote SQL: Relaxed When Possible Strict When Necessary. arXiv:1902.03576 [cs.DB] https:\/\/arxiv.org\/abs\/1902.03576"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 23rd Conference on 23rd ACM\/IFIP International Middleware Conference (Quebec, QC, Canada) (Middleware '22)","author":"Mao Yunhao","year":"2022","unstructured":"Yunhao Mao, Zongxin Liu, and Hans-Arno Jacobsen. 2022. Reversible Conflict-Free Replicated Data Types. In Proceedings of the 23rd Conference on 23rd ACM\/IFIP International Middleware Conference (Quebec, QC, Canada) (Middleware '22). ACM, 295--307."},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Pezhman Nasirifard Ruben Mayer and Hans-Arno Jacobsen. 2019. FabricCRDT: A Conflict-Free Replicated Datatypes Approach to Permissioned Blockchains (Middleware '19). ACM 110--122.","DOI":"10.1145\/3361525.3361540"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 24th International Middleware Conference","author":"Nasirifard Pezhman","year":"2023","unstructured":"Pezhman Nasirifard, Ruben Mayer, and Hans-Arno Jacobsen. 2023. Orderless-Chain: A CRDT-based BFT Coordination-free Blockchain Without Global Order of Transactions. In Proceedings of the 24th International Middleware Conference (Bologna, Italy) (Middleware '23). ACM, 137--150."},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Nuno Pregui\u00e7a. 2018. Conflict-free Replicated Data Types: An Overview. arXiv:1806.10254 [cs.DC] https:\/\/arxiv.org\/abs\/1806.10254","DOI":"10.1007\/978-3-319-63962-8_185-1"},{"key":"e_1_2_1_37_1","volume-title":"33rd International Symposium on Reliable Distributed Systems Workshops","author":"Pregui\u00e7a Nuno","year":"2014","unstructured":"Nuno Pregui\u00e7a, Marek Zawirski, Annette Bieniusa, S\u00e9rgio Duarte, Valter Balegas, Carlos Baquero, and Marc Shapiro. 2014. SwiftCloud: Fault-Tolerant Geo-Replication Integrated all the Way to the Client Machine. In 33rd International Symposium on Reliable Distributed Systems Workshops (Nara, Japan) (SRDS '14). IEEE, 30--33."},{"key":"e_1_2_1_38_1","first-page":"1","article-title":"Optimistic replication","volume":"37","author":"Saito Yasushi","year":"2005","unstructured":"Yasushi Saito and Marc Shapiro. 2005. Optimistic replication. ACM Comput. Surv. 37, 1 (March 2005), 42--81.","journal-title":"ACM Comput. Surv."},{"key":"e_1_2_1_40_1","volume-title":"Conflict-Free Replicated Data Types. In 13th International Symposium on 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 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (Grenoble, France) (SSS 2011). Springer, 386--400."},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security","author":"Spiegelman Alexander","year":"2022","unstructured":"Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias. 2022. Bullshark: DAG BFT Protocols Made Practical. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (Los Angeles, CA, USA) (CCS '22). ACM, 2705--2718."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles","author":"Suri-Payer Florian","year":"2021","unstructured":"Florian Suri-Payer, Matthew Burke, Zheng Wang, Yunhao Zhang, Lorenzo Alvisi, and Natacha Crooks. 2021. Basil: Breaking up BFT with ACID (transactions). In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles (Virtual Event, Germany) (SOSP '21). ACM, 1--17."},{"key":"e_1_2_1_43_1","volume-title":"2017 47th Annual IEEE\/IFIP International Conference on Dependable Systems and Networks","author":"Wang Guosai","year":"2017","unstructured":"Guosai Wang, Lifei Zhang, and Wei Xu. 2017. What Can We Learn from Four Years of Data Center Hardware Failures?. In 2017 47th Annual IEEE\/IFIP International Conference on Dependable Systems and Networks (Denver, CO, USA) (DSN 2017). IEEE, 25--36."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447865.3457962"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331591"},{"key":"e_1_2_1_46_1","unstructured":"Gengrui Zhang Yunhao Mao Shiquan Zhang Shashank Motepalli Fei Pan and Hans-Arno Jacobsen. 2023. V-Guard: An Efficient Permissioned Blockchain for Achieving Consensus under Dynamic Memberships in V2X. arXiv:2301.06210 [cs.DC] https:\/\/arxiv.org\/abs\/2301.06210"},{"key":"e_1_2_1_47_1","volume-title":"Article 134 (Jan.","author":"Zhang Gengrui","year":"2024","unstructured":"Gengrui Zhang, Fei Pan, Yunhao Mao, Sofia Tijanic, Michael Dang'ana, Shashank Motepalli, Shiquan Zhang, and Hans-Arno Jacobsen. 2024. Reaching Consensus in the Byzantine Empire: AComprehensive Review of BFT Consensus Algorithms. ACM Comput. Surv. 56, 5, Article 134 (Jan. 2024)."},{"key":"e_1_2_1_48_1","volume-title":"PrestigeBFT: Revolutionizing View Changes in BFT Consensus Algorithms with Reputation Mechanisms. In 40th International Conference on Data Engineering","author":"Zhang Gengrui","year":"2024","unstructured":"Gengrui Zhang, Fei Pan, Sofia Tijanic, and Hans-Arno Jacobsen. 2024. PrestigeBFT: Revolutionizing View Changes in BFT Consensus Algorithms with Reputation Mechanisms. In 40th International Conference on Data Engineering (Utrecht, Netherlands) (ICDE 2024). IEEE, 1930--1943."},{"key":"e_1_2_1_49_1","article-title":"Building Consistent Transactions with Inconsistent Replication","volume":"35","author":"Zhang Irene","year":"2018","unstructured":"Irene Zhang, Naveen Kr. Sharma, Adriana Szekeres, Arvind Krishnamurthy, and Dan R. K. Ports. 2018. Building Consistent Transactions with Inconsistent Replication. ACM Trans. Comput. Syst. 35, 4, Article 12 (dec 2018).","journal-title":"ACM Trans. Comput. Syst."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/3488766.3488802"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1080\/17445760.2015.1078802"},{"key":"e_1_2_1_52_1","volume-title":"IET International Conference on Information and Communications Technologies (IETICT","author":"Zhao Wenbing","year":"2013","unstructured":"Wenbing Zhao and Mamdouh Babi. 2013. Byzantine fault tolerant collaborative editing. In IET International Conference on Information and Communications Technologies (IETICT 2013). IEEE, 233--240."},{"key":"e_1_2_1_53_1","volume-title":"2016 IEEE International Conference on Electro Information Technology (EIT","author":"Zhao Wenbing","year":"2016","unstructured":"Wenbing Zhao, Mamdouh Babi, William Yang, Xiong Luo, Yueqin Zhu, Jack Yang, Chaomin Luo, and Mary Yang. 2016. Byzantine fault tolerance for collaborative editing with commutative operations. In 2016 IEEE International Conference on Electro Information Technology (EIT 2016). IEEE, 0246--0251."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3705829.3705850","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T23:26:29Z","timestamp":1740785189000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3705829.3705850"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["10.14778\/3705829.3705850"],"URL":"https:\/\/doi.org\/10.14778\/3705829.3705850","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,10]]},"assertion":[{"value":"2025-02-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}