{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T09:03:56Z","timestamp":1775639036809,"version":"3.50.1"},"reference-count":128,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,5]]},"abstract":"<jats:p>Distributed datastores underpin highly concurrent, read-intensive applications, ensuring consistency, availability, and performance. They use crash-tolerant protocols to replicate data and endure replica server crashes. To ensure safety and meet the performance demands, replication must support high-throughput, strongly consistent (i.e., linearizable) reads without assuming any synchrony. However, existing protocols either 1 relax consistency, or provide linearizable reads that are 2 fully asynchronous but remote (involving multiple replicas), or 3 local but require synchrony.<\/jats:p>\n          <jats:p>\n            This work explores the tradeoffs between consistency, asynchrony, and performance in crash-tolerant protocols, and proves that\n            <jats:italic toggle=\"yes\">in linearizable asynchronous read\/write registers tolerating a single crash, no reads can be local.<\/jats:italic>\n            Building on this, we introduce\n            <jats:italic toggle=\"yes\">almost-local reads<\/jats:italic>\n            (ALRs), a new abstraction that ensures crash tolerance and linearizability under asynchrony. While ALRs have slightly higher latency than local reads, they remain lightweight, with computation and network costs close to single-node reads.\n          <\/jats:p>\n          <jats:p>We present two simple yet effective ALR schemes that enhance protocols across all three categories. For protocols with local reads, ALRs address consistency or synchrony issues with minimal throughput loss. In asynchronous linearizable protocols, they improve performance without compromises. Our evaluation shows that ALR-enhanced ZAB and Hermes achieve within 2% and 5% of their original throughput in 95% reads while ensuring linearizability under asynchrony. On Raft, ALRs deliver over 2.5x higher throughput without compromising consistency or asynchrony.<\/jats:p>","DOI":"10.14778\/3746405.3746411","type":"journal-article","created":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T17:06:20Z","timestamp":1756919180000},"page":"2831-2845","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["The LAW Theorem: Local Reads and Linearizable Asynchronous Replication"],"prefix":"10.14778","volume":"18","author":[{"given":"Antonios","family":"Katsarakis","sequence":"first","affiliation":[{"name":"Huawei Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vasilis","family":"Gavrielatos","sequence":"additional","affiliation":[{"name":"Huawei Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emmanouil","family":"Giortamis","sequence":"additional","affiliation":[{"name":"TU Munich"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pramod","family":"Bhatotia","sequence":"additional","affiliation":[{"name":"TU Munich"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aleksandar","family":"Dragojevic","sequence":"additional","affiliation":[{"name":"OpenAI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boris","family":"Grot","sequence":"additional","affiliation":[{"name":"University of Edinburgh"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vijay","family":"Nagarajan","sequence":"additional","affiliation":[{"name":"University of Utah"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panagiota","family":"Fatourou","sequence":"additional","affiliation":[{"name":"FORTH ICS and University of Crete"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,3]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Consul configuration store. https:\/\/www.consul.io\/. (Accessed on 09\/06\/2025)."},{"key":"e_1_2_1_2_1","unstructured":"etcd Key-Value storage system. https:\/\/etcd.io\/. (Accessed on 09\/06\/2025)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2012.33"},{"key":"e_1_2_1_4_1","first-page":"3","volume-title":"Proceedings of the 12th Conference on Hot Topics in Operating Systems, HotOS'09","author":"Marcos","year":"2009","unstructured":"Marcos K. Aguilera and Michael Walfish. No time for asynchrony. In Proceedings of the 12th Conference on Hot Topics in Operating Systems, HotOS'09, page 3, USA, 2009. USENIX Association."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2831090.2831103"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9407-2"},{"key":"e_1_2_1_7_1","first-page":"570","volume-title":"Proceedings of the 2nd International Conference on Software Engineering, ICSE '76","author":"Alsberg Peter","year":"1976","unstructured":"Peter Alsberg and John Day. A principle for resilient sharing of distributed resources. In Proceedings of the 2nd International Conference on Software Engineering, ICSE '76, pages 562\u2013570, USA, 1976. IEEE."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS47924.2020.00120"},{"key":"e_1_2_1_9_1","first-page":"14","volume-title":"Proceedings of the 9th USENIX Conference on Hot Topics in Cloud Computing, HotCloud'17","author":"Arora Vaibhav","year":"2017","unstructured":"Vaibhav Arora, Tanuj Mittal, Divyakant Agrawal, Amr El Abbadi, Xun Xue, Zhiyanan Zhiyanan, and Zhujianfeng Zhujianfeng. Leader or majority: Why have one when you can have both? improving read scalability in raft-like consensus protocols. In Proceedings of the 9th USENIX Conference on Hot Topics in Cloud Computing, HotCloud'17, page 14, USA, 2017. USENIX Association."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2318857.2254766"},{"issue":"1","key":"e_1_2_1_11_1","first-page":"124","article-title":"Sharing Memory Robustly","volume":"42","author":"Attiya Hagit","year":"1995","unstructured":"Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing Memory Robustly in Message-passing Systems. J. ACM, 42(1):124\u2013142, 1995.","journal-title":"Message-passing Systems. J. ACM"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/176575.176576"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735508.2735509"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2909870"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2639988.2655736"},{"key":"e_1_2_1_16_1","first-page":"234","volume-title":"Proceedings of the Conference on Innovative Data system Research (CIDR)","author":"Baker Jason","year":"2011","unstructured":"Jason Baker, Chris Bond, James C. Corbett, JJ Furman, Andrey Khorlin, James Larson, Jean-Michel Leon, Yawei Li, Alexander Lloyd, and Vadim Yushprakh. Megastore: Providing scalable, highly available storage for interactive services. In Proceedings of the Conference on Innovative Data system Research (CIDR), pages 223\u2013234, Asilomar, CA, 2011."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2534500"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3015146"},{"key":"e_1_2_1_19_1","volume-title":"Parameterized algorithm for replicated objects with local reads","author":"Bi Changyu","year":"2022","unstructured":"Changyu Bi, Vassos Hadzilacos, and Sam Toueg. Parameterized algorithm for replicated objects with local reads. 2022."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/41457.37515"},{"key":"e_1_2_1_21_1","first-page":"154","volume-title":"Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, NSDI'11","author":"Bolosky William J.","year":"2011","unstructured":"William J. Bolosky, Dexter Bradshaw, Randolph B. Haagens, Norbert P. Kusters, and Peng Li. Paxos Replicated State Machines As the Basis of a High-performance Data Store. In Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, NSDI'11, pages 141\u2013154, USA, 2011. USENIX Association."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/343477.343502"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2012.37"},{"key":"e_1_2_1_24_1","first-page":"60","volume-title":"Proceedings of the 2013 Conference on Annual Technical Conference, ATC'13","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, Mark Marchukov, Dmitri Petrov, Lovro Puzar, Yee Jiun Song, and Venkat Venkataramani. TAO: Facebook's Distributed Data Store for the Social Graph. In Proceedings of the 2013 Conference on Annual Technical Conference, ATC'13, pages 49\u201360, Berkeley, 2013. USENIX."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1561\/2500000011"},{"key":"e_1_2_1_26_1","first-page":"617","volume-title":"17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20)","author":"Burke Matthew","year":"2020","unstructured":"Matthew Burke, Audrey Cheng, and Wyatt Lloyd. Gryff: Unifying consensus and shared registers. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20), pages 591\u2013617, Santa Clara, CA, February 2020. USENIX Association."},{"key":"e_1_2_1_27_1","first-page":"24","volume-title":"Burrows. The Chubby Lock Service for Loosely-coupled Distributed Systems. In Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation -","volume":"7","author":"Mike","year":"2006","unstructured":"Mike Burrows. The Chubby Lock Service for Loosely-coupled Distributed Systems. In Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation - Volume 7, OSDI '06, pages 24\u201324, USA, 2006. USENIX Association."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933111"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226647"},{"key":"e_1_2_1_30_1","first-page":"407","volume-title":"Joshua Redstone. Paxos Made Live: An Engineering Perspective. In Proceedings of the Twenty-sixth Annual ACM Symposium on Principles of Distributed Computing, PODC '07","author":"Chandra Tushar D.","year":"2007","unstructured":"Tushar D. Chandra, Robert Griesemer, and Joshua Redstone. Paxos Made Live: An Engineering Perspective. In Proceedings of the Twenty-sixth Annual ACM Symposium on Principles of Distributed Computing, PODC '07, pages 398\u2013407, USA, 2007. ACM."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/3357062.3357073"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3538598.3538616"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454167"},{"key":"e_1_2_1_34_1","first-page":"154","volume-title":"Russell Sears. Benchmarking Cloud Serving Systems with YCSB. In Proceedings of the 1st ACM Symposium on Cloud Computing, SoCC '10","author":"Cooper Brian F.","year":"2010","unstructured":"Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. Benchmarking Cloud Serving Systems with YCSB. In Proceedings of the 1st ACM Symposium on Cloud Computing, SoCC '10, pages 143\u2013154, New York, NY, USA, 2010. ACM."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491245"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2020.2992106"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323189"},{"key":"e_1_2_1_38_1","first-page":"414","volume-title":"Orion Hodson. FaRM: Fast Remote Memory. In 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI 14)","author":"Dragojevi\u0107 Aleksandar","year":"2014","unstructured":"Aleksandar Dragojevi\u0107, Dushyanth Narayanan, Miguel Castro, and Orion Hodson. FaRM: Fast Remote Memory. In 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI 14), pages 401\u2013414, Seattle, WA, 2014. USENIX Association."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815425"},{"key":"e_1_2_1_40_1","first-page":"14","volume-title":"Proceedings of the USENIX Annual Technical Conference, ATC '19","author":"Duplyakin Dmitry","year":"2019","unstructured":"Dmitry Duplyakin, Robert Ricci, Aleksander Maricq, Gary Wong, Jonathon Duerig, Eric Eide, Leigh Stoller, Mike Hibler, David Johnson, Kirk Webb, Aditya Akella, Kuangching Wang, Glenn Ricart, Larry Landweber, Chip Elliott, Michael Zink, Emmanuel Cecchet, Snigdhaswin Kar, and Prabodh Mishra. The design and operation of CloudLab. In Proceedings of the USENIX Annual Technical Conference, ATC '19, pages 1\u201314, July 2019."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011802"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/42282.42283"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46140-3_14"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1984.1056918"},{"issue":"2","key":"e_1_2_1_45_1","first-page":"374","volume":"32","author":"Fischer Michael J.","year":"1985","unstructured":"Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of Distributed Consensus with One Faulty Process. J. ACM, 32(2):374\u2013382, April 1985.","journal-title":"Paterson. Impossibility of Distributed Consensus with One Faulty Process. J. ACM"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3190508.3190550"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447786.3456240"},{"key":"e_1_2_1_48_1","first-page":"16","volume-title":"Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '20","author":"Gavrielatos Vasilis","year":"2020","unstructured":"Vasilis Gavrielatos, Antonios Katsarakis, Vijay Nagarajan, Boris Grot, and Arpit Joshi. Kite: Efficient and available release consistency for the datacenter. In Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '20, page 1\u201316, New York, NY, USA, 2020. Association for Computing Machinery."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400817"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/564585.564601"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/74850.74870"},{"key":"e_1_2_1_52_1","first-page":"297","volume-title":"Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, PODC '00","author":"Guerraoui Rachid","year":"2000","unstructured":"Rachid Guerraoui. Indulgent algorithms (preliminary version). In Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, PODC '00, page 289\u2013297, New York, NY, USA, 2000. Association for Computing Machinery."},{"key":"e_1_2_1_53_1","first-page":"2007","volume-title":"Vivien Quema. A High Throughput Atomic Storage Algorithm. In Proceedings of the 27th International Conference on Distributed Computing Systems, ICDCS '07","author":"Guerraoui Rachid","unstructured":"Rachid Guerraoui, Dejan Kostic, Ron R. Levy, and Vivien Quema. A High Throughput Atomic Storage Algorithm. In Proceedings of the 27th International Conference on Distributed Computing Systems, ICDCS '07, pages 19\u2013, Washington, DC, USA, 2007. IEEE Computer Society."},{"key":"e_1_2_1_54_1","volume-title":"Memory access efficiency in distributed atomic object implementations","author":"Hadjistasi Theophanis","year":"2019","unstructured":"Theophanis Hadjistasi. Memory access efficiency in distributed atomic object implementations. 2019."},{"key":"e_1_2_1_55_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming (ICALP 2018","author":"Hadjistasi Theophanis","year":"2018","unstructured":"Theophanis Hadjistasi and Alexander A Schwarzmann. Consistent distributed memory services: Resilience and efficiency. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415535"},{"key":"e_1_2_1_58_1","first-page":"11","volume-title":"Benjamin Reed. ZooKeeper: Wait-free Coordination for Internet-scale Systems. In Proceedings of the USENIX Annual Technical Conference, USENIX ATC'10","author":"Hunt Patrick","year":"2010","unstructured":"Patrick Hunt, Mahadev Konar, Flavio P. Junqueira, and Benjamin Reed. ZooKeeper: Wait-free Coordination for Internet-scale Systems. In Proceedings of the USENIX Annual Technical Conference, USENIX ATC'10, pages 11\u201311, Berkeley, CA, USA, 2010. USENIX Association."},{"issue":"2","key":"e_1_2_1_59_1","first-page":"1","article-title":"Derecho: Fast state machine replication for cloud services","volume":"36","author":"Jha Sagar","year":"2019","unstructured":"Sagar Jha, Jonathan Behrens, Theo Gkountouvas, Matthew Milano, Weijia Song, Edward Tremel, Robbert Van Renesse, Sydney Zink, and Kenneth P. Birman. Derecho: Fast state machine replication for cloud services. Trans. Comput. Syst., 36(2):4:1\u20134:49, 2019.","journal-title":"Trans. Comput. Syst."},{"key":"e_1_2_1_60_1","first-page":"49","volume-title":"15th USENIX Symposium on Networked Systems Design and Implementation (NSDI 18)","author":"Jin Xin","year":"2018","unstructured":"Xin Jin, Xiaozhou Li, Haoyu Zhang, Nate Foster, Jeongkeun Lee, Robert Soul\u00e9, Changhoon Kim, and Ion Stoica. NetChain: Scale-Free Sub-RTT coordination. In 15th USENIX Symposium on Networked Systems Design and Implementation (NSDI 18), pages 35\u201349, Renton, WA, April 2018. USENIX Association."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2011.5958223"},{"key":"e_1_2_1_62_1","first-page":"15","volume-title":"Indranil Gupta. Service Fabric: A Distributed Platform for Building Microservices in the Cloud. In Proceedings of the EuroSys Conference, EuroSys '18","author":"Kakivaya Gopal","year":"2018","unstructured":"Gopal Kakivaya, Lu Xun, Richard Hasha, Shegufta Bakht Ahsan, Todd Pfieiger, Rishi Sinha, Anurag Gupta, Mihail Tarta, Mark Fussell, Vipul Modi, Mansoor Mohsin, Ray Kong, Anmol Ahuja, Oana Platon, Alex Wun, Matthew Snider, Chacko Daniel, Dan Mastrian, Yang Li, Aprameya Rao, Vaishnav Kidambi, Randy Wang, Abhishek Ram, Sumukh Shivaprakash, Rajeet Nair, Alan Warwick, Bharat S. Narasimman, Meng Lin, Jeffrey Chen, Abhay Balkrishna Mhatre, Preetha Subbarayalu, Mert Coskun, and Indranil Gupta. Service Fabric: A Distributed Platform for Building Microservices in the Cloud. In Proceedings of the EuroSys Conference, EuroSys '18, pages 1\u201315, USA, 2018. ACM."},{"key":"e_1_2_1_63_1","first-page":"450","volume-title":"David Andersen. Design Guidelines for High Performance RDMA Systems. In Proceedings of the 2016 USENIX Conference on Usenix Annual Technical Conference, USENIX ATC '16","author":"Kalia Anuj","year":"2016","unstructured":"Anuj Kalia, Michael Kaminsky, and David Andersen. Design Guidelines for High Performance RDMA Systems. In Proceedings of the 2016 USENIX Conference on Usenix Annual Technical Conference, USENIX ATC '16, pages 437\u2013450, Berkeley, CA, USA, 2016. USENIX Association."},{"key":"e_1_2_1_64_1","first-page":"201","volume-title":"12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16)","author":"Kalia Anuj","year":"2016","unstructured":"Anuj Kalia, Michael Kaminsky, and David G. Andersen. FaSST: Fast, scalable and simple distributed transactions with Two-Sided (RDMA) datagram RPCs. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16), pages 185\u2013201, Savannah, GA, November 2016. USENIX Association."},{"key":"e_1_2_1_65_1","volume-title":"Hermes protocol. https:\/\/github.com\/ease-lab\/Hermes","author":"Katsarakis Antonios","year":"2020","unstructured":"Antonios Katsarakis. Hermes protocol. https:\/\/github.com\/ease-lab\/Hermes, 2020. (Accessed on 09\/06\/2025)."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373376.3378496"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447786.3456234"},{"key":"e_1_2_1_68_1","first-page":"143","volume-title":"VLDB","author":"Kemme Bettina","unstructured":"Bettina Kemme and Gustavo Alonso. Don't be lazy, be consistent: Postgres-r, a new way to implement database replication. In VLDB, pages 134\u2013143. Citeseer, 2000."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.14778\/3523210.3523213"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3342195.3387545"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS49936.2021.00101"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/138873.138877"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01786228"},{"key":"e_1_2_1_75_1","volume-title":"The part-time parliament. ACM Transactions on Computer Systems (TOCS), 16(2):133\u2013169","author":"Lamport Leslie","year":"1998","unstructured":"Leslie Lamport. The part-time parliament. ACM Transactions on Computer Systems (TOCS), 16(2):133\u2013169, 1998."},{"key":"e_1_2_1_76_1","volume-title":"Generalized consensus and Paxos","author":"Lamport Leslie","year":"2005","unstructured":"Leslie Lamport. Generalized consensus and Paxos, 2005."},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-006-0005-x"},{"issue":"4","key":"e_1_2_1_78_1","first-page":"18","article-title":"Paxos made simple","volume":"32","author":"Leslie Lamport","year":"2001","unstructured":"Leslie Lamport et al. Paxos made simple. ACM Sigact News, 32(4):18\u201325, 2001.","journal-title":"ACM Sigact News"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/1582716.1582783"},{"key":"e_1_2_1_80_1","volume-title":"Alexander Shraer. Modular Composition of Coordination Services. In USENIX Annual Technical Conference","author":"Lev-Ari Kir","year":"2016","unstructured":"Kir Lev-Ari, Edward Bortnikov, Idit Keidar, and Alexander Shraer. Modular Composition of Coordination Services. In USENIX Annual Technical Conference, 2016."},{"key":"e_1_2_1_81_1","first-page":"292","volume-title":"2014 USENIX Annual Technical Conference (USENIX ATC 14)","author":"Li Cheng","year":"2014","unstructured":"Cheng Li, Joao Leit\u00e3o, Allen Clement, Nuno Pregui\u00e7a, Rodrigo Rodrigues, and Viktor Vafeiadis. Automating the choice of consistency levels in replicated systems. In 2014 USENIX Annual Technical Conference (USENIX ATC 14), pages 281\u2013292, Philadelphia, PA, June 2014. USENIX Association."},{"key":"e_1_2_1_82_1","first-page":"278","volume-title":"Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI'12","author":"Li Cheng","year":"2012","unstructured":"Cheng Li, Daniel Porto, Allen Clement, Johannes Gehrke, Nuno Pregui\u00e7a, and Rodrigo Rodrigues. Making geo-replicated systems fast as possible, consistent when necessary. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI'12, pages 265\u2013278, Berkeley, CA, USA, 2012. USENIX Association."},{"key":"e_1_2_1_83_1","first-page":"483","volume-title":"Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation, OSDI'16","author":"Li Jialin","year":"2016","unstructured":"Jialin Li, Ellis Michael, Naveen Kr. Sharma, Adriana Szekeres, and Dan R. K. Ports. Just Say No to Paxos Overhead: Replacing Consensus with Network Ordering. In Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation, OSDI'16, pages 467\u2013483, USA, 2016. USENIX Association."},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/2670979.2670988"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/121132.121169"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043593"},{"key":"e_1_2_1_87_1","first-page":"150","volume-title":"Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation, OSDI'16","author":"Lu Haonan","year":"2016","unstructured":"Haonan Lu, Christopher Hodsdon, Khiem Ngo, Shuai Mu, and Wyatt Lloyd. The snow theorem and latency-optimal read-only transactions. In Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation, OSDI'16, page 135\u2013150, USA, 2016. USENIX Association."},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.5555\/3488766.3488785"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815426"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627699"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1109\/FTCS.1997.614100"},{"key":"e_1_2_1_92_1","first-page":"384","volume-title":"Keith Marzullo. Mencius: Building Efficient Replicated State Machines for WANs. In Proceedings of the 8th Conference on Operating Systems Design and Implementation, OSDI'08","author":"Mao Yanhua","year":"2008","unstructured":"Yanhua Mao, Flavio P. Junqueira, and Keith Marzullo. Mencius: Building Efficient Replicated State Machines for WANs. In Proceedings of the 8th Conference on Operating Systems Design and Implementation, OSDI'08, pages 369\u2013384, Berkeley, CA, USA, 2008. USENIX."},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2011.5958258"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2517350"},{"key":"e_1_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1145\/2670979.2671001"},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-018-0615-8"},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1145\/3694715.3695945"},{"key":"e_1_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-01764-3"},{"key":"e_1_2_1_99_1","first-page":"398","volume-title":"Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation, nsdi'13","author":"Nishtala Rajesh","year":"2013","unstructured":"Rajesh Nishtala, Hans Fugal, Steven Grimm, Marc Kwiatkowski, Herman Lee, Harry C. Li, Ryan McElroy, Mike Paleczny, Daniel Peek, Paul Saab, David Stafford, Tony Tung, and Venkateshwaran Venkataramani. Scaling Memcache at Facebook. In Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation, nsdi'13, pages 385\u2013398, Berkeley, CA, USA, 2013. USENIX Association."},{"key":"e_1_2_1_100_1","first-page":"320","volume-title":"Proceedings of the USENIX Annual Technical Conference, USENIX ATC'14","author":"Ongaro Diego","year":"2014","unstructured":"Diego Ongaro and John Ousterhout. In Search of an Understandable Consensus Algorithm. In Proceedings of the USENIX Annual Technical Conference, USENIX ATC'14, pages 305\u2013320, USA, 2014. USENIX."},{"key":"e_1_2_1_101_1","volume-title":"9th USENIX Symposium on Operating Systems Design and Implementation (OSDI 10)","author":"Peng Daniel","year":"2010","unstructured":"Daniel Peng and Frank Dabek. Large-scale incremental processing using distributed transactions and notifications. In 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI 10), 2010."},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.1145\/2749246.2749267"},{"key":"e_1_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.1145\/3078597.3078598"},{"key":"e_1_2_1_104_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452744"},{"key":"e_1_2_1_105_1","first-page":"1847","article-title":"Eventual Leader Service in Unreliable Asynchronous Systems: Why? How?","author":"Raynal Michel","year":"2007","unstructured":"Michel Raynal. Eventual Leader Service in Unreliable Asynchronous Systems: Why? How? Research Report PI 1847, 2007.","journal-title":"Research Report PI"},{"key":"e_1_2_1_106_1","volume-title":"Concurrent programming: algorithms, principles, and foundations","author":"Raynal Michel","year":"2012","unstructured":"Michel Raynal. Concurrent programming: algorithms, principles, and foundations. Springer Science & Business Media, 2012."},{"key":"e_1_2_1_107_1","first-page":"6","volume-title":"Reed and Flavio P. Junqueira. A Simple Totally Ordered Broadcast Protocol. In Proceedings of the 2nd Workshop on Large-Scale Distributed Systems and Middleware, LADIS '08","author":"Benjamin","year":"2008","unstructured":"Benjamin Reed and Flavio P. Junqueira. A Simple Totally Ordered Broadcast Protocol. In Proceedings of the 2nd Workshop on Large-Scale Distributed Systems and Middleware, LADIS '08, pages 2:1\u20132:6, USA, 2008. ACM."},{"key":"e_1_2_1_108_1","doi-asserted-by":"publisher","DOI":"10.1145\/1024393.1024400"},{"key":"e_1_2_1_109_1","first-page":"370","article-title":"The fail-stop processor approach. Concurency control and reliability in distributed systems","volume":"13","author":"Schneider Fred B","year":"1987","unstructured":"Fred B Schneider. The fail-stop processor approach. Concurency control and reliability in distributed systems, Chapitre, 13:370\u2013394, 1987.","journal-title":"Chapitre"},{"key":"e_1_2_1_110_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352125"},{"key":"e_1_2_1_111_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453914"},{"key":"e_1_2_1_112_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24550-3_29"},{"key":"e_1_2_1_113_1","volume-title":"FlightTracker: Consistency across Read-Optimized Online Stores at Facebook","author":"Shi Xiao","year":"2020","unstructured":"Xiao Shi, Scott Pruett, Kevin Doherty, Jinyu Han, Dmitri Petrov, Jim Carrig, John Hugg, and Nathan Bronson. FlightTracker: Consistency across Read-Optimized Online Stores at Facebook. USENIX Association, USA, 2020."},{"key":"e_1_2_1_114_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213954"},{"key":"e_1_2_1_115_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536232"},{"key":"e_1_2_1_116_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3386134"},{"key":"e_1_2_1_117_1","first-page":"11","volume-title":"Proceedings of the 2009 Conference on USENIX Annual Technical Conference, USENIX'09","author":"Terrace Jeff","year":"2009","unstructured":"Jeff Terrace and Michael J. Freedman. Object Storage on CRAQ: High-throughput Chain Replication for Read-mostly Workloads. In Proceedings of the 2009 Conference on USENIX Annual Technical Conference, USENIX'09, pages 11\u201311, Berkeley, CA, USA, 2009. USENIX Association."},{"key":"e_1_2_1_118_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522731"},{"key":"e_1_2_1_119_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213838"},{"key":"e_1_2_1_120_1","doi-asserted-by":"publisher","DOI":"10.1145\/3274808.3274818"},{"key":"e_1_2_1_121_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522713"},{"key":"e_1_2_1_122_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407847"},{"key":"e_1_2_1_123_1","first-page":"7","volume-title":"Proceedings of the 6th Conference on Symposium on Opearting Systems Design & Implementation, OSDI'04","author":"van Renesse Robbert","year":"2004","unstructured":"Robbert van Renesse and Fred B. Schneider. Chain Replication for Supporting High Throughput and Availability. In Proceedings of the 6th Conference on Symposium on Opearting Systems Design & Implementation, OSDI'04, pages 7\u20137, Berkeley, CA, USA, 2004. USENIX."},{"key":"e_1_2_1_124_1","doi-asserted-by":"publisher","DOI":"10.1145\/1435417.1435432"},{"key":"e_1_2_1_125_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2898401"},{"key":"e_1_2_1_126_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547323"},{"key":"e_1_2_1_127_1","doi-asserted-by":"publisher","DOI":"10.1145\/3269981"},{"key":"e_1_2_1_128_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368301"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3746405.3746411","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T19:53:32Z","timestamp":1757015612000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3746405.3746411"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5]]},"references-count":128,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["10.14778\/3746405.3746411"],"URL":"https:\/\/doi.org\/10.14778\/3746405.3746411","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,5]]},"assertion":[{"value":"2025-09-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}