Crossword : Adaptive Consensus for Dynamic Data-Heavy Workloads DOI: xxxxxxx.xxxxxxx ISBN: 978-1-4503-xxxx-x/xxxx/xx

Guanzhou Hu, Yiwei Chen, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau · 2025

Read Crossword : Adaptive Consensus for Dynamic Data-Heavy Workloads DOI: xxxxxxx.xxxxxxx ISBN: 978-1-4503-xxxx-x/xxxx/xx by Guanzhou Hu, Yiwei Chen, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-07157.txt.

Introduction

Data-heavy cloud workloads are the target of Crossword, a 2025 consensus protocol from Guanzhou Hu and 3 co-authors. Consensus protocols let many machines agree on the same data even when messages vary in size. Large payloads can clog the network at random moments, and older protocols assign fixed roles that cannot adapt when traffic changes.

Crossword codes each data item with erasure coding, which splits data into shards that can rebuild the whole from a subset. It then shifts how shards are assigned and how many machines must agree, based on live workload and network state. A lazy gossip scheme handles leader failure with little cost. In tests it matched the best older protocols in calm settings and beat them by up to 2.3 times under changing loads. A trial inside CockroachDB lifted total throughput as well.

Catalog record

CREATORGuanzhou Hu, Yiwei Chen, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-07157

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Crossword : Adaptive Consensus for Dynamic Data-Heavy Workloads DOI: xxxxxxx.xxxxxxx ISBN: 978-1-4503-xxxx-x/xxxx/xx Guanzhou Hu, Yiwei Chen, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau Abstract . We present Crossword , a flexible consensus protocol for dynamic data-heavy workloads , a rising challenge in the cloud where replication payload sizes span a wide spectrum and introduce sporadic bandwidth stress . Crossword applies per-instance erasure coding and distributes coded shards intelligently to reduce critical-path data transfer significantly when desirable . Unlike previous approaches that statically assign shards to servers, Crossword enables an adaptive tradeoff between the assignment of shards and quorum size in reaction to dynamic workloads and network conditions, while always retaining the availability guarantee of classic protocols. Crossword handles leader failover gracefully by employing a lazy follower gossiping mechanism that incurs minimal impact on critical-path performance. We implement Crossword (along with relevant protocols) in Gazette , a distributed, replicated, and protocol-generic key-value store written in async Rust. We evaluate Crossword comprehensively to show that it matches the best performance among previous protocols (MultiPaxos, Raft, RSPaxos, and CRaft) in static scenarios, and outperforms them by up to 2.3x under dynamic workloads and network conditions. Our integration of Crossword with CockroachDB brings 1.32x higher aggregate throughput to TPC-C under 5-way replication. We will open-source Gazette upon publication. 1. Introduction Consensus protocols are at the heart of most fault-tolerant distributed systems. They enable the fundamental operation of consistent replication, often with a log of state machine commands ( Schneider 1990 ; Ongaro and Ousterhout 2014 ) , across machines over an asynchronous network ( Lamport 1998 ) . Protocols such as MultiPaxos ( Lamport 2001 ) and Raft ( Ongaro and Ousterhout 2014 ) prove indispensable in guarding the critical data of widely-deployed distributed systems, including but not limited to distributed file systems ( Ghemawat et al. 2003 ; Hildebrand and Serenyi 2023 ; Cao et al. 2018 ) , object stores ( Barr 2023 ; Hadoop 2023 ) , coordination services ( Burrows 2006 ; Hunt et al. 2010 ; Kreps et al. 2011 ; Redpanda 2024 ) , cluster managers ( etcd 2023 ; Inc. 2023 ; Rensin 2015 ; Xu et al. 2022 ) , and cloud databases ( Corbett et al. 2013 ; Shute et al. 2013 ; VanBenschoten et al. 2022 ; Huang et al. 2020 ; ScyllaDB 2023 ) . Due to the common assumption that consensus workloads carry small values (e.g., ~100 byte state machine commands ( etcd 2023 ) ), network transport delay has been considered the major bottleneck in consensus protocols ( Lamport 2001 ) . Previous protocols were thus mainly designed to reduce message round-trips ( Lamport 2001 ; Oki and Liskov 1988 ; Ongaro and Ousterhout 2014 ; Lamport 2006 ) and minimize communication delay ( Lamport 2005 ; Mao et al. 2008 ; Moraru et al. 2013 ; Tollman et al. 2021 ; Jiang et al. 2023 ; Ngo et al. 2020 ; Ganesan et al. 2020 ; Ganesan et al. 2021 ) , largely neglecting bandwidth constraints on the critical path. Unfortunately, bandwidth constraints can no longer be neglected as modern distributed systems place increasingly heavier workloads onto consensus protocols. For example, cloud databases ( Corbett et al. 2013 ; Shute et al. 2013 ; VanBenschoten et al. 2022 ; Huang et al. 2020 ; ScyllaDB 2023 ) use Paxos or Raft to replicate redo/undo actions, each carrying KBs or even MBs of data per operation. When consensus instances carry large payloads, broadcasting them over the network and persisting them durably stresses the bandwidth aspect of the system. Figure 1 shows a payload size profile of the Raft module in two modern databases, TiDB ( Huang et al. 2020 ) and CockroachDB ( VanBenschoten et al. 2022 ) , running TPC-C ( Leutenegger and Dias 1993 ) . A considerable portion of the payloads are large ( \geqslant 4KB) and span a wide range of up to 290KB and 63MB, respectively. The dynamicity and diversity in hardware environment conditions and workload sizes further complicate the problem: small payloads are likely delay-bounded, while large payloads in a bandwidth-limited environment necessitate optimizations that reduce data size. Figure 1 . Raft replication payload size CDF in modern cloud databases. Profiled by running 200-warehouses TPC-C. Previous research has integrated consensus protocols with erasure coding ( Reed and Solomon 1960 ; Huang et al. 2012 ) , allowing the leader node to transform the payload into shards, each having a fractional size of the original. These protocols, including RSPaxos ( Mu et al. 2014 ) , CRaft ( Wang et al. 2020 ) and variants ( Ren et al. 2022a ; Xu et al. 2021 ; Jia et al. 2022 ; Zhang et al. 2023 ) , reduce bandwidth pressure by sending exactly one shard to each follower. However, they provide a degraded availability guarantee, exhibit ungraceful leader failover, and provide no flexibility in reaction to dynamic workloads and hardware conditions. Instead of fixing the number of coded shards assigned per server to one, we treat it as a new dimension in the design space. Specifically, we establish an availability-preserving tradeoff between the number of shards per server ( c ) and the minimum accept quorum size ( q ). Using this intuitive but powerful result, we propose Crossword , a bandwidth-adaptive consensus protocol that operates dynamically on the set of valid [c,q] configurations, reducing the data transfer volume in bandwidth-constrained cases and minimizing the quorum size in delay-dominant scenarios. Moreover, Crossword employs a follower gossiping mechanism to keep followers updated without interfering with critical-path operations, permitting graceful handling of leader failover. Summary of Contributions . 1 We recognize the increasing significance of dynamic data-heavy consensus workloads, and demonstrate the insufficiency of previous protocols under such workloads. 2 We propose Crossword , the first consensus protocol to our knowledge that establishes a runtime-dynamic tradeoff between data volume and quorum size using erasure coding; Crossword retains the availability guarantee and graceful failover behavior of classic protocols. 3 We build Gazette , a protocol-generic replicated key-value store, and implement six consensus protocols in a sum of 27.3k lines of async Rust. 4 We evaluate Crossword comprehensively to show that Crossword matches the best performance among previous protocols in static scenarios, and outperforms MultiPaxos/Raft by up to 2.3x and RSPaxos/CRaft by up to 1.9x under dynamic mixed workloads. Crossword recovers promptly after leader failover and sustains a consistent performance gain under macro-benchmarks. Integration with CockroachDB ( VanBenschoten et al. 2022 ) delivers 1.32x higher throughput to 200-warehouses TPC-C under 5-way replication. 5 We append a \textrm{TLA}^{+} specification. The rest of this paper is organized as follows. § 2 details background and motivation. § 3 and § 4 presents design and implementation, respectively. § 5 presents evaluation results. § 6 discusses related work and § 7 concludes. 2. Background and Motivation We provide background context and motivation. 2.1. The Consensus Problem Consensus is a fundamental problem that confronts any distributed system seeking consistency. We consider the common fail-stop model with an asynchronous network ( Lamport 2001 ) . State Machine Replication (SMR) . Given the ubiquity of the state machine approach to designing fault-tolerant distributed systems ( Schneider 1990 ) ,

Read the complete text