Building State Machine Replication Using Practical Network Synchrony
Yiliang Wan Nitin Shivaraman Akshaye Shenoi Xiang Liu Tao Luo Jialin Li · 2025
Read Building State Machine Replication Using Practical Network Synchrony by Yiliang Wan Nitin Shivaraman Akshaye Shenoi Xiang Liu Tao Luo Jialin Li (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-2507-12792.txt.
Introduction
Yiliang Wan and co-authors rebuild a core distributed systems tool in a 2025 paper. State machine replication keeps many servers in perfect sync, so a service survives failures. Standard protocols assume the network may delay messages by unknown amounts, a safe but limiting view. The authors argue modern data centers can offer near-lockstep timing in the common case.
They built a network design with kernel-bypass links and loosened round lengths that holds rounds under two microseconds. On top of it sits their protocol, Chora. Chora pipelines many replication rounds at once and lets every server propose in parallel, with no extra coordination. In tests it beat leading single-leader protocols by 255 percent in throughput, and multi-leader ones by 109 percent.
Catalog record
| CREATOR | Yiliang Wan Nitin Shivaraman Akshaye Shenoi Xiang Liu Tao Luo Jialin Li |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 72 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-12792
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Building State Machine Replication Using Practical Network Synchrony Yiliang Wan Nitin Shivaraman Akshaye Shenoi Xiang Liu Tao Luo Jialin Li Abstract Distributed systems, such as state machine replication, are critical infrastructures for modern applications. Practical distributed protocols make minimum assumptions about the underlying network: They typically assume a partially synchronous or fully asynchronous network model. In this work, we argue that modern data center systems can be designed to provide strong synchrony properties in the common case, where servers move in synchronous lock-step rounds. We prove this hypothesis by engineering a practical design that uses a combination of kernel-bypass network, multithreaded architecture, and loosened round length, achieving a tight round bound under 2 μ \mu s. Leveraging our engineered networks with strong synchrony, we co-design a new replication protocol, Chora. Chora exploits the network synchrony property to efficiently pipeline multiple replication instances, while allowing all replicas to propose in parallel without extra coordination. Experiments show that Chora achieves 255% and 109% improvement in throughput over state-of-the-art single-leader and multi-leader protocols, respectively. 1 Introduction It is well-established that network synchrony assumptions fundamentally impact distributed systems designs. While a synchronous network simplifies protocol designs, practical distributed systems only assume a weaker partially synchronous [ 29 , 22 , 25 , 4 , 40 ] or fully asynchronous network model [ 27 , 7 , 36 ] . The rationale is completely justified — strong synchrony assumptions are impossible to guarantee in any realistic deployment. But can we provide stronger synchrony properties in the common case ? Traditionally, partially synchronous networks assume the network exhibits periods of synchrony; this synchrony implies the existence of a bound on message delivery and processing latency. The bound could be loose, as long as it is finite. We are, however, interested in a stronger form of synchrony, where message delivery and processing across all servers exhibit low variance in latency. Such synchronous property allows us to divide physical time into “rounds”; in each round, each server sends and receives messages, makes transitions in its state machine, and synchronously moves to the next round. With low variance in message latencies, we can set a tight bound on the round duration such that all servers complete each round with high probability while having high resource utilization. This “lock-step” style of distributed computation is highly reminiscent of traditional synchronous distributed protocols, albeit with probabilistic guarantees. In this work, we demonstrate that practical networks can be designed and engineered to provide such a level of synchrony in the common case. Time synchronization protocols, such as NTP [ 32 ] and PTP [ 20 ] , are commonly deployed to provide accurate clock synchronization ; distributed systems can leverage kernel-bypassed stacks [ 12 , 1 , 41 ] and virtualized hardware device queues [ 30 , 39 ] to achieve low and predictable I/O processing latency. A multithreaded software architecture can isolate the protocol critical path into a streamlined core with highly deterministic performance. A blend of these solutions enable a cross-stack system design that offers our desired synchrony properties among distributed servers. Critically, our synchrony model does not require equal link delays, a much harder task for practical networks; instead, we only demand low variance in message delivery and protocol processing speed on each server. Our cross-stack design enables synchronized rounds among five cluster servers with a tight latency bound under 2 \mu s. Why does our stronger form of synchrony matter for distributed protocols? Traditionally, protocols only leverage network synchrony to ensure liveness properties [ 11 ] . In this work, we take the more extreme position: Stronger synchrony can also improve distributed protocol performance. While prior work has demonstrated that synchronized clocks can improve read-only operation performance in distributed transactions [ 6 ] and replication [ 3 ] , we show that our synchrony model can accelerate arbitrary workloads of a distributed protocol. We take state machine replication [ 34 ] as a concrete protocol instance. Our synchronized replica rounds permit all replicas to propose in each round, while naturally remove the extra coordination overhead resulted from such multi-leader design, a major drawback in prior leaderless protocols [ 26 , 28 ] . Lock-step processing also enables pipelined replication instances in a coordinated, streamlined fashion: Each protocol message serves concurrently as a new proposal and an acknowledgement to proposals in prior rounds. The resulting protocol could achieve O(1) amortized message complexity without compromising latency. The above insights motivate us to propose a new replication protocol, Chora. Chora is a state machine replication protocol co-designed with a network layer that is engineered to provide our stronger synchrony properties. Chora replicas proceed in synchronous lock-step rounds in normal operation. Each replica can propose commands, acknowledge prior proposals, and commit commands using a single broadcast message within a single round. Replicas also process events across multiple log slots in well-coordinated order, minimizing idle resources on any replica. Chora thus enables a fully pipelined protocol with tightly “clocked” stages, committing up to N proposals in each round while not compromising end-to-end latency, where N is the replica number. We evaluated the performance of Chora on a testbed with up to five replica servers. Chora achieves 255% and 109% higher throughput than Multi-Paxos [ 22 ] and Mencius [ 26 ] in time-slotted mode and over 130% and 35% higher throughput in responsive mode, all with virtually zero impact on latency. We also demonstrate the impact of selecting optimal round length on the throughput and communication efficiency. 2 Background and Related Work In this paper, we consider the problem of state machine replication (SMR) [ 34 ] , in which a set of replica servers applies a series of deterministic operations to a state machine. A correct SMR protocol guarantees linearizability [ 15 ] , even when a subset of replicas fails. In this work, we assume all replicas follow the protocol, and can only fail by crashing. SMR protocols have been widely deployed to provide strong fault tolerance guarantees in distributed systems [ 3 , 6 , 16 , 2 ] . SMR protocols Most commonly deployed SMR protocols are leader-based [ 22 , 38 , 25 , 29 ] , where one replica is elected as a designated leader. All clients forward their requests first to the leader replica. The leader is responsible for ordering the operations, and replicating its ordered operation sequence to other replicas. To guarantee protocol safety, the leader collects quorum acknowledgements before committing and replying to clients. Leader-based SMR protocols have two main weaknesses. First, the leader replica limits the overall protocol throughput. Second, in wide area deployments, clients which locate far from the leader suffer longer replication latency. Multi-leader replication protocols [ 26 , 28 , 37 , 35 ] address the issue by allowing concurrent request proposers. Specifically, Mencius [ 26 ] partitions the operation log space across proposers, EPaxos [ 28 , 37 ] leverages operation dependency graph to detect ordering conflicts and resolve them in a slow path, while Insanely Scalable SMR [ 35 ] provides a generic construction to turn leader-driven protocols into multi-leader ones for better scalability. Network models Prior SMR protocols commonly assume a partially synchronous [ 10 ] network model.