{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T20:37:11Z","timestamp":1780346231955,"version":"3.54.1"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:p>\n            Distributed coordination services are fundamental components of distributed systems, employing durable replicated state machines (RSMs) to ensure consistency across replicas and prevent data loss, even in the event of all nodes failing. These services typically rely on persistent logs for rapid recovery, as a universally agreed-upon log allows replicas to restore their state by sequentially replaying ordered log entries. However, the requirement for a\n            <jats:italic toggle=\"yes\">totally ordered<\/jats:italic>\n            log inherently limits opportunities for parallelism.\n          <\/jats:p>\n          <jats:p>\n            This paper introduces Fleet, a high-performance durable RSM protocol that combines a hybrid scattered-entry log with an asynchronous ordered log. Our approach integrates synchronous persistence of scattered entries with asynchronous persistence of ordered entries, ensuring both rapid recovery and high levels of parallelism. Additionally, we propose a parallel applying optimization for the etcd database, named\n            <jats:italic toggle=\"yes\">pre-apply.<\/jats:italic>\n            Experimental results demonstrate that Fleet significantly outperforms Raft and Scalog in terms of throughput and latency, achieving up to 10\u00d7 the throughput under specific configurations and scaling effectively across multiple nodes. Additionally, with the pre-apply optimization, Fleet delivers a 10-fold increase in throughput compared to sequential applying on etcd. Although Fleet incurs a 5% overhead in recovery time during leader failure, this delay is tolerable given the rarity of such events.\n          <\/jats:p>","DOI":"10.14778\/3718057.3718077","type":"journal-article","created":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T18:11:49Z","timestamp":1756318309000},"page":"1522-1535","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["FLEET: High-Performance Durable Replicated State Machines Using Scattered and Coordinated Log Entries"],"prefix":"10.14778","volume":"18","author":[{"given":"Hua","family":"Fan","sequence":"first","affiliation":[{"name":"Alibaba Cloud Computing"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hao","family":"Tan","sequence":"additional","affiliation":[{"name":"University of Waterloo"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wenchao","family":"Zhou","sequence":"additional","affiliation":[{"name":"Alibaba Cloud Computing"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Feifei","family":"Li","sequence":"additional","affiliation":[{"name":"Alibaba Cloud Computing"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,8,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCCN.2016.7568499"},{"key":"e_1_2_1_2_1","unstructured":"Raft authors. 2024. Raft Consensus Algorithm. https:\/\/raft.github.io\/. Accessed: 2024-11-01."},{"key":"e_1_2_1_3_1","volume-title":"Kubernetes: Production-Grade Container Orchestration. https:\/\/kubernetes.io. Accessed: 2024-11-01.","author":"The Kubernetes","year":"2024","unstructured":"The Kubernetes authors. 2024. Kubernetes: Production-Grade Container Orchestration. https:\/\/kubernetes.io. Accessed: 2024-11-01."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535930"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522732"},{"key":"e_1_2_1_6_1","unstructured":"MariaDB Knowledge Base. 2024. Parallel Replication. https:\/\/mariadb.com\/kb\/en\/parallel-replication. Accessed: 2024-11-01."},{"key":"e_1_2_1_7_1","volume-title":"On the Efficiency of Durable State Machine Replication. In 2013 USENIX Annual Technical Conference (USENIX ATC 13)","author":"Bessani Alysson","year":"2013","unstructured":"Alysson Bessani, Marcel Santos, Jo\u00e3o Felix, Nuno Neves, and Miguel Correia. 2013. On the Efficiency of Durable State Machine Replication. In 2013 USENIX Annual Technical Conference (USENIX ATC 13). USENIX Association, San Jose, CA, 169\u2013180. https:\/\/www.usenix.org\/conference\/atc13\/technical-sessions\/presentation\/bessani"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/SRDS.2012.66"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1298455.1298487"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196898"},{"key":"e_1_2_1_11_1","volume-title":"Linearizable Quorum Reads in Paxos. In 11th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 19)","author":"Charapko Aleksey","year":"2019","unstructured":"Aleksey Charapko, Ailidani Ailijiang, and Murat Demirbas. 2019. Linearizable Quorum Reads in Paxos. In 11th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 19). USENIX Association, Renton, WA. https:\/\/www.usenix.org\/conference\/hotstorage19\/presentation\/charapko"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452834"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3139645.3139658"},{"key":"e_1_2_1_15_1","volume-title":"17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20)","author":"Ding Cong","year":"2020","unstructured":"Cong Ding, David Chu, Evan Zhao, Xiang Li, Lorenzo Alvisi, and Robbert Van Renesse. 2020. Scalog: Seamless Reconfiguration and Total Order in a Scalable Shared Log. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20). USENIX Association, Santa Clara, CA, 325\u2013338. https:\/\/www.usenix.org\/conference\/nsdi20\/presentation\/ding"},{"key":"e_1_2_1_16_1","unstructured":"etcd authors. 2024. etcd mvcc package. https:\/\/github.com\/etcd-io\/etcd\/tree\/v3.5.1\/server\/mvcc. Accessed: 2024-11-01."},{"key":"e_1_2_1_17_1","unstructured":"etcd authors. 2024. etcd mvcc server. https:\/\/github.com\/etcd-io\/etcd\/tree\/v3.5.1\/server. Accessed: 2024-11-01."},{"key":"e_1_2_1_18_1","unstructured":"etcd docs. 2024. Data model. https:\/\/etcd.io\/docs\/v3.5\/learning\/data_model\/. Accessed: 2024-11-01."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_2_1_20_1","unstructured":"Cloud Native Computing Foundation. 2024. A distributed reliable key-value store for the most critical data of a distributed system. https:\/\/etcd.io\/. Accessed: 2024-11-01."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/74850.74870"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3561261.3561262"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544908"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","unstructured":"Heidi Howard Dahlia Malkhi and Alexander Spiegelman. 2017. Flexible Paxos: Quorum Intersection Revisited. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016) (Leibniz International Proceedings in Informatics (LIPIcs)) Panagiota Fatourou Ernesto Jim\u00e9nez and Fernando Pedone (Eds.) Vol. 70. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik Dagstuhl Germany 25:1\u201325:14. 10.4230\/LIPIcs.OPODIS.2016.25","DOI":"10.4230\/LIPIcs.OPODIS.2016.25"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415535"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 2010 USENIX Conference on USENIX Annual Technical Conference","author":"Hunt Patrick","year":"2010","unstructured":"Patrick Hunt, Mahadev Konar, Flavio P. Junqueira, and Benjamin Reed. 2010. ZooKeeper: Wait-Free Coordination for Internet-Scale Systems. In Proceedings of the 2010 USENIX Conference on USENIX Annual Technical Conference (Boston, MA) (USENIXATC'10). USENIX Association, USA, 11."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1243418.1243426"},{"key":"e_1_2_1_28_1","volume-title":"13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16)","author":"Istv\u00e1n Zsolt","year":"2016","unstructured":"Zsolt Istv\u00e1n, David Sidler, Gustavo Alonso, and Marko Vukolic. 2016. Consensus in a Box: Inexpensive Coordination in Hardware. In 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16). USENIX Association, Santa Clara, CA, 425\u2013438. https:\/\/www.usenix.org\/conference\/nsdi16\/technical-sessions\/presentation\/istvan"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434770.3459730"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00092"},{"key":"e_1_2_1_31_1","volume-title":"Eventually Durable State Machines. Master's thesis","author":"Kathuria Kriti","unstructured":"Kriti Kathuria. 2024. Eventually Durable State Machines. Master's thesis. University of Waterloo, Waterloo, Canada."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465363"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2993.2994"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/279227.279229"},{"key":"e_1_2_1_35_1","first-page":"4","article-title":"Paxos Made Simple","volume":"32","author":"Lamport Leslie","year":"2001","unstructured":"Leslie Lamport. 2001. Paxos Made Simple. ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001) (December 2001), 51\u201358. https:\/\/www.microsoft.com\/en-us\/research\/publication\/paxos-made-simple\/","journal-title":"ACM SIGACT News (Distributed Computing Column)"},{"key":"e_1_2_1_36_1","unstructured":"Leslie Lamport. 2005. Generalized Consensus and Paxos. Technical Report MSR-TR-2005-33. 60 pages. https:\/\/www.microsoft.com\/en-us\/research\/publication\/generalized-consensus-and-paxos\/"},{"key":"e_1_2_1_37_1","volume-title":"Distributed Computing 19 (October","author":"Lamport Leslie","year":"2006","unstructured":"Leslie Lamport. 2006. Fast Paxos. Distributed Computing 19 (October 2006), 79\u2013103. https:\/\/www.microsoft.com\/en-us\/research\/publication\/fast-paxos\/"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/645953.675640"},{"key":"e_1_2_1_39_1","volume-title":"12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16)","author":"Li Jialin","unstructured":"Jialin Li, Ellis Michael, Naveen Kr. Sharma, Adriana Szekeres, and Dan R. K. Ports. 2016. Just Say NO to Paxos Overhead: Replacing Consensus with Network Ordering. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16). USENIX Association, Savannah, GA, 467\u2013483. https:\/\/www.usenix.org\/conference\/osdi16\/technical-sessions\/presentation\/li"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3458454"},{"key":"e_1_2_1_41_1","unstructured":"Barbara Liskov and James Cowling. 2012. Viewstamped Replication Revisited. Technical Report MIT-CSAIL-TR-2012-021. MIT."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation","author":"Mao Yanhua","year":"2008","unstructured":"Yanhua Mao, Flavio P. Junqueira, and Keith Marzullo. 2008. Mencius: Building Efficient Replicated State Machines for WANs. In Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation (San Diego, California) (OSDI'08). USENIX Association, USA, 369\u2013384."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2517350"},{"key":"e_1_2_1_44_1","unstructured":"Diego Ongaro. 2014. Consensus: Bridging Theory and Practice. Ph.D. Dissertation. Stanford CA USA. Advisor(s) K. Ousterhout John and David Mazi\u00e8res and Mendel Rosenblum . AAI28121474."},{"key":"e_1_2_1_45_1","volume-title":"2014 USENIX Annual Technical Conference (USENIX ATC 14)","author":"Ongaro Diego","year":"2014","unstructured":"Diego Ongaro and John Ousterhout. 2014. In Search of an Understandable Consensus Algorithm. In 2014 USENIX Annual Technical Conference (USENIX ATC 14). USENIX Association, Philadelphia, PA, 305\u2013319. https:\/\/www.usenix.org\/conference\/atc14\/technical-sessions\/presentation\/ongaro"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-39940-9_299"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2749246.2749267"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3546037.3546058"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 18th International Conference on Network and Service Management","author":"Sagkriotis Stefanos","year":"2023","unstructured":"Stefanos Sagkriotis and Dimitrios Pezaros. 2023. Scalable Data Plane Caching for Kubernetes. In Proceedings of the 18th International Conference on Network and Service Management (Thessaloniki, Greece) (CNSM '22). International Federation for Information Processing, Laxenburg, AUT, Article 66, 7 pages."},{"key":"e_1_2_1_50_1","unstructured":"scalog authors. 2024. scalog. https:\/\/github.com\/scalog\/scalog. Accessed: 2024-11-01."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/98163.98167"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3386134"},{"key":"e_1_2_1_53_1","volume-title":"Twine: A Unified Cluster Management System for Shared Infrastructure. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20)","author":"Tang Chunqiang","year":"2020","unstructured":"Chunqiang Tang, Kenny Yu, Kaushik Veeraraghavan, Jonathan Kaldor, Scott Michelson, Thawan Kooburat, Aravind Anbudurai, Matthew Clark, Kabir Gogia, Long Cheng, Ben Christensen, Alex Gartrell, Maxim Khutornenko, Sachin Kulkarni, Marcin Pawlowski, Tuomas Pelkonen, Andre Rodrigues, Rounak Tibrewal, Vaishnavi Venkatesan, and Peter Zhang. 2020. Twine: A Unified Cluster Management System for Shared Infrastructure. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). USENIX Association, 787\u2013803. https:\/\/www.usenix.org\/conference\/osdi20\/presentation\/tang"},{"key":"e_1_2_1_54_1","volume-title":"Object Storage on CRAQ: High-Throughput Chain Replication for Read-Mostly Workloads. In 2009 USENIX Annual Technical Conference (USENIX ATC 09)","author":"Terrace Jeff","unstructured":"Jeff Terrace and Michael J. Freedman. 2009. Object Storage on CRAQ: High-Throughput Chain Replication for Read-Mostly Workloads. In 2009 USENIX Annual Technical Conference (USENIX ATC 09). USENIX Association, San Diego, CA. https:\/\/www.usenix.org\/conference\/usenix-09\/object-storage-craq-high-throughput-chain-replication-read-mostly-workloads"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2673577"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476273"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3542929.3563462"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3718057.3718077","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T18:13:17Z","timestamp":1756318397000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3718057.3718077"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1]]},"references-count":57,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["10.14778\/3718057.3718077"],"URL":"https:\/\/doi.org\/10.14778\/3718057.3718077","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,1]]},"assertion":[{"value":"2025-08-27","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}