CS Paper Radar

Exploring Adaptive Byzantine Quorum Systems to Improve Latency in the WAN

Linus Gnan, Rüdiger Kapitza, Christian Berger

cs.DC ·submitted 2026-09-30 13:28 UTC · v1
published

Abstract

Quorum systems enforce strict consistency in Byzantine fault-tolerant (BFT) state machine replication: Before a value is decided, a subset of replicas (called quorum) must exchange votes for the value. In wide-area networks, the size and composition of a quorum determines the speed at which replicas can make progress and thus impacts the latency perceived by clients. A variety of quorum constructions has been proposed, e.g., threshold, weighted, grid and others, but the literature offers little in the way of an apples-to-apples comparison. Each construction typically lives inside a different protocol implementation, so the influence of quorum design on client latency cannot be easily separated from other implementation effects, especially the use of optimization techniques. In this paper, we close that gap by extending BFT-SMaRt with a modular quorum-system abstraction that allows a variety of quorum constructions to live inside the same framework and interact with the same set of optimization techniques. Via our framework, we explore the impact of different quorum system constructions on client-observed latency in wide-area BFT replication using network simulation.

Comment
Accepted at LADC 2026, the 15th Latin-American Symposium on Dependable and Secure Computing. 15 Pages

Closest papers

Nearest neighbours by meaning across the whole index.

Breaking Fault Lines: Unifying TEE-Assisted BFT Consensus in Partially Trusted Worlds

cs.DC ·2026-09-09 ·Xiaoqing Wen, Tong Liu, Jianyu Niu, Jialin Li, Cong Wang +2 more
published similarity 0.71
Abstract · Accepted to EuroSys 2027

This paper revisits TEE-assisted BFT under a universal partial-TEE model, where an arbitrary subset of replicas execute inside TEEs while the remaining replicas operate without hardware trust guarantees. We show that heterogeneous trust changes the structure of quorum formation and fault tolerance. In particular, we derive a tight resilience bound f < max {n/3, m/2}, where n is the total number of replicas and m is the number of TEE-enabled replicas. The result reveals a sharp threshold phenomenon: TEEs improve fault tolerance only once they exceed two-thirds of the deployment. Guided by this characterization, we introduce two protocol principles: (1) a dual-quorum construction that safely combines TEE-only and mixed quorums, and (2) a TEE-leader fast path that leverages hardware-enforced non-equivocation to reduce both consensus and view-change latency. We realize these ideas in Raftel, which is, to our knowledge, the first HotStuff-style BFT protocol designed explicitly for arbitrary partial-TEE deployments, and in chained-Raftel, a pipelined variant that further accelerates mixed-trust execution. We implement both protocols atop Intel SGX and evaluate them in LAN and WAN environments. Our results show that Raftel achieves up to 625 TPS with sub-670 ms latency in WAN settings, outperforming HotStuff by up to 308 TPS in throughput while approaching the performance of fully TEE-assisted protocols.

0.26

MANTA: Unlocking DAG Flexibility in Asynchronous BFT

cs.DC ·2026-10-25 ·Mohan Yu, Chenlin Wu, Jianyu Niu, Cong Wang, Chenyuan Wu
published similarity 0.69
Abstract · 20 pages, 13 figures, Proceedings of the 24th USENIX Symposium on Networked Systems Design and Implementation 2027

DAG-based BFT protocols marked a shift in consensus design by replacing single-leader proposal paths with concurrent block proposals linked through a shared graph, where references encode consensus evidence. However, under heterogeneous wide-area networks (WANs), existing designs suffer from prolonged rounds and degraded performance due to straggler effects. The root cause is rigid round advancement: replicas move in synchronized rounds, waiting for enough references from the previous round before advancing. We propose a flexible DAG growth framework for asynchronous BFT consensus. Our key observation is that while reference quorums are necessary for safety and liveness, they need not block every round advancement. Instead, the connectivity required for commitment can be accumulated across rounds. Within the framework, we instantiate MANTA, which combines flexible DAG growth to advance by relaxing round synchronization and flexible coin to trigger leader election and finality earlier. Experiments on heterogeneous WAN deployments show that MANTA reduces latency by approximately 30%-70% in our evaluation.

0.32

Optimality and Trade-offs in Fast BFT SMR (Extended Version)

cs.DC ·2026-08-20 ·Neil Giridharan, Minh Tung Nguyen, Ittai Abraham, Allen Clement, Natacha Crooks +1 more
similarity 0.68
Abstract

Fast state-machine replication (SMR) protocols in the crash-fault setting have attracted significant interest in both academia and industry. This interest stems from their advantages over leader-based protocols, including low execution latency for non-conflicting commands, high throughput, improved availability, and increased fairness. While Fast SMR is well studied in the crash-fault setting, the Byzantine fault-tolerant (BFT) setting remains much less understood, with only a small number of existing Fast BFT SMR protocols. In this paper, we present tight upper and lower bounds on the replication factor required for Fast BFT SMR. We also present a suboptimal protocol that illustrates a trade-off between replication factor and recovery efficiency.

0.30

Pangolin: Efficient DAG-based BFT State-Machine Replication with TEE-Accelerated Commitment

cs.DC ·2026-10-19 ·Paul Franke-Bergmann, Maya Kuhlmann, Alexander Heß, Marc Leinweber, Rüdiger Kapitza +3 more
similarity 0.68
Abstract · 28 pages

Currently many Byzantine fault-tolerant (BFT) protocols use directed acyclic graphs (DAGs) to let replicas propose blocks of requests in parallel for improved throughput. Yet, the existing DAG-based designs mainly consider the atomic-broadcast layer: They typically do not describe an efficient client interaction layer, their garbage collection is either unspecified or relies on trusted external storage, and the lowest-latency designs rely on timing assumptions that may be violated in geo-distributed deployments. In this paper, we propose the Pangolin protocol: It introduces a novel low-latency DAG-based atomic broadcast layer and completes it into an efficient state-machine replication (SMR) framework. To preserve system throughput, clients issue requests to a single replica and verify replies efficiently via compact execution proofs. Furthermore, Pangolin introduces a new garbage-collection scheme for DAGs which bounds memory usage even under full asynchrony. Pangolin leverages trusted execution environments to tolerate f Byzantine faults with only n >= 2f + 1 replicas and accelerates vertex commitments significantly: Broadcasting certified vertices requires only a single communication step, and commit rules are refined to commit both frequently and early without revealing the coin-elected anchor. This way, Pangolin overtakes the fastest partially synchronous DAG protocols while being live under asynchrony: In our evaluation, Pangolin achieves an average 1.27x (up to 1.52x) latency speedup over Mysticeti.

0.23

Seamless Reconfiguration for DAG-BFT (Technical Report)

cs.DC ·2026-10-01 ·Michael Yiqing Hu, Leander Jehl, Paul Franke-Bergmann, Jialin Li, Christian Berger
published similarity 0.66
Abstract · Accepted to OPODIS 26

Byzantine Atomic Broadcast in Asynchronous networks has been studied extensively for decades. In a fully asynchronous system with even one possible crash failure, the FLP impossibility result rules out deterministic consensus, motivating randomized protocols that achieve termination with probability one. More recently, DAG-Rider popularized a new abstraction in which processes continuously reliably broadcast blocks to construct a Directed Acyclic Graph (DAG) and then locally derive a total order using a randomized perfect coin. This separation of dissemination from ordering has renewed interest in asynchronous DAG-based Byzantine Fault Tolerance (BFT) and inspired numerous protocols that improve expected latency or throughput. Reconfiguration, however, remains largely unexplored. Existing DAG-based BFT protocols generally assume a static set of processes, whereas deployed systems must occasionally add or remove nodes in response to operational demands. Existing solutions are not seamless; they either pause the system or delay membership changes until a predetermined epoch boundary. This may be impractical and can introduce downtime. A single agreed switching round is difficult to use seamlessly: by the time processes learn it, the dissemination layer may already have advanced beyond it. In this work, we present a seamless reconfiguration protocol for Asynchronous DAG-based Byzantine Atomic Broadcast. Our protocol allows the DAG to continue growing while the membership and corresponding quorum thresholds change, without halting the system. To the best of our knowledge, ours is the first protocol to provide seamless reconfiguration for DAG-based Byzantine atomic broadcast in a fully asynchronous network.

0.17

On the Robustness of Gossip Protocols in Modern Blockchains

cs.CR ·2026-10-15 ·Wenting Li, Jannik Albrecht, Frederik Armknecht, Ghassan Karame
top venue similarity 0.65
Abstract · Accepted at IEEE Symposium on Security and Privacy (IEEE SP), 2027

Modern platforms such as Ethereum and Polkadot nowadays execute Byzantine fault-tolerant consensus protocols over large validator committees, often comprising hundreds of nodes. At this scale, complete graph topologies for connecting nodes are impractical, leading systems to adopt various gossip mechanisms, often in an ad hoc manner. In this paper, we study the robustness of widely deployed gossip protocols used in committee-based blockchains against realistic network adversaries. We show, both analytically and through extensive empirical measurements, that the graph parameters commonly chosen to instantiate random graphs are insufficient to guarantee that enough honest nodes receive consensus messages for quorum formation in existing protocols. Motivated by this finding, we empirically assess the robustness of Bitcoin's Erdős-Rényi (ER) graphs, Polkadot's grid topology, Ethereum's GossipSub, and Solana's chunk- and tree-based disseminations. Our results reveal surprising tradeoffs: Solana's dynamic trees are bandwidth-efficient in benign settings but fragile under adaptive attacks; Polkadot's grid achieves strong robustness at the cost of high bandwidth overhead; GossipSub is both bandwidth-efficient and resilient to adaptive adversaries, yet highly sensitive to parameter choices; and ER graphs provide a strong robustness-efficiency tradeoff, e.g., when the (average) fanout degree exceeds 15 for networks up to 5000 nodes.

0.29

Adaptive Switching Between Leader-Based and Leaderless BFT Protocols

cs.DC ·2026-09-25 ·Sudip Bhujel, Yue Li, Ning Zhang, Y. Thomas Hou, Wenjing Lou +1 more
similarity 0.65
Abstract

Byzantine fault-tolerant (BFT) protocols are known for providing operational consistency and resilience in distributed systems. However, evolving network conditions, often driven by the network's inherent dynamism or adversarial influence, make it suboptimal to rely on a static protocol at all times. Existing BFT protocol adaptation solutions switch only among leader-based protocols and coordinate each switch through a separate consensus round, leaving them ineffective at handling severe asynchrony or situations in which an adaptive adversary targets the network's leader. We propose BFTide, a protocol adaptation architecture that enables a BFT system to intelligently and swiftly switch to a suitable protocol as network conditions shift. BFTide integrates a novel protocol switching layer that embeds protocol transition logic into the ongoing BFT operation, enabling safe and low-overhead transitions between partially synchronous leader-based protocols and asynchronous leaderless protocols. It further incorporates an offline-trained reinforcement learning policy that allows nodes to propose protocols at runtime based on observed system metrics. Experimental results show that BFTide reduces transaction latency under adverse network conditions compared with static BFT protocols and the state-of-the-art BFT protocol adaptation scheme BFTBrain (NSDI'25), while maintaining comparable throughput. The switching layer adds a modest 10-21% overhead to median latency when idle and requires no separate consensus round per switch.

0.13

KCensus: Synthesizing Latency-Optimal Consensus Fast Paths (Extended Version)

cs.DC ·2026-09-25 ·Clément Burgelin, Antoine Murat, Gal Sela, Marcos K. Aguilera, Rachid Guerraoui
published similarity 0.65
Abstract · 38 pages, 15 figures. Extended version of the paper to appear in the 22nd European Conference on Computer Systems (EuroSys '27), Rabat, Moro…

Strongly consistent geo-replication often relies on fast paths to reduce latency in the common case of no failures or contention. Existing fast-path schemes, however, are ad hoc and restrictive: each corresponds to a point in a broad design space shaped by network topology, workload, and latency objective, so no single scheme works best across settings. This paper looks at fast-path schemes from a new perspective, as mechanisms that spread knowledge about proposals. With this view, we identify a fundamental condition on the spread of knowledge for a fast-path scheme to work. We then introduce KCensus, a framework that turns this condition into an optimization problem, synthesizing new fast-path schemes that are optimal for a given setting. We use KCensus to build a geo-replicated key-value store and evaluate it across AWS regions. Our system outperforms competing protocols, with up to 16% lower average latency.

0.57