Source-linked AI summary
Barnacle: Adaptive Multi-Leader Scheduling for DAG-Based Consensus
George Danezis, Zeno De Angeli, Alexandru Ianov Vitanov, Philipp Jovanovic, Lefteris Kokoris-Kogias, Alberto Sonnino, Pasindu Tennage, Igor Zablotchi
TL;DR
DAG consensus can reduce transaction queuing latency with multiple leaders, but existing dynamic schedulers choose who leads rather than how many leaders run. Barnacle adapts the leader count using AIMD, and its reported results match the best static count across regimes.
Problem
DAG consensus can reduce queuing latency with multiple leaders, while prior dynamic schedulers choose who leads rather than how many leaders run.
Source: §1 · pp. 2, 4Method
Barnacle adapts the leader count with an AIMD control rule as a generic add-on to DAG consensus.
Source: §1 · p. 4, §9 · p. 19Results
Barnacle matches the best static leader count in every regime: latency is 6–13% lower than a single leader’s in healthy networks and 35–56% below a static high count under degradation while matching a single leader.
Source: §1 · p. 4Takeaways & Limitations
One implementation spans four fault models, and the paper establishes safety and liveness through formal proofs and a Lean formalization.
Source: §1 · p. 4, §2.1 · p. 5The evaluation relies on simulation; benchmarking and testing BFT protocols under actual Byzantine behavior remains an open problem.
Source: §7 · p. 15
Abstract
from arXiv · showhide
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.
1 Introduction
Multiple leader slots can reduce queuing latency but expose the commit pipeline to head-of-line blocking, making any fixed leader count poorly suited to every network regime. Barnacle adapts the count at runtime using information already present in the committed DAG.
1 Introduction
- More leaders reduce queuing latency, but a slow leader can delay later slots because commits proceed in round-then-slot order.A partially reached leader may await the indirect decision rule, while later slots wait behind it.Source: §1 · p. 2
- Barnacle adjusts the number of leaders at runtime, using the fraction of recent committed-DAG slots decided as commits by the direct rule as a network-health signal.All honest validators compute the same signal from agreed state, without extra messages or cryptography.Source: §1 · pp. 2–3
- Barnacle is a generic add-on over a minimal DAG interface, instantiated on four base protocols: Mysticeti (n=3f+1), Blue Bottle (n=5f+1), Nemo-Nemo (n=2c+1), and Orcaella (n=5f+3c+1).The protocols are respectively Byzantine, Byzantine with a two-round commit, crash-fault tolerant, and mixed (f Byzantine plus c crashed).Source: §1 · p. 3
- In healthy networks, Barnacle’s latency is 6–13% lower than a single leader’s; under degradation, it matches a single leader while remaining 35–56% below a static high count.Overall, Barnacle matches the best static leader count in every regime.Source: §1 · p. 4
- The authors are collaborating with the Sui team to integrate Barnacle into the Sui blockchain.The paper also positions Barnacle as addressing a deployment choice in which production networks run a single leader per round.Source: §1 · pp. 2, 4
2 Background and Model
The section sets out the system assumptions and correctness requirements for Barnacle, then explains the DAG structure and leader-decision mechanisms on which it operates.
2.1 System model and problem
- The model uses a partially synchronous network: after GST, messages arrive within a known bound ∆, and the base protocol’s leader timeout is at least ∆.After GST, only slots led by crashed or Byzantine validators can remain undecided, at most f+c per round.Source: §2.1 · pp. 4–5
- In deployments, a short fixed leader timeout means even an honest leader delayed by congestion may fail to reach the direct commit rule.Barnacle observes that symptom without distinguishing temporary degradation from a faulty leader.Source: §2.1 · p. 5
- Barnacle must preserve the base protocol’s properties and aim to match the best static leader count as conditions change; correctness is proved, while performance is evaluated empirically.The requirements specify no healthy-condition latency penalty and tracking the best static count when slots stall, with recovery as conditions improve.Source: §2.1 · p. 5
2.2 DAG-based consensus
- Every validator proposes a block each round, and ordered leader slots are decided first by a wave-local direct rule, then by a slower indirect rule if needed.The indirect rule uses a future anchor and certified causal paths; decided leaders are ordered by round and slot.Source: §2.2 · pp. 5–6
- The four base protocols span Byzantine, crash-only, and mixed fault models; Barnacle leaves quorum sizes inside the base protocol’s decision rules.The instances are Mysticeti, Blue Bottle, Nemo-Nemo, and Orcaella; the same measurement also applies to certified DAGs, though it is not evaluated there.Source: §2.2 · p. 6
3 Overview
Barnacle periodically estimates recent direct-commit performance from a committed DAG window and uses the result to update the leader count deterministically. The shared window lets honest validators agree on changes without additional messages or cryptography.
3 Overview
- At each pivot, Barnacle counts slots in the preceding Interval-round causal-history window that the direct rule decided as commits, then compares the count with an expected total.The expected value is based on the current leader count and the number of eligible rounds.Source: §3 · pp. 6–7
- A rate meeting the threshold increases the leader count by one; consecutive unhealthy windows decrease it by 1, 2, 4, and so on, bounded between one and maxLeaders.This is additive increase, multiplicative decrease, and the updated count applies after the pivot.Source: §3 · p. 7
- The pivot’s causal history gives honest validators the same measurement window, so they compute the same configuration change deterministically.The test is a single integer comparison and requires no messages or cryptography.Source: §3 · p. 7
- Barnacle’s correctness argument does not depend on AIMD: safety and liveness hold for any deterministic update rule computed on the shared window.The base protocol interface supplies the leader schedule, committed prefix, and direct-decision predicate; quorum sizes remain within the base protocol.Source: §3 · pp. 7–8
4 The Barnacle Protocol
Barnacle adapts the leader count through a minimal DAG-protocol interface, using direct-commit outcomes from a shared committed window to guide updates. Its integration keeps each round under one leader count and leaves base-protocol decision logic in place.
4 The Barnacle Protocol
- Barnacle uses the base protocol’s leader schedule, committed prefix, and direct-commit predicate; only the decider is protocol-specific across the four instantiations.The instantiations cover Mysticeti, Blue Bottle, Nemo-Nemo, and Orcaella.Source: §4 · p. 8, §4.1 · p. 9
4.1 Integration with the base protocol
- Each round is decided under one leader count: a committed pivot triggers an update for the next round, while its remaining slots retain the old count.The pivot is reached after the last update interval; the trigger tolerates a skipped pivot slot.Source: §4.1 · pp. 8–9
4.2 Updating the leader count
- The update window is the pivot’s causal history over the last Interval rounds, giving honest validators that commit the pivot the same window.It includes every referenced leader block and direct-rule reference in those rounds.Source: §4.2 · p. 11
- Barnacle counts window slots committed by the direct rule and compares them with the slots decidable within the window.The last waveLength rounds are excluded from expected commits because their decisions cannot be completed within the window.Source: §4.2 · p. 11
- If the direct-decision rate meets the threshold, the leader count rises by one; otherwise it falls by 2^backoff, floored at 1.The increase is capped at maxLeaders, and backoff resets after a healthy interval.Source: §4.2 · p. 11
5 Correctness
Barnacle preserves the base protocol’s safety under its stated interface assumptions and maintains liveness after GST. Its correctness statements are machine-checked in Lean.
5 Correctness
- Honest validators agree on reached configurations, including their start rounds, leader counts, and verdicts for closed configurations.The proposition applies to any deterministic update rule, including AIMD.Source: §5 · p. 12
- Barnacle composed with any base protocol satisfying A1–A4 preserves agreement, total order, and integrity of committed sequences.The statements and proof sketches are machine-checked in Lean.Source: §5 · pp. 11–12
- With a constant update rule, Barnacle is the base protocol; AIMD keeps the leader count within [1, maxLeaders].The constant rule yields the same schedule, verdicts, and ledger.Source: §5 · p. 13
- After GST, every honest validator reaches every height, closes each configuration, and continues to see committed slots.The finite-horizon statement leaves a wave plus the commit gap below the horizon for decisions.Source: §5 · p. 13
- For all four base protocols, the paper proves per-configuration liveness at every leader count using a new argument with a commit gap of n + waveLength − 1 rounds.The argument descends through the first slot of each round and uses a pigeonhole argument on the rotation.Source: §5 · p. 13
- The chosen leader count is heuristic rather than proven optimal, and Byzantine validators can bias one window’s measurement for one interval.The count nevertheless remains within [1, maxLeaders] and never falls below the single-leader baseline.Source: §5 · p. 13
6 Implementation
The implementation adds a Rust scheduler and commit-path integration to Mysticeti, while a simulator exercises the same consensus logic under changing, heterogeneous network conditions.
6 Implementation
- The scheduler is about 270 lines of code and adds no messages, cryptography, or persistent state beyond the current configuration.It runs unchanged on the four base protocols.Source: §6 · p. 14
- About 500 additional lines integrate the scheduler into the commit path and configuration, with the same code across protocol variants.The simulator replaces the networking stack behind the same interface, leaving consensus logic unmodified.Source: §6 · p. 14
- The simulator extends the inherited layer by about 600 lines to model time-varying, heterogeneous links and scripted phases with selected slow validators.It records committed latency, leader count, and leader-slot decision types per validator and sampling window.Source: §6 · p. 14
7 Evaluation
Across four DAG protocols, scripted simulations evaluate Barnacle in healthy, degraded, and recovery phases; it adapts leader counts while matching strong static baselines.
7.1 Experimental setup
- The evaluation scripts 100 s healthy, 400 s degraded, and 100 s recovery phases, with affected links raised beyond the 1 s leader timeout.Barnacle uses 25-round intervals, a maximum of five leaders, and a 0.96 threshold; fixed-1 and fixed-5 are the static baselines.Source: §7.1 · pp. 15–16
7.2 Healthy network
- In healthy windows, Barnacle equaled fixed-5 within 1% and beat fixed-1 by 6% (Mysticeti), 13% (Blue Bottle), 10% (Nemo-Nemo), and 12% (Orcaella).The reported fixed-1 latencies were 348 ms (Mysticeti), 274 ms (Blue Bottle), 259 ms (Nemo-Nemo), and 268 ms (Orcaella).Source: §7.2 · p. 16, Figure 2 · p. 16
7.3 Degraded network and recovery
- In steady degraded windows, Barnacle matched fixed-1 and beat fixed-5 by 35% (Mysticeti), 56% (Blue Bottle), 44% (Nemo-Nemo), and 43% (Orcaella).The reported latencies were 2.08 s versus 3.18 s for Mysticeti, 0.75 s versus 1.69 s for Blue Bottle, 1.97 s versus 3.48 s for Nemo-Nemo, and 1.21 s versus 2.13 s for Orcaella.Source: Figure 2 · p. 16, §7.3 · p. 17
- Barnacle backed off within 15 s, reached one leader about 45 s into degradation, then recovered one leader per interval to five about 15 s after healing.Across the whole degraded phase, latency was 5% (Mysticeti), 9% (Blue Bottle), 6% (Nemo-Nemo), and 6% (Orcaella) above fixed-1; every validator continued committing transactions.Source: §7.3 · p. 17, Figure 3 · p. 17
7.4 Generality across fault models
- Across Mysticeti, Blue Bottle, Nemo-Nemo, and Orcaella, behavior persisted with identical scheduler code and parameters; steady-window fixed-5 penalties over fixed-1 ranged from 53% to 125%.The range was 53% for Mysticeti and 125% for Blue Bottle.Source: §7.4 · p. 17
- The evaluation does not test sensitivity to Interval or threshold; the 0.96 threshold tolerates about four non-direct slots per window under five leaders and none under one.No per-protocol tuning was needed.Source: §7.4 · p. 18
8 Related Work
Barnacle differs from prior fixed-count multi-leader DAG protocols by adapting leader count at runtime as a composable add-on. The section situates it alongside reputation-based leader selection and adaptive BFT approaches.
8 Related Work
- Barnacle is presented as the first runtime leader-count adaptation and the first add-on that composes with existing multi-leader DAG protocols.Earlier multi-leader DAG protocols fix leader count at configuration time.Source: §8 · p. 18
- Recent multi-leader DAG protocols use fixed counts; Barnacle is instantiated on four of them.The cited protocols span certified and uncertified DAGs, Byzantine, crash, and mixed fault settings.Source: §8 · p. 18
- Reputation-based election excludes unreliable validators, while Barnacle sizes the leader set; the approaches are orthogonal and composable.Both can derive schedules deterministically from committed history without messages.Source: §8 · p. 18
- Parallel consensus systems face a related global-ordering straggler problem, but applying Barnacle to them remains future work.Barnacle adapts parallelism, whereas Ladon dynamically orders blocks.Source: §8 · p. 18
- Unlike BFTBrain’s protocol switching with reinforcement learning and consensus-coordinated learning, Barnacle uses a deterministic AIMD rule without learning or extra coordination.The AIMD control law is attributed to Chiu and Jain.Source: §8 · p. 18
9 Conclusion
Barnacle adjusts leader count from the direct decision rate on the committed DAG, addressing the fact that no static count suits every regime. The paper reports that it preserves base-protocol safety and liveness while matching the best static count across regimes.
9 Conclusion
- Barnacle uses a local, deterministic, message-free AIMD control loop on the direct decision rate measured on the committed DAG.Its safety and liveness are preserved from the base protocol.Source: §9 · p. 19
- Barnacle matches the best static leader count in every evaluated regime, reducing latency over one leader when healthy and avoiding severe degradation from high counts during instability.It is currently being integrated into the Sui blockchain.Source: §9 · p. 19
- The update rule can be changed without changing the proofs, and future work includes counterfactual window replay and extending the approach beyond DAG protocols.The proposed extensions include multi-proposer protocols.Source: §9 · p. 19
A Base-Protocol Pseudocode
The appendix specifies a generic decider used by all four base protocols, separating shared decision logic from protocol-specific parameters.
A Base-Protocol Pseudocode
- One generic decider covers all four base protocols, with shared wave geometry and DAG predicates.Algorithm 4 gives the decider instance, identical across protocols.Source: A Base-Protocol Pseudocode · p. 21
- Algorithm 5 supplies decision rules parameterized by commitThreshold, skipThreshold, and linkSize.Table 1 gives the values used by each protocol.Source: A Base-Protocol Pseudocode · p. 21
- The pseudocode follows Mysticeti’s published algorithms [2], generalized for differences among the four protocols.Source: A Base-Protocol Pseudocode · p. 21
A.1 One decider for four protocols
The appendix presents shared decider logic for four protocols, including a parameterized instance and direct and indirect decision rules. Protocol-specific thresholds and certificate/link behavior specialize those rules.
A.1 One decider for four protocols
- The generic decider changes the published rules by parameterizing quorum sizes, using parent lookup for votes, and making skip tests per slot rather than per equivocating leader block.It also aligns vote and certify behavior when their rounds coincide and counts certified links against linkSize.Source: §A.1 · p. 21
A.2 The decider instance
- A decider instance takes a wave offset, slot index, and DAG; pipelining uses one instance per offset.LeaderBlock returns the slot’s leader block or several in case of equivocation; IsVote and IsLink represent direct parenthood and reference reachability.Source: §A.2 · p. 21
A.3 The decision rules
- The direct rule commits or skips from vote and certificate thresholds; the indirect rule uses a later non-skipped anchor and link threshold to resolve undecided slots.While the anchor is undecided, the original slot remains undecided.Source: §A.3 · p. 21
- Mysticeti uses n−f thresholds and one certified link, while Blue Bottle uses the vote as its certificate and linkSize n−3f.The parameter choices are protocol-specific.Source: §A.3 · p. 22
- Nemo-Nemo uses c+1 thresholds and resolves skips indirectly; Orcaella uses n−f−c thresholds and n−3f−2c links, with c=0 recovering Blue Bottle.Source: §A.3 · p. 22
B Full Proofs
The appendix proves Barnacle’s safety and post-GST liveness from base-protocol assumptions, then documents its Lean-checked formalization, interface, and run model.
B Full Proofs
- Barnacle preserves agreement, total order, and integrity for any base protocol satisfying A1–A4.The proof uses agreement on configurations and slot verdicts to show committed sequences agree and grow only by appending, with no block committed twice.Source: B Full Proofs · pp. 24–25
- After GST, once all honest validators close Ck, one closes Ck+1 within bounded time and all follow within Δ; repeated progress reaches every height.Each configuration closing commits a pivot, so committed slots keep appearing.Source: B Full Proofs · pp. 25–26
- The rotating schedule is live at every leader count: reliable round heads recur within n + waveLength − 1 rounds, bounding the commit gap.The head-based proof works where a consecutive honest-led-slot argument can fail under multiple leaders.Source: B Full Proofs · pp. 26–27
C Lean Formalization
- Every Section 5 statement is machine-checked in Lean 4, with no sorry and no axioms beyond Lean’s three standard ones.Executable witnesses evaluate definitions on concrete DAGs before theorem use.Source: C Lean Formalization · p. 27
C.1 The Base-Protocol Interface
- The abstract interface captures causal completeness, agreement, direct-decision soundness, and candidate-only decisions; fault assumptions remain in protocol instantiations.Table 3 maps paper statements to their machine-checked counterparts.Source: §C.1 · pp. 27–28, Table 3 · p. 28
C.2 Runs and Liveness
- Each configuration has a fixed leader schedule and closes at a pivot, where its update rule determines the next configuration.The observed count concerns slots in the pivot’s causal-history window that a direct rule decided as commit.Source: §C.2 · pp. 28–29
- Liveness is expressed structurally on good DAGs: slots are decided with a commit-gap-plus-wave margin under the horizon, while some slot commits within each gap.The margin is necessary for slots that rely on indirect decisions.Source: §C.2 · p. 29
C.3 Results
The results map the four base protocols to their interface and liveness bounds, with fault bounds entering through each protocol’s reliable set.
C.3 Results
- Mysticeti and Blue Bottle satisfy the interface and descent laws at slack f, with commit gaps n + 2 and n + 1, respectively.The table maps each Section 5 statement to its machine-checked counterpart.Source: §C.3 · p. 29
- Nemo-Nemo’s safety uses no fault bound; its liveness uses the crash bound for a synchronized live majority and has commit gap n + 1.The fault bound enters through the reliable set.Source: §C.3 · p. 29
- Orcaella satisfies the laws at slack f + c with commit gap n + 1; its mixed-fault bound enters only through the reliable set.The table maps each Section 5 statement to its machine-checked counterpart.Source: §C.3 · p. 29