{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T22:04:05Z","timestamp":1778537045050,"version":"3.51.4"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:p>State machine replication protocols, like MultiPaxos and Raft, are a critical component of many distributed systems and databases. However, these protocols offer relatively low throughput due to several bottlenecked components. Numerous existing protocols fix different bottlenecks in isolation but fall short of a complete solution. When you fix one bottleneck, another arises. In this paper, we introduce compartmentalization, the first comprehensive technique to eliminate state machine replication bottlenecks. Compartmentalization involves decoupling individual bottlenecks into distinct components and scaling these components independently. Compartmentalization has two key strengths. First, compartmentalization leads to strong performance. In this paper, we demonstrate how to compartmentalize MultiPaxos to increase its throughput by 6\u00d7 on a write-only workload and 16\u00d7 on a mixed read-write workload. Unlike other approaches, we achieve this performance without the need for specialized hardware. Second, compartmentalization is a technique, not a protocol. Industry practitioners can apply compartmentalization to their protocols incrementally without having to adopt a completely new protocol.<\/jats:p>","DOI":"10.14778\/3476249.3476273","type":"journal-article","created":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T16:46:23Z","timestamp":1635353183000},"page":"2203-2215","source":"Crossref","is-referenced-by-count":20,"title":["Scaling replicated state machines with compartmentalization"],"prefix":"10.14778","volume":"14","author":[{"given":"Michael","family":"Whittaker","sequence":"first","affiliation":[{"name":"UC Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ailidani","family":"Ailijiang","sequence":"additional","affiliation":[{"name":"Microsoft"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aleksey","family":"Charapko","sequence":"additional","affiliation":[{"name":"University of New Hampshire"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Murat","family":"Demirbas","sequence":"additional","affiliation":[{"name":"University at Buffalo"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neil","family":"Giridharan","sequence":"additional","affiliation":[{"name":"UC Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph M.","family":"Hellerstein","sequence":"additional","affiliation":[{"name":"UC Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Heidi","family":"Howard","sequence":"additional","affiliation":[{"name":"University of Cambridge"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ion","family":"Stoica","sequence":"additional","affiliation":[{"name":"UC Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adriana","family":"Szekeres","sequence":"additional","affiliation":[{"name":"VMWare"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,10,27]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. A Brief Introduction of TiDB. https:\/\/pingcap.github.io\/blog\/2017-05-23-perconalive17\/. Accessed: 2019-10-21.  [n.d.]. A Brief Introduction of TiDB. https:\/\/pingcap.github.io\/blog\/2017-05-23-perconalive17\/. Accessed: 2019-10-21."},{"key":"e_1_2_1_2_1","unstructured":"[n.d.]. Global data distribution with Azure Cosmos DB - under the hood. https:\/\/docs.microsoft.com\/en-us\/azure\/cosmos-db\/global-dist-under-the-hood. Accessed: 2019-10-21.  [n.d.]. Global data distribution with Azure Cosmos DB - under the hood. https:\/\/docs.microsoft.com\/en-us\/azure\/cosmos-db\/global-dist-under-the-hood. Accessed: 2019-10-21."},{"key":"e_1_2_1_3_1","unstructured":"[n.d.]. Lightweight transactions in Cassandra 2.0. https:\/\/www.datastax.com\/blog\/2013\/07\/lightweight-transactions-cassandra-20. Accessed: 2019-10-21.  [n.d.]. Lightweight transactions in Cassandra 2.0. https:\/\/www.datastax.com\/blog\/2013\/07\/lightweight-transactions-cassandra-20. Accessed: 2019-10-21."},{"key":"e_1_2_1_4_1","unstructured":"[n.d.]. Raft Replication in YugaByte DB. https:\/\/www.yugabyte.com\/resources\/raft-replication-in-yugabyte-db\/. Accessed: 2019-10-21.  [n.d.]. Raft Replication in YugaByte DB. https:\/\/www.yugabyte.com\/resources\/raft-replication-in-yugabyte-db\/. Accessed: 2019-10-21."},{"key":"e_1_2_1_5_1","volume-title":"WPaxos: Wide Area Network Flexible Consensus","author":"Ailijiang Ailidani","year":"2019","unstructured":"Ailidani Ailijiang , Aleksey Charapko , Murat Demirbas , and Tevfik Kosar . 2019. WPaxos: Wide Area Network Flexible Consensus . IEEE Transactions on Parallel and Distributed Systems ( 2019 ). Ailidani Ailijiang, Aleksey Charapko, Murat Demirbas, and Tevfik Kosar. 2019. WPaxos: Wide Area Network Flexible Consensus. IEEE Transactions on Parallel and Distributed Systems (2019)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2017.35"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2318857.2254766"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2014.41"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SRDS.2012.66"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1298455.1298487"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281103"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/3357062.3357073"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452834"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491245"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/3388242.3388265"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/945445.945450"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.OPODIS.2016.25"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/3307441.3307445"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1924908.1924910"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/279227.279229"},{"key":"e_1_2_1_21_1","first-page":"18","article-title":"Paxos made simple","volume":"32","author":"Lamport Leslie","year":"2001","unstructured":"Leslie Lamport . 2001 . Paxos made simple . ACM Sigact News 32 , 4 (2001), 18 -- 25 . Leslie Lamport. 2001. Paxos made simple. ACM Sigact News 32, 4 (2001), 18--25.","journal-title":"ACM Sigact News"},{"key":"e_1_2_1_22_1","unstructured":"Leslie Lamport. 2005. Generalized consensus and Paxos. (2005).  Leslie Lamport. 2005. Generalized consensus and Paxos. (2005)."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-006-0005-x"},{"key":"e_1_2_1_24_1","unstructured":"Barbara Liskov and James Cowling. 2012. Viewstamped replication revisited. (2012).  Barbara Liskov and James Cowling. 2012. Viewstamped replication revisited. (2012)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855741.1855767"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2517350"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2670979.2671001"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2482626.2482663"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2643634.2643666"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/3323234.3323240"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2789770.2789774"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25959-3_11"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.10.002"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352125"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3386134"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/3388242.3388295"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855807.1855818"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213838"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2673577"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1251254.1251261"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Michael Whittaker Ailidani Ailijiang Aleksey Charapko Murat Demirbas Neil Giridharan Joseph M. Hellerstein Heidi Howard Ion Stoica and Adriana Szekeres. 2020. Scaling Replicated State Machines with Compartmentalization [Technical Report]. arXiv:2012.15762 [cs.DC]  Michael Whittaker Ailidani Ailijiang Aleksey Charapko Murat Demirbas Neil Giridharan Joseph M. Hellerstein Heidi Howard Ion Stoica and Adriana Szekeres. 2020. Scaling Replicated State Machines with Compartmentalization [Technical Report]. arXiv:2012.15762 [cs.DC]","DOI":"10.14778\/3476249.3476273"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447865.3457962"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3269981"},{"key":"e_1_2_1_44_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\/3476249.3476273","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:13:39Z","timestamp":1672222419000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3476249.3476273"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7]]},"references-count":44,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["10.14778\/3476249.3476273"],"URL":"https:\/\/doi.org\/10.14778\/3476249.3476273","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,7]]}}}