Source-linked AI summary
MANTA: Unlocking DAG Flexibility in Asynchronous BFT
Mohan Yu, Chenlin Wu, Jianyu Niu, Cong Wang, Chenyuan Wu
TL;DR
In heterogeneous WANs, rigid round advancement makes asynchronous DAG-based BFT protocols wait for quorum references and stragglers. The paper develops flexible DAG growth and instantiates MANTA with flexible growth and flexible coin to support earlier progress and commitment. MANTA consistently outperforms prior asynchronous DAG-based BFT protocols in fault-free heterogeneous deployments, reducing latency by at least 30% while preserving robustness.
Problem
Method
The framework decouples connectivity requirements from round advancement, and MANTA combines flexible growth with flexible coin to pursue earlier progress and commitment.
Source: §1 · p. 2Results
MANTA consistently outperforms prior asynchronous DAG-based BFT protocols under fault-free heterogeneous deployments, reducing latency by at least 30% while preserving robustness.
Source: §8 · p. 12Takeaways & Limitations
MANTA's flexible growth and coin support earlier connectivity and commitment while preserving worst-case safety and liveness.
Source: §1 · p. 2A lower reference threshold may disadvantage slow replicas, while τcand trades off early recovery against worst-case latency under Byzantine behavior.
Source: §6.4 · p. 12
Abstract
from arXiv · showhide
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.
1 Introduction
Rigid per-round quorum requirements make asynchronous DAG protocols wait for stragglers in heterogeneous WANs, despite connectivity accumulating over time. The paper develops a flexible DAG growth framework and instantiates MANTA to advance and commit earlier while preserving worst-case guarantees.
Problem
- Rigid per-round quorum collection makes heterogeneous WAN progress wait for stragglers, increasing commit latency and reducing throughput.The barrier requires replicas to gather a quorum of references before advancing; rounds are parallelized, but still wait for slow replicas.Source: §1 · pp. 1–2
Evaluation
Flexible DAG growth
- The framework formalizes the tradeoff between faster low-threshold progress and sufficient connectivity for commitment, and derives liveness bounds.Its coverage-based abstraction uses boost edges to accumulate connectivity across rounds rather than rebuild it in each round.Source: §1 · p. 2
MANTA
- MANTA combines flexible growth and flexible coin to decouple connectivity from round advancement and trigger earlier commitment while preserving worst-case safety and liveness.If early commitment is unavailable, execution falls back to the normal path without affecting correctness or performance.Source: §1 · p. 2
Evaluation
- MANTA reduces latency by up to 70%, improves throughput by up to 18% at scale, and remains performant under faults.The evaluation compares MANTA with state-of-the-art protocols under realistic heterogeneous WANs.Source: §1 · p. 2
2 Background and Motivation
DAG-based BFT protocols use vertex references to build shared connectivity that supports common-core formation and commitment. In heterogeneous WANs, per-round quorum barriers make progress depend on slow vertices, motivating connectivity accumulation across rounds and commit rules that accommodate it.
2.1 DAG-Based BFT Consensus
- DAG vertices reference earlier vertices, and accumulated reachability supports common-core formation and subsequent commitment.At each wave's end, a common coin elects a leader; if it belongs to the common core, its causal history is committed.Source: §2.1 · p. 2
2.2 Dissecting DAG-Based BFT Performance
- Requiring 2f + 1 previous-round vertices before advancing creates a barrier in which progress is dictated by slow quorum vertices.Fast replicas can remain idle, delaying transaction admission and increasing commit latency.Source: §2.2 · p. 3
- With the same average RTT of 80 ms and workload of 20K–120K tx/s, heterogeneity raises commit latency by around 40% and round duration by over 25%.The comparison contrasts evenly distributed replicas and workloads with deployment across three continents and uneven workloads.Source: §2.2 · p. 3
- Connectivity can accumulate across rounds because safety and liveness depend on sufficient observation for the common core, not exact round-completion timing.Rigid within-round quorum requirements can make replicas wait despite early-arriving vertices already providing partial connectivity.Source: §2.2 · p. 3
- Flexible connectivity also requires commit conditions that account for connectivity formed across rounds rather than relying on consecutive-round structure.The framework characterizes how round-boundary constraints limit connectivity accumulation, and MANTA uses that flexibility to accelerate commitment.Source: §2.2 · p. 3
3 System Model
The system model considers state machine replication among n = 3f + 1 replicas, with up to f Byzantine. It assumes fully asynchronous communication and specifies safety and liveness as the protocol's required properties.
System model
- The model has n = 3f + 1 replicas, of which up to f may be Byzantine, and assumes authenticated reliable channels and a PKI.The adversary is computationally bounded.Source: §3 · p. 3
- Message delays are unbounded and delivery order arbitrary; the model also assumes reliable broadcast and a shared random coin.These assumptions capture heterogeneous network delays and support randomized coordination under asynchrony.Source: §3 · p. 3
- For state machine replication, safety prohibits correct replicas from committing different transactions at the same position, while liveness requires eventual commitment of every correct client's transaction.The protocol's goal is agreement on a total transaction order.Source: §3 · p. 3
4 Flexible DAG Growth Framework
The framework models how reference thresholds and wave length trade round latency against commitment connectivity, then uses worst-case liveness analysis to motivate accumulating coverage across rounds. This allows flexible reference patterns and lower per-round thresholds while preserving liveness guarantees.
4 Flexible DAG Growth Framework
- The framework models the trade-off between faster round advancement from lower reference thresholds and weaker connectivity for commitment, then analyzes worst-case liveness to guide flexible DAG designs.Its analysis models commit probability and latency under network conditions, examines adversarial DAG topologies, and motivates coverage-based flexibility.Source: §4 · p. 4
4.1 Modeling DAG Performance
- Commit latency depends on the probability of successful commitment and the time to accumulate connectivity over a wave, with each round waiting for the ref-th fastest vertex.The model uses ref and wave length k to characterize visible-set size and wave duration.Source: §4.1 · p. 4
4.1.1 Optimistic Analysis under Heterogeneity
- Under high heterogeneity, a smaller ref and larger k achieve better performance by allowing connectivity to accumulate across rounds rather than waiting for per-round synchronization.In low heterogeneity, a larger ref and smaller k minimize latency by maximizing per-round connectivity.Source: §4.1.1 · pp. 4–5
4.2 Liveness Constraints
- When ref = f +1, |Gk| = 0 for f > 1; when ref ≥ n−f, Gk remains non-empty and its guaranteed size increases with k.In two-round designs, liveness requires a threshold above the corresponding worst-case bound; stronger worst-case liveness requires a larger common core, ref, and k.Source: §4.2 · pp. 5–6, Table 1 · p. 6
4.3 From Rigidity to Flexibility
- Coverage, cov, counts target-round vertices reachable from a current-round vertex, allowing connectivity to be built through different reference paths rather than a fixed pattern.Progress edges inherit references through previous-round parents; boost edges add coverage from earlier rounds within the wave.Source: §4.3 · p. 6
- Different edge compositions can preserve the same worst-case liveness: by round 3, at least f +1 first-round vertices satisfy the commit rule when the required coverage is met.Different patterns that yield the same guaranteed set Gk also yield the same commit probability P.Source: §4.3 · pp. 6–7, Figure 5 · p. 6
5 MANTA Design
MANTA instantiates flexible DAG growth with a flexible coin, then specifies how replicas build, order, and commit the DAG. Its design is analyzed for safety and liveness and used to express existing DAG protocols in a shared parameter space.
5.1 Instantiation of MANTA
- MANTA’s parameter space sets cov = 2f +1, σ = 2, κ = 2, and ref = f +1, yielding a five-round wave with two solid steps.Each honest replica proposes at least one solid vertex per step; cov and κ are chosen to ensure worst-case liveness.Source: Figure 7 · p. 7, §5.1 · p. 7
5.2 Protocol in Detail
- Replicas propose vertices using either ref references from the preceding round or a solid vertex; certified vertices support ordering and commitment.The regular path elects a wave’s first-round leader with a common coin and checks its support in round 3; flexible coin can trigger earlier recovery and, in the fast path, use round 2 with an extended solid step.Source: §5.2 · pp. 7–8
5.3 Correctness Analysis
- The regular commit rule preserves a common total order, and repeated waves eventually commit a leader with probability 1.Safety follows from quorum intersection across the solid-step structure; the probability of selecting a committable leader per wave is at least (f +1)/(3f +1).Source: §5.3 · p. 9
5.4 Encoding Existing DAG-BFT Protocols
- The framework maps five representative DAG protocols to design points, expressing their different DAG-growth patterns through a shared abstraction.Examples include Tusk and DAG-Rider with dense references and different κ values, while Chitu can switch between fast and normal wave configurations.Source: §5.4 · p. 9
6 Evaluation
The evaluation compares MANTA with asynchronous DAG-based protocols in heterogeneous WAN settings, examines design parameters and faults, and measures component effects and resource use.
6.1 Implementation and Experimental Setup
- The evaluation uses CloudLab and AWS deployments, including a three-cluster WAN with unequal inter-cluster delays, and measures consensus latency from first receipt to ordering.The default MANTA configuration is σ = 2, ref = f +1, cov = 2f +1, and κ = 2.Source: §6.1 · p. 10
6.2 Design Parameter Trade-off
- Under network heterogeneity, large cov increases latency by requiring more slow replicas; among equal-round-per-wave configurations (σ, κ) = (1, 4), (2, 2), and (4, 1), fewer, longer solid steps achieve lower latency than more, shorter steps.In the Byzantine scenario, degradation gradually decreases as cov and κ increase and is nearly neutralized at κ = 3, cov = 10.Source: §6.2 · pp. 10–11
6.3.1 Fault-Free Performance
- At n = 50, MANTA reduces latency around 70% versus Chitu, Tusk, and DAG-Rider, and delivers around 30% lower latency and 18% higher throughput than Mahi-Mahi.Mahi-Mahi is the second-best baseline in this experiment.Source: Figure 10 · p. 11, §6.3.1 · p. 11
- At n = 10, MANTA achieves the lowest latency, reducing it by 30%–70% against the compared protocols.The comparison includes Tusk, Chitu, Mahi-Mahi, and DAG-Rider under fault-free settings.Source: §6.3.1 · p. 11
6.3.2 Performance under Faults
- With up to f silent nodes, MANTA performs comparably to the other protocols.The remaining replicas can form more complete connectivity, potentially helping baseline protocols use their fast paths and leaving less room for MANTA to benefit from faster progression.Source: §6.3.2 · p. 11
6.4 Breakdown and Resource Utilization
- Flexible coin consistently reduces latency by enabling commitment checks as soon as sufficient connectivity emerges, with a larger benefit at higher input rates.Flexible DAG growth shortens rounds from about 139.4 ms to 75.8 ms; flexible coin can then enable commitment before the final round.Source: §6.4 · p. 11
- Flexible coin adds negligible resource cost, while MANTA uses 1,465.8 B of average per-vertex metadata versus 388.0 B for Tusk.The protocol’s additional resource use is mainly associated with solid-step metadata; Boost edges may also add DAG state-management overhead.Source: Table 2 · p. 12, §6.4 · p. 12
- A lower reference threshold may disadvantage slow replicas, while τcand trades early recovery against worst-case latency under Byzantine behavior.The paper identifies dynamic parameter adaptation and finer-grained coin scheduling as future work.Source: §6.4 · p. 12
7 Related Work
Prior asynchronous DAG protocols improve consensus through structured parallelism but retain fixed progression rules; MANTA instead redesigns progression for heterogeneous WANs. Related approaches vary in network assumptions, construction, and how they introduce flexibility.
Asynchronous BFT
- MANTA redesigns DAG progression for heterogeneous WANs, unlike prior asynchronous DAG systems that largely retain fixed progression rules.DAG-Rider introduced DAG-based asynchronous BFT, followed by systems adding a mempool layer, a fast path, or uncertified DAG construction and lightweight dissemination.Source: §7 · p. 12
Partially synchronous DAG-based BFT
- Partially synchronous DAG protocols use designated leaders and optimistic paths, but depend on timing assumptions and can degrade under highly heterogeneous WAN conditions.MANTA instead operates in a fully asynchronous model without synchrony assumptions.Source: §7 · p. 12
Uncertified DAG-based BFT
- Uncertified DAGs and best-effort dissemination reduce overhead but are more sensitive to packet loss and delay variation, which can force data recovery onto the critical path.MANTA focuses on certified DAG constructions.Source: §7 · p. 12
Flexibility in DAG-based BFT
- Existing flexibility approaches modify reference rules, metadata, finality, or round boundaries; MANTA relaxes round advancement while retaining explicit rounds and waves.Lemonshark’s key-space sharding is described as orthogonal to MANTA, while Avalanche uses probabilistic sub-sampling without explicit round boundaries.Source: §7 · p. 12
8 Conclusion
MANTA decouples commitment requirements from round advancement and combines flexible growth with a flexible coin; experiments report lower latency under fault-free heterogeneous deployments. The accompanying appendix passages define the reliable-broadcast, common-coin, and common-core concepts used in the paper.
8 Conclusion
- MANTA decouples commit requirements from round advancement and combines flexible growth with a flexible coin for earlier connectivity and commitment.Under fault-free heterogeneous deployments, experiments report at least 30% lower latency than prior asynchronous DAG-based BFT protocols while preserving robustness.Source: §8 · p. 12
A.1 Reliable Broadcast (RBC)
- Reliable broadcast ensures that, despite a Byzantine sender, honest replicas eventually deliver the same message or none.Its stated properties are agreement, integrity, and validity.Source: §A.1 · p. 15
A.2 Global Perfect Coin
- The global perfect coin gives honest replicas the same unpredictable leader choice, with termination when at least f + 1 replicas invoke it.The appendix also states unpredictability and unbiasedness guarantees.Source: §A.2 · p. 15
A.3 Common Core Abstraction
- The common-core abstraction aggregates received values across k rounds, yielding a set shared by every honest replica at the end.The common-core size captures how many first-round inputs are guaranteed commonly visible and determines a wave’s commitment probability.Source: §A.3 · p. 15
B DAG Growth Proof
The appendix models heterogeneous-delay DAG growth through round and wave timing and analyzes leader visibility and commitment under stochastic delays. Its latency and commitment estimates depend on a stable aggregate arrival trend, while the random-delay analysis models reference selection probabilistically.
B.1 Heterogeneous Network Model
- The heterogeneous-network model assumes a stable aggregate arrival trend, treating vertices as arriving in tiers and abstracting away replica-specific views and cross-round causal dependencies.It uses independent quorum delays while aiming to capture latency and connectivity trends as delay distributions and DAG parameters vary.Source: §B.1 · p. 15
This is the minimum physical time within which one round
- For n i.i.d. replica delays d, d(ref), the ref-th order statistic, represents one logical round’s completion time; a wave window is defined for k rounds at target confidence c ∈(0,1).Source: §B.1 · p. 16, This is the minimum physical time… · p. 16
B.2 Random-Delay Network Model (Stochastic case).
- The stochastic model tracks how leader visibility propagates across rounds and treats a leader as committed when final-round support reaches f + 1.Its latency measure is the expected number of rounds until commitment, and the cited tables summarize commit probability and expected rounds for reference configurations without supplying their values here.Source: §B.2 · pp. 16–17, Table 3 · p. 17, Table 4 · p. 17
B.3 Adversarial Network Model (Worst case)
The adversarial analysis bounds how many first-round vertices remain committable under worst-case DAG topology. For n = 3f + 1 and ref ≥ n − f, larger waves yield stronger guaranteed sets; lower thresholds can fail to guarantee liveness.
B.3 Adversarial Network Model (Worst case)
- For n = 3f + 1, ref ≥ n − f guarantees at least f + 1 committable first-round vertices in a two-round wave.The analysis treats vertices not guaranteed committable under every admissible topology as non-committable for its lower bound.Source: §B.3 · p. 17
- For n = 3f + 1, ref ≥ n − f guarantees at least 1.5f committable first-round vertices in a three-round wave.The proof uses the quorum-intersection structure of links through the decision round.Source: §B.3 · pp. 17–18
- In a three-round wave, ref ≥ 1.5f + 1 guarantees at least one committable vertex, and ref ≥ 1.8f + 1 guarantees at least f + 1.At ref ≥ f + 1, the bound gives no liveness guarantee.Source: §B.3 · p. 18
- For n = 3f + 1, ref ≥ n − f guarantees at least 2f + 1 committable first-round vertices in a four-round wave.The proof applies the three-round guarantee to an intermediate common-core set and considers maximally overlapping reference sets.Source: §B.3 · p. 18
C.1 Safety Proof
The safety proof shows that committed leaders remain in the causal history of later committed leaders, so honest replicas cannot commit different leader sequences.
C.1 Safety Proof
- A committed leader has a path from every vertex in every round of every higher wave.Flexible coin permits observation at r2, r3, or r4; quorum intersection and the solid-step links establish the path into the next wave, which then extends inductively.Source: §C.1 · p. 18
- Any two honest replicas commit the same sequence of vertex leaders.A later committed leader has a path to an earlier committed leader, so the earlier leader is in its causal history and cannot be skipped.Source: §C.1 · p. 18
C.2 Liveness Proof
The liveness proof establishes that enough first-round vertices satisfy the commit rule for flexible coin to proceed, ensuring eventual commitment of correct-client transactions.
C.2 Liveness Proof
- At least f + 1 vertices in the first round of each wave satisfy the commit rule.Counting links from an arbitrary 2f + 1 round-three vertices, while assigning at most f links to non-committable vertices, yields the lower bound.Source: §C.2 · p. 18
- Every transaction issued by a correct client is eventually committed.The proof relies on at least f + 1 committable first-round vertices and permits any τcand ≥1.Source: §C.2 · pp. 18–19
- Any τcand ≥1 is sufficient for liveness when flexible coin is used.The proof says the coin prerequisite is met once a replica locally observes at least τcand first-round vertices satisfying the commitment criteria.Source: §C.2 · p. 19
D Optimizations
MANTA decouples transaction dissemination from consensus metadata to reduce delays from straggling replicas, and the section compares asynchronous and partially synchronous protocols under partition-like WAN delays.
D Optimizations
- MANTA's flexible data structure separates transaction dissemination from consensus metadata to address bandwidth underutilization and queuing delays in heterogeneous networks.Transactions need not wait for a designated proposer or the next vertex window before dissemination.Source: D Optimizations · p. 19
- Tblocks carry raw transaction data via best-effort broadcast, while vertices carry Tblock digests and PVAs via Byzantine Reliable Broadcast.A PVA requires f + 1 acknowledgments and guarantees delivery to at least one honest replica; vertices with valid PVAs can be voted on without waiting for Tblock contents.Source: D Optimizations · p. 19
- A transaction's Tblock can enter the DAG once authenticated rather than waiting for its sender's designated vertex, reducing excessive delays from stragglers or unstable networks.After other replicas receive the Tblock and its PVA, they can include its digest in their own vertices.Source: D Optimizations · p. 19
- The simplified RBC checks each proposal for equivocation and valid PVAs, then incorporates it after a certificate or at least 2f + 1 votes, once referenced certificates are stored.The proposer collects n−f votes, aggregates them into a vertex certificate, and broadcasts it.Source: D Optimizations · p. 19
E Performance under Heterogeneous Network
- Under partition-like WAN delays, Tusk throughput drops about 13% and average latency rises 4.5×, while Autobahn maintains similar throughput but average latency rises over 30×.The comparison is presented as evidence of stronger robustness for asynchronous designs under highly heterogeneous WAN conditions.Source: Figure 13 · p. 20, E Performance under Heterogeneous… · p. 20