2025/09/08 by Guanzhou Hu, Hu, Guanzhou, Yiwei Chen +5
Computer Science · #Advanced Data Storage Technologies #Cloud Computing and Resource Management #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2509.07157
openalex publication_date 2025/09/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.