{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T05:15:32Z","timestamp":1768972532424,"version":"3.49.0"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>Distributed protocols such as 2PC and Paxos lie at the core of many systems in the cloud, but standard implementations do not scale. New scalable distributed protocols are developed through careful analysis and rewrites, but this process is ad hoc and error-prone. This paper presents an approach for scaling any distributed protocol by applying rule-driven rewrites, borrowing from query optimization. Distributed protocol rewrites entail a new burden: reasoning about spatiotemporal correctness. We leverage order-insensitivity and data dependency analysis to systematically identify correct coordination-free scaling opportunities. We apply this analysis to create preconditions and mechanisms for coordination-free decoupling and partitioning, two fundamental vertical and horizontal scaling techniques. Manual rule-driven applications of decoupling and partitioning improve the throughput of 2PC by 5\u00d7 and Paxos by 3\u00d7, and match state-of-the-art throughput in recent work. These results point the way toward automated optimizers for distributed protocols based on correct-by-construction rewrite rules.<\/jats:p>","DOI":"10.1145\/3639257","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-25","source":"Crossref","is-referenced-by-count":6,"title":["Optimizing Distributed Protocols with Query Rewrites"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9922-1994","authenticated-orcid":false,"given":"David C.Y.","family":"Chu","sequence":"first","affiliation":[{"name":"University of California, Berkeley, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-1428-5024","authenticated-orcid":false,"given":"Rithvik","family":"Panchapakesan","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6658-6548","authenticated-orcid":false,"given":"Shadaj","family":"Laddad","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-3073-0844","authenticated-orcid":false,"given":"Lucky E.","family":"Katahanas","sequence":"additional","affiliation":[{"name":"Sutter Hill Ventures, Palo Alto, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-1880-1941","authenticated-orcid":false,"given":"Chris","family":"Liu","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-5943-9301","authenticated-orcid":false,"given":"Kaushik","family":"Shivakumar","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3567-801X","authenticated-orcid":false,"given":"Natacha","family":"Crooks","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7712-4306","authenticated-orcid":false,"given":"Joseph M.","family":"Hellerstein","sequence":"additional","affiliation":[{"name":"University of California, Berkeley &amp; Sutter Hill Ventures, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5256-7664","authenticated-orcid":false,"given":"Heidi","family":"Howard","sequence":"additional","affiliation":[{"name":"Azure Research, Microsoft, Cambridge, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Foundations of Databases","author":"Abiteboul Serge","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley. http:\/\/webdam.inria.fr\/Alice\/pdfs\/all.pdf"},{"key":"e_1_2_2_2_1","volume-title":"Revisiting Fast Practical Byzantine Fault Tolerance. CoRR","author":"Abraham Ittai","year":"2017","unstructured":"Ittai Abraham, Guy Gueta, Dahlia Malkhi, Lorenzo Alvisi, Ramakrishna Kotla, and Jean-Philippe Martin. 2017. Revisiting Fast Practical Byzantine Fault Tolerance. CoRR, Vol. abs\/1712.01367 (2017). arxiv: 1712.01367 http:\/\/arxiv.org\/abs\/1712.01367"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2019.2929793"},{"key":"e_1_2_2_4_1","unstructured":"Peter Alvaro Tom J Ameloot Joseph M Hellerstein William Marczak and Jan Van den Bussche. 2011a. A declarative semantics for Dedalus. UC Berkeley EECS Technical Report Vol. 120 (2011) 2011."},{"key":"e_1_2_2_5_1","volume-title":"Fifth Biennial Conference on Innovative Data Systems Research, CIDR 2011, Asilomar, CA, USA, January 9--12, 2011, Online Proceedings. 249--260","author":"Alvaro Peter","year":"2011","unstructured":"Peter Alvaro, Neil Conway, Joseph M. Hellerstein, and William R. Marczak. 2011b. Consistency Analysis in Bloom: a CALM and Collected Approach. In Fifth Biennial Conference on Innovative Data Systems Research, CIDR 2011, Asilomar, CA, USA, January 9--12, 2011, Online Proceedings. 249--260. http:\/\/cidrdb.org\/cidr2011\/Papers\/CIDR11_Paper35.pdf"},{"key":"e_1_2_2_6_1","volume-title":"Dedalus: Datalog in Time and Space","author":"Alvaro Peter","year":"2011","unstructured":"Peter Alvaro, William R. Marczak, Neil Conway, Joseph M. Hellerstein, David Maier, and Russell Sears. 2011c. Dedalus: Datalog in Time and Space. In Datalog Reloaded, Oege de Moor, Georg Gottlob, Tim Furche, and Andrew Sellers (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 262--281."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3106412"},{"key":"e_1_2_2_8_1","volume-title":"Boon Thau Loo, and Mohammad Sadoghi.","author":"Amiri Mohammad Javad","year":"2022","unstructured":"Mohammad Javad Amiri, Chenyuan Wu, Divyakant Agrawal, Amr El Abbadi, Boon Thau Loo, and Mohammad Sadoghi. 2022. The bedrock of bft: A unified platform for bft protocol design and implementation. arXiv preprint arXiv:2205.04534 (2022)."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535862"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477132.3483544"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3284764.3284767"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/209937.209958"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2011.10.003"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656877.2656890"},{"key":"e_1_2_2_15_1","volume-title":"The Bulletin of the Technical Committee on Data Engineering","volume":"38","author":"Carbone Paris","year":"2015","unstructured":"Paris Carbone, Asterios Katsifodimos, Stephan Ewen, Volker Markl, Seif Haridi, and Kostas Tzoumas. 2015. Apache flink: Stream and batch processing in a single engine. The Bulletin of the Technical Committee on Data Engineering, Vol. 38, 4 (2015)."},{"key":"e_1_2_2_16_1","doi-asserted-by":"crossref","unstructured":"David Chu Rithvik Panchapakesan Shadaj Laddad Lucky Katahanas Chris Liu Kaushik Shivakumar Natacha Crooks Joseph M. Hellerstein and Heidi Howard. 2024. Optimizing Distributed Protocols with Query Rewrites [Technical Report]. https:\/\/github.com\/rithvikp\/autocomp.","DOI":"10.1145\/3639257"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732279.2732285"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2391229.2391230"},{"key":"e_1_2_2_19_1","volume-title":"Proceedings of the 6th Conference on Symposium on Operating Systems Design I& Implementation -","volume":"6","author":"Dean Jeffrey","year":"2004","unstructured":"Jeffrey Dean and Sanjay Ghemawat. 2004. MapReduce: Simplified Data Processing on Large Clusters. In Proceedings of the 6th Conference on Symposium on Operating Systems Design I& Implementation - Volume 6 (San Francisco, CA) (OSDI'04). USENIX Association, USA, 10."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1331939.1331940"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/129888.129894"},{"key":"e_1_2_2_22_1","unstructured":"David J. DeWitt Robert H. Gerber Goetz Graefe Michael L. Heytens Krishna B. Kumar and M. Muralikrishna. 1986. GAMMA - A High Performance Dataflow Database Machine. In VLDB. 228--237."},{"key":"e_1_2_2_23_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--338. https:\/\/www.usenix.org\/conference\/nsdi20\/presentation\/ding"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/42282.42283"},{"key":"e_1_2_2_25_1","first-page":"209","article-title":"An Overview of The System Software of A Parallel Relational Database Machine GRACE","volume":"86","author":"Fushimi Shinya","year":"1986","unstructured":"Shinya Fushimi, Masaru Kitsuregawa, and Hidehiko Tanaka. 1986. An Overview of The System Software of A Parallel Relational Database Machine GRACE.. In VLDB, Vol. 86. 209--219.","journal-title":"VLDB"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/93605.98724"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3329120"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2020.13"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1755913.1755950"},{"key":"e_1_2_2_30_1","volume-title":"Conference on Innovative Data Systems Research (CIDR).(2023)","author":"Gupta Suyash","year":"2023","unstructured":"Suyash Gupta, Mohammad Javad Amiri, and Mohammad Sadoghi. 2023. Chemistry behind Agreement. In Conference on Innovative Data Systems Research (CIDR).(2023)."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815428"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3369736"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_2_2_34_1","volume-title":"Buug ra Gedik, and Scott Schneider","author":"Hirzel Martin","year":"2018","unstructured":"Martin Hirzel, Robert Soul\u00e9, Buug ra Gedik, and Scott Schneider. 2018. Stream Query Optimization. Springer International Publishing, 1--9."},{"key":"e_1_2_2_35_1","unstructured":"Heidi Howard and Ittai Abraham. 2020. Raft does not Guarantee Liveness in the face of Network Faults. https:\/\/decentralizedthoughts.github.io\/2020--12--12-raft-liveness-full-omission\/."},{"key":"e_1_2_2_36_1","volume-title":"Flexible paxos: Quorum intersection revisited. arXiv preprint arXiv:1608.06696","author":"Howard Heidi","year":"2016","unstructured":"Heidi Howard, Dahlia Malkhi, and Alexander Spiegelman. 2016. Flexible paxos: Quorum intersection revisited. arXiv preprint arXiv:1608.06696 (2016)."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3380787.3393681"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272996.1273005"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/Blockchain.2019.00048"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2020.19"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781638280439"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360549"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/279227.279229"},{"key":"e_1_2_2_44_1","unstructured":"Leslie Lamport. 2002. Specifying systems: the TLA language and tools for hardware and software engineers. (2002)."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592761.1592785"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/7239.7266"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2517350"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01536403"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477132.3483584"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699417"},{"key":"e_1_2_2_51_1","volume-title":"bridging theory and practice. Ph.,D. Dissertation","author":"Ongaro Diego","unstructured":"Diego Ongaro. 2014. Consensus : bridging theory and practice. Ph.,D. Dissertation. Stanford University."},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1986.6312888"},{"key":"e_1_2_2_53_1","unstructured":"George Pirlea. 2023. Errors found in distributed protocols. https:\/\/github.com\/dranov\/protocol-bugs-list."},{"key":"e_1_2_2_54_1","volume-title":"Hydroflow: A Model and Runtime for Distributed Systems Programming.","author":"Samuel Mingwei","year":"2021","unstructured":"Mingwei Samuel, Joseph M Hellerstein, and Alvin Cheung. 2021. Hydroflow: A Model and Runtime for Distributed Systems Programming. (2021)."},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","unstructured":"Bruhathi Sundarmurthy Paraschos Koutris and Jeffrey Naughton. 2021. Locality-Aware Distribution Schemes. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. https:\/\/doi.org\/10.4230\/LIPICS.ICDT.2021.22","DOI":"10.4230\/LIPICS.ICDT.2021.22"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477132.3483552"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2019.105901"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3236263"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2673577"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/tdsc.2014.2355848"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331595"},{"key":"e_1_2_2_62_1","unstructured":"Michael Whittaker. 2020. mwhittaker\/craq_bug. https:\/\/github.com\/mwhittaker\/craq_bug."},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476273"},{"key":"e_1_2_2_64_1","volume-title":"echnical Report]. arxiv","author":"Whittaker Michael","year":"2012","unstructured":"Michael Whittaker, Ailidani Ailijiang, Aleksey Charapko, Murat Demirbas, Neil Giridharan, Joseph M. Hellerstein, Heidi Howard, Ion Stoica, and Adriana Szekeres. 2021b. Scaling Replicated State Machines with Compartmentalization [Technical Report]. arxiv: 2012.15762 [cs.DC]"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.5070\/SR31154817"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2737958"},{"key":"e_1_2_2_67_1","unstructured":"Jianan Yao Runzhou Tao Ronghui Gu Jason Nieh Suman Jana and Gabriel Ryan. 2021. DistAI: Data-Driven Automated Invariant Learning for Distributed Protocols.. In OSDI. 405--421."},{"key":"e_1_2_2_68_1","volume-title":"Spark: Cluster Computing with Working Sets. In 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud 10)","author":"Zaharia Matei","year":"2010","unstructured":"Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2010. Spark: Cluster Computing with Working Sets. In 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud 10). USENIX Association, Boston, MA. https:\/\/www.usenix.org\/conference\/hotcloud-10\/spark-cluster-computing-working-sets"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522737"},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447802"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639257","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639257","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:18:18Z","timestamp":1755789498000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639257"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":70,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639257"],"URL":"https:\/\/doi.org\/10.1145\/3639257","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}