← All papers
First page of Barnacle: Adaptive Multi-Leader Scheduling for DAG-Based Consensus

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

cs.DC Sep 3, 2026 · v2 cs.CR
Safety, liveness, agreement, and AIMD-rule properties of the Barnacle leader-count scheduler are machine-checked in Lean 4, with an open-source repository.
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.

DAG-based consensus protocols could cut queuing latency by using multiple leader slots per round. Production systems still run a single leader because a slow leader causes head-of-line blocking, and this risk grows with the leader count.

Barnacle is an add-on that measures, on the committed DAG, the fraction of leader slots decided by the direct commit rule in each interval. It then adjusts the leader count using additive increase, multiplicative decrease. It needs no extra messages and no cryptography, and it is instantiated on four protocols covering Byzantine, crash-only, and mixed fault models. Window agreement, leader-count agreement, safety, liveness, and AIMD bounds are proven by hand and machine-checked in Lean 4, with no sorry and only the standard axioms.

In simulation, 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. Under degradation it matches a single leader and stays 35-56% below a static count of five leaders.

Protocolfixed-1fixed-5Barnacle
Mysticeti2,0843,1832,077
Blue Bottle7531,693745
Nemo-Nemo1,9643,4841,965
Orcaella1,2122,1301,209
Latency (ms) in the degraded steady state