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

Barnacle is a generic, add-on mechanism for DAG-based consensus that dynamically adapts the number of leader slots per round to optimize end-to-end latency. It addresses the trade-off where multiple leaders reduce queuing latency but risk head-of-line blocking if a slow leader stalls the pipeline, forcing production deployments to use a single leader.

The system uses an Additive Increase, Multiplicative Decrease (AIMD) control loop based on the direct decision rate (the fraction of slots committed via the fast rule) observed in the agreed-upon committed DAG. This measurement requires no extra messages or cryptography and is deterministic across validators.

Key performance metrics include: Healthy Networks: Latency is 6–13% lower than single-leader configurations by leveraging multiple leaders. Degraded Networks: It automatically reduces the leader count to match the safety and latency of a single leader, remaining 35–56% faster than static multi-leader configurations. * Generality: It preserves safety and liveness across Byzantine, crash-only, and mixed fault models and is currently being integrated into the Sui blockchain.

Context and problem. The paper addresses a core tension in DAG-based BFT consensus: validators can propose blocks concurrently, forming a block DAG, but transaction commit is still paced by a smaller set of designated leader blocks. Allowing multiple leader slots per round can reduce queuing latency and improve utilization, but production systems often fall back to a single leader because of head-of-line blocking. If one leader is slow or delayed, the commit pipeline can stall for at least one leader timeout, and the delay can propagate across several waves if the system must wait for a fallback or indirect path before progress can resume.

Barnacle’s contribution. Barnacle proposes an adaptive multi-leader scheduling policy that tries to recover the latency benefits of multiple leaders without exposing the system to the same pipeline stalls. Instead of treating leader slots as a fixed, serial dependency, it dynamically manages how many leaders are active, when they are scheduled, and how the system reacts when a leader lags. The central insight is that the bottleneck in multi-leader DAG consensus is not parallelism itself, but the scheduling and failover mechanism: a slow leader should not force the entire round to wait if other leader slots can safely continue advancing commit progress.

Why it matters. For high-throughput, low-latency ledger designs, this matters because DAG-based consensus aims to combine concurrent block production with fast finality, but production usability depends on robust behavior under heterogeneous network conditions. If Barnacle can make multi-leader scheduling safe and stable despite delayed validators, it could reduce commit latency, improve tolerance to stragglers, and make DAG-based systems more practical in real deployments where validator timing variability is common.

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

Barnacle addresses a practical bottleneck in DAG-based consensus systems, where validators propose blocks concurrently but only designated leader blocks are used to drive transaction commit. In such protocols, using multiple leader slots per round can reduce transaction queuing latency by creating more frequent commit points. However, production deployments often fall back to a single leader because of head-of-line blocking: if one leader is slow or unresponsive, the commit pipeline can stall for at least one leader timeout, and in some cases the delay can propagate across several waves when the protocol must wait for a fallback path.

The key contribution is an adaptive multi-leader scheduling approach that makes multi-leader operation more robust without sacrificing the latency benefits of parallel block production. Instead of relying on a fixed leader schedule, Barnacle dynamically manages leader slots in response to observed behavior, allowing the system to continue committing transactions even when individual leaders are delayed. The work reframes the leader-selection problem as a scheduling tradeoff among commit frequency, liveness, and resilience to stragglers, while preserving the ordering guarantees required by DAG-based consensus.

This matters because DAG-based consensus is attractive for high-throughput, low-latency blockchain designs, but its performance is often limited by conservative production choices such as single-leader scheduling. By directly targeting head-of-line blocking, Barnacle offers a path to more efficient multi-leader pipelines with lower tail latency, better utilization of parallel validator proposals, and stronger resilience to partial failures. It is especially relevant to researchers and engineers designing consensus protocols where parallel block creation must be reconciled with deterministic transaction ordering.