Research
Barnacle: Adaptive Multi-Leader Scheduling for DAG-Based Consensus
In DAG-based consensus protocols every validator proposes a block each round, and specially designated "leader" blocks determine which transactions get committed.

- arXiv
- 2609.03978
- Published
- 2026-09-03
- Authors
- George Danezis, Zeno De Angeli, Alexandru Ianov Vitanov, Philipp Jovanovic, Lefteris Kokoris-Kogias, Alberto Sonnino, Pasindu Tennage, Igor Zablotchi
AI summary
Overview
Research area: Distributed systems and blockchain consensus — specifically DAG-based Byzantine fault-tolerant (BFT) consensus protocols and their leader-scheduling policies.
Technical level: Advanced. The paper combines a networking-systems control loop, formal safety/liveness proofs (hand-written and machine-checked in Lean 4), and a performance evaluation across four consensus protocols.
Scope (one sentence): Barnacle is a generic, message-free add-on that dynamically adjusts how many leader slots per round a DAG-based consensus protocol uses, based on a deterministic measurement taken from the already-committed DAG, and the paper proves its correctness and evaluates its latency against static leader counts.
What This Paper Is About
In DAG-based consensus protocols every validator proposes a block each round, and specially designated "leader" blocks determine which transactions get committed. Adding more leaders per round shortens the queue a transaction waits in before being included in a leader block, but each extra leader is also another chance for a slow validator to stall the pipeline — a problem called head-of-line blocking. Because this trade-off depends on network conditions, any fixed leader count is wrong in some regime, so production systems (including Sui's deployment of Mysticeti) run a single leader. The paper's goal is a mechanism that picks the leader count automatically at run time, tracking the best static choice in both healthy and degraded conditions.
Key Contributions
-
First run-time adaptation of leader count (not leader identity) in DAG consensus. Prior dynamic schedulers choose who leads; Barnacle decides how many validators lead, using no additional protocol messages and no cryptographic tools.
-
A generic interface and safety/liveness proofs. The authors define an abstract base-protocol interface (A1–A4: rounds and slots, causal completeness, a direct-decision predicate, and base safety/liveness) and prove that composing Barnacle with any protocol meeting it preserves Atomic Broadcast safety and liveness — for any deterministic update rule, not just the one they chose. Proofs are given by hand and machine-checked in Lean 4.
-
One implementation across four fault models. The same code runs on Mysticeti (n = 3f+1, Byzantine, three-round waves), Blue Bottle (n = 5f+1, Byzantine, two-round waves), Nemo-Nemo (n = 2c+1, crash faults, two-round waves), and Orcaella (n = 5f+3c+1, mixed Byzantine plus crash, two-round waves). Barnacle never inspects n, f, c, or quorum sizes.
-
Empirical claim of matching the best static leader count in every regime. In a healthy network, latency is 6–13% lower than with a single leader per round; under degradation it matches a single leader while staying 35–56% below a static high leader count.
Main Findings
-
Queuing latency motivates multi-leader, but blocking prevents it. In Sui's Mysticeti deployment, validators propose roughly every 75 ms and end-to-end latency is about 400 ms. A transaction reaching the next round's leader waits about 35 ms in expectation (half a block interval), while one reaching a non-leading validator waits a full round of 75 ms — roughly a 20% increase in end-to-end latency. With L leaders among n validators, a transaction lands on a leader with probability L/n.
-
Head-of-line blocking has two forms, and both are visible in one signal. In round-level blocking the leader block reaches nobody in time and the slot is decided as skip by the direct rule; in commit-level blocking the block reaches only part of the committee, the slot stays undecided, and every later slot waits at least a wave for the indirect decision rule. In both cases the slot is not decided as commit by the direct rule — so that fraction is a sufficient health signal.
-
The measurement is free and deterministic. Because every validator proposes a block every round, the pivot's causal history over the last Interval rounds contains every leader block and every reference the direct rule reads. Every honest validator that commits the pivot computes an identical window, an identical count, and therefore an identical configuration change.
-
Additive increase, multiplicative decrease (AIMD) is the chosen control law. With an Interval of 50 rounds (a few seconds), maxLeaders of 5, and a threshold of 0.96, the leader count grows by one on a healthy window and shrinks by 1, 2, 4, … on consecutive unhealthy windows, never below one. Expected commits are computed as (Interval − waveLength + 1) × leadersPerRound, excluding the last waveLength rounds rather than counting them as failures.
-
Correctness holds for any deterministic update rule. Proposition 1 shows validators agree configuration by configuration; Theorem 5.1 gives Agreement, Integrity and Total Order; Lemma 2 and Theorem 5.2 give liveness after GST. With the constant update rule, Barnacle is exactly the base protocol.
-
Liveness needed a new argument at high leader counts. The classic "wave of consecutive honest-led slots" argument has no instance once several leaders share a round, so the authors use a descent through the first slot of each round plus a pigeonhole on the leader rotation, yielding a commit gap of n + waveLength − 1 rounds.
-
Base protocols differ only in their decider parameters. Mysticeti uses commit/skip thresholds of n − f and one link; Blue Bottle uses n − f (that is, 4f+1) with linkSize = n − 3f (2f+1); Nemo-Nemo uses a commit threshold of c+1 and a skip threshold of n (so skips in practice come from the indirect rule); Orcaella uses n − f − c (4f+2c+1) with linkSize = n − 3f − 2c (2f+c+1), recovering Blue Bottle when c = 0.
-
Not evaluated: certified DAGs. The authors state the same measurement applies to certified DAGs such as Narwhal/Bullshark or Shoal, because every validator's certified block still exists in every round, but this is explicitly not evaluated.
Methodology in Plain English
The core idea is to reuse information the protocol already produces instead of adding a health-monitoring protocol. Every so often — every 50 rounds by default — a validator picks the first leader it commits that is more than Interval rounds past the previous such leader, called the pivot. The pivot's causal history, restricted to the last Interval rounds, becomes a fixed snapshot that every honest validator will compute identically.
Inside that snapshot, validators count how many leader slots were decided as commit by the protocol's fast, optimistic decision rule. That count is compared against how many were expected given the current leader count. If the ratio meets the 0.96 threshold, the network is judged healthy and the leader count goes up by one (up to 5). If not, the count is cut — by 1, then 2, then 4, and so on for consecutive bad windows — down to a floor of one. The test is a single integer comparison, with no extra messages and no cryptography.
The integration detail that makes this safe is bookkeeping: the new configuration starts at the round after the pivot, and the remaining slots of the pivot's round are still decided under the old count. That way no round ever mixes two leader counts, and the leader schedule stays an interpretation of the DAG rather than part of it — so the base protocol's own safety argument applies within each configuration, and the switch is the only delicate point. The authors prove correctness by induction over configurations, then encode the statements in Lean 4 (open-sourced at github.com/gdanezis/lean-dag, commit 24d727f). Performance is assessed separately, since the latency goal (R2) is outside the formal model; the paper's Section 7 reports the latency comparisons, though the truncated content provided here does not include the experimental setup, testbed, or workload details.
Why This Matters
Impact on research. The paper reframes leader scheduling in DAG consensus: instead of treating the leader count as a static deployment parameter or electing who leads, it makes the count itself a control variable driven by protocol-internal evidence. The generic interface A1–A4 and the proof that any deterministic update rule preserves correctness separate the safety argument from the control policy, so others can plug in different controllers. The observation that the direct-decision rate is exactly the signature of head-of-line blocking gives protocol designers a zero-cost instrumentation point.
Real-world applications.
- Blockchain validator deployments running Mysticeti-style consensus, notably Sui, where the authors report active collaboration with the Sui team to integrate Barnacle.
- High-throughput payment and exchange settlement chains where end-to-end latency is the primary operator metric.
- Permissioned or consortium ledgers using crash-tolerant (2c+1) or mixed (5f+3c+1) DAG protocols that must tolerate both crashed and Byzantine nodes.
- Any DAG-based infrastructure that experiences variable network conditions and currently hand-tunes a conservative leader count.
Industry relevance. The paper directly addresses why operators run a single leader despite published multi-leader support — the original Mysticeti paper itself recommends deploying with only two leaders or a small constant. Barnacle offers a way to capture the multi-leader latency win without accepting the tail-latency risk during congestion, using a mechanism that adds no messages, no signatures, and no new failure modes.
Future Directions
- Integration and measurement in Sui. The stated next step is integrating Barnacle into the Sui blockchain; production behaviour under real congestion, and the interaction with Sui's 200 ms leader timeout, remain to be reported.
- Certified DAGs. The authors argue the same window measurement applies to certified DAGs such as Narwhal/Bullshark and Shoal, but explicitly do not evaluate it — a natural extension.
- Alternative control policies. Since safety and liveness hold for any deterministic rule computed on the window, comparing AIMD against other controllers (different intervals, thresholds, or non-AIMD laws) is left open; the paper only notes that the one-interval lag before a decrease is evaluated empirically.
- Tuning the cost of a wrong step. The paper argues additive increase costs at most one interval of one stalled slot, but the interaction between Interval, maxLeaders, and threshold across different network regimes is not characterized analytically.
Target Audience
Consensus-protocol researchers and graduate students working on DAG-based BFT and atomic broadcast; blockchain protocol engineers and validator operators who deploy these systems and care about tail latency; and formal-methods practitioners interested in a worked example of proving an add-on correct for an abstract base protocol and machine-checking it in Lean 4. Readers need comfort with quorum-based fault models (3f+1, 5f+1, 2c+1, 5f+3c+1), wave/slot terminology, and partially synchronous network assumptions.
Authors’ 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…
The full abstract on arXiv