CS Paper Radar

MANTA: Unlocking DAG Flexibility in Asynchronous BFT

Mohan Yu, Chenlin Wu, Jianyu Niu, Cong Wang, Chenyuan Wu

cs.DC ·submitted 2026-10-25 16:18 UTC · v1
published

Abstract

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.

Comment
20 pages, 13 figures, Proceedings of the 24th USENIX Symposium on Networked Systems Design and Implementation 2027

Closest papers

Nearest neighbours by meaning across the whole index.

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.69
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

Exploring Adaptive Byzantine Quorum Systems to Improve Latency in the WAN

cs.DC ·2026-09-30 ·Linus Gnan, Rüdiger Kapitza, Christian Berger
published similarity 0.69
Abstract · Accepted at LADC 2026, the 15th Latin-American Symposium on Dependable and Secure Computing. 15 Pages

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.

0.20

Steelhead: Interleaving Partially Synchronous and Asynchronous Commit Rules on a Shared DAG

cs.DC cs.CR ·2026-09-24 ·Zeno De Angeli, Philipp Jovanovic, Lefteris Kokoris-Kogias, Markus Legner, Alberto Sonnino
theory similarity 0.67
Abstract

Dual-mode consensus protocols are fast when the network is partially synchronous and remain live under asynchrony. We introduce Steelhead, a dual-mode mechanism that composes a partially synchronous and an asynchronous commit rule over one DAG: every k-th round is decided by the asynchronous rule, whose leader a common coin reveals after the votes, and all other rounds by the partially synchronous rule. Every interval, validators replay the committed DAG under each candidate period, adopt the one with the fewest expected message delays, and fall back to k = 1 when the output stalls; the asynchronous rule applied to the coin rounds alone keeps the protocol live. Steelhead sends no message beyond the DAG's blocks, not even to agree on the period, and opens a coin only on the rounds that need a hidden leader. It is generic over pairs of DAG commit rules that share a committee; we instantiate it with Mysticeti and Mahi-Mahi at n >= 3f+1 and with the two variants of BlueBottle at n >= 5f+1. We prove it safe and live, and provide mechanized proofs in Lean 4. In simulation, Steelhead matches the partially synchronous protocol in a healthy network, stays close to the asynchronous one when network conditions stall the partially synchronous one, and adapts quickly in both directions.

0.26

Hydrozoan: Latency-Adaptive DAG Consensus under Mixed Byzantine and Crash Faults

cs.DC cs.CR ·2026-09-22 ·Qianyu Yu, Lefteris Kokoris-Kogias, Alberto Sonnino
theory similarity 0.65
Abstract

DAG-based consensus protocols can achieve great throughput and the optimal three-message-delay limit for n = 3f+1 consensus. While two-delay protocols exist, they pay with reduced resilience (requiring 5f+1-style committees) or rely on fallbacks that sacrifice the DAG's high throughput. This paper introduces Hydrozoan, the first DAG protocol with a dual commit path under a hybrid fault model of f Byzantine and c crashed validators, on n = 3f+c+2p+1 validators. Leaders commit in two message delays whenever at most p validators are faulty, and in three otherwise, with no extra messages, no view changes, and multiple leaders per round. Both paths are evaluated on the same DAG, using a novel graded indirect rule to reconcile them so that every honest validator reaches the same decision. We show that under geo-distributed conditions, which path is faster is a property of geography rather than the protocol, as rounds reaching a remote region cost far more than those that do not. The (f, c, p) knobs place the fast quorum where the deployment requires it, allowing a commit in two message delays. If misconfigured, Hydrozoan can still commit in three message delays: Hydrozoan commits on whichever path fires first. We also present Optimal-Hydrozoan, a variant that tolerates one more fault on the fast path, the first construction to match the known lower bound. The safety and liveness of both protocols are machine-checked in Lean 4. Our geo-distributed evaluation shows that Hydrozoan matches Mysticeti's throughput, commits ~25% faster when the fast quorum fits fast regions, and falls back to three message delays when it does not or past p faults, where existing two-delay protocols stall.

0.22

Sharpedo: Dual-Mode Uncertified DAG-Based Consensus Protocol

cs.DC ·2026-09-04 ·Zeno de Angeli
similarity 0.65
Abstract · MSc thesis, University College London, 2025. Supervised by Philipp Jovanovic and Alberto Sonnino

Mysticeti and Mahi-Mahi represent leading approaches to consensus protocols, leveraging a novel uncertified Directed Acyclic Graph data structure to achieve substantial performance benefits compared to prior work. Mysticeti and Mahi-Mahi differ in their underlying network assumptions, where the former makes assumptions about timing bounds for communication while the latter does not. Mysticeti trades robustness for lower levels of latency in ideal conditions, whereas Mahi-Mahi favours increased latency in order to ensure stronger progress guarantees in asynchronous settings. Although dual-mode protocols exist (i.e., protocols that can adapt do different network assumptions), none have been implemented to take full advantage of the novel data structure seen in the aforementioned protocols. Thus, our research project aims to trace the progression of consensus protocols, analyse how they address network assumptions constraints, and explore dual-mode protocols. Then, we present Sharpedo, the first dual-mode uncertified Directed Acyclic Graph consensus protocols which aims to achieve the best of both worlds: the high-performance of partially-synchronous protocols, while providing guarantees of progress even in asynchronous settings. Furthermore, Sharpedo integrates a novel dynamic scheduling mechanism resulting in improved system efficiency and performance optimization.

0.15

Barnacle: Adaptive Multi-Leader Scheduling for DAG-Based Consensus

cs.DC cs.CR ·2026-09-03 ·George Danezis, Zeno De Angeli, Alexandru Ianov Vitanov, Philipp Jovanovic, Lefteris Kokoris-Kogias +3 more
similarity 0.64
Abstract

In DAG-based consensus, all validators propose blocks concurrently, and designated leader blocks drive transaction commit. Having multiple leader slots per round cuts queuing latency, yet production deployments run a single leader because of head-of-line blocking: a slow leader stalls the pipeline for at least one leader timeout, and for several waves when its slot must wait for the fallback indirect decision rule. This risk grows with the leader count. We introduce Barnacle, an add-on that adapts the leader count at run time. Every interval, it measures on the agreed committed DAG the fraction of slots decided as commit by the direct rule, and drives the leader count with additive increase, multiplicative decrease. The measurement requires no extra messages and no cryptography, and is deterministic. Barnacle is generic over DAG protocols; we instantiate it on four protocols spanning the Byzantine (3f + 1, 5f + 1), crash-only (2c + 1), and mixed (5f + 3c + 1) fault models, with proven safety and liveness. Results show Barnacle matches the best static leader count in every regime: in a healthy network its latency is 6-13% lower than a single leader's, and under degradation it matches a single leader while remaining 35-56% below a static high count. We are currently collaborating with the Sui team to integrate Barnacle into the Sui blockchain.

0.35

Flamingo: On Load Balancing in DAG-based Consensus Protocols

cs.DC cs.DB ·2026-09-23 ·Zhen Ping Khor, Garvit Gupta, Mohammad Javad Amiri, Boon Thau Loo
similarity 0.64
Abstract

Distributed data management systems deployed in untrusted environments rely on Byzantine Fault-Tolerant (BFT) consensus protocols to tolerate malicious failures. DAG-based BFT protocols improve throughput by letting validators disseminate transactions concurrently and by scaling execution across multiple workers. However, imbalances in workload or resource capacity can still degrade performance significantly. This paper presents Flamingo, a load-balancing protocol for certified DAG-based BFT protocols that addresses imbalance at both the ordering and execution layers. At the ordering layer, Flamingo periodically migrates client accounts away from overloaded validators, adapting to skewed submissions and heterogeneous validator capacity while preserving correctness under Byzantine faults, with migrations taking effect only through the committed log. At the execution layer, Flamingo redistributes committed transactions across executor workers using a deterministic, order-preserving scheduler that balances load and minimizes cross-worker data movement, without centralized coordination or costly distributed commit. Built on top of Narwhal and Tusk, our prototype shows that Flamingo recovers throughput and latency under workload skew, validator heterogeneity, and shifting hotspots, adds negligible overhead when the system is balanced, and needs load balancing in both layers, since resolving only one shifts the bottleneck to the other.

0.17

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.64
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