PaperlayerView exact revision on arXiv

Source-linked AI summary

Flamingo: On Load Balancing in DAG-based Consensus Protocols

Zhen Ping Khor, Garvit Gupta, Mohammad Javad Amiri, Boon Thau Loo

arXiv:2609.28361v2cs.DCcs.DB

TL;DR

DAG-based BFT protocols can lose performance under workload skew and heterogeneous capacity, despite concurrent dissemination and parallel execution. Flamingo balances client assignments and executor scheduling, recovering performance across imbalanced conditions while adding negligible overhead when balanced.

  • Problem

    DAG-based BFT protocols can suffer performance degradation under workload imbalance and validator heterogeneity, even though they scale transaction dissemination and execution.

    Source: §1 · pp. 1–2

  • Method

    Flamingo rebalances client accounts using certified-DAG signals and schedules committed transactions across executor workers deterministically while preserving order.

    Source: §1 · p. 2

  • Results

    Flamingo recovers throughput and latency under submission skew, heterogeneous validator bandwidth, and shifting hotspots, with negligible overhead when balanced.

    Source: §1 · p. 2, §8 · p. 14

  • Takeaways & Limitations

    Both ordering- and execution-layer balancing are needed to address their respective bottlenecks.

    Source: §1 · p. 2, §8 · p. 14

    Flamingo’s design extends to certified-DAG protocols but does not directly carry over to uncertified-DAG protocols.

    Source: §4 · p. 4

Abstract

from arXiv · show

Distributed data management systems deployed in untrusted environments rely on Byzantine Fault-Tolerant (BFT) consensus protocols to tolerate malicious failures. DAG-based BFT protocols improve throughput by letting validators disseminate transactions concurrently and by scaling execution across multiple workers. However, imbalances in workload or resource capacity can still degrade performance significantly. This paper presents Flamingo, a load-balancing protocol for certified DAG-based BFT protocols that addresses imbalance at both the ordering and execution layers. At the ordering layer, Flamingo periodically migrates client accounts away from overloaded validators, adapting to skewed submissions and heterogeneous validator capacity while preserving correctness under Byzantine faults, with migrations taking effect only through the committed log. At the execution layer, Flamingo redistributes committed transactions across executor workers using a deterministic, order-preserving scheduler that balances load and minimizes cross-worker data movement, without centralized coordination or costly distributed commit. Built on top of Narwhal and Tusk, our prototype shows that Flamingo recovers throughput and latency under workload skew, validator heterogeneity, and shifting hotspots, adds negligible overhead when the system is balanced, and needs load balancing in both layers, since resolving only one shifts the bottleneck to the other.

1 INTRODUCTION

DAG-based BFT protocols improve on leader-centered designs, but workload skew and validator heterogeneity can sharply reduce performance. Flamingo addresses imbalance at both ordering and execution layers, with migrations activated through committed evidence and deterministic scheduling that preserves order.

1 INTRODUCTION

  • Traditional BFT leader designs cap throughput at the leader’s capacity, while leader rotation adds synchronization overhead and still requires peak-capacity provisioning.Multi-proposer protocols reduce underutilization but remain vulnerable to a single node’s failure because dissemination and consensus are coupled.Source: §1 · p. 1
  • ∼58 ktps (45% reduction) with one node at one-third bandwidth, ∼44 ktps (58% reduction) under 90% submission skew, and ∼39 ktps (63% reduction) with 90% execution on one worker.The balanced four-node deployment reaches approximately 106 ktps.Source: Figure 1 · p. 1, §1 · p. 1
  • Both layers need balancing: ordering faces skewed submissions and heterogeneous capacity, while execution faces hot shards and coordination costs for distributed transactions.Execution must also preserve consensus order deterministically across validators with different worker counts.Source: §1 · pp. 1–2
  • Flamingo rebalances client-validator assignments from certified DAG signals and schedules committed transactions across executor workers while preserving consensus order.Ordering migrations take effect only after matching committed decisions and the receiver’s committed acceptance; execution uses deterministic scheduling and data fusion.Source: §1 · p. 2
  • Flamingo recovers throughput and latency under skew, heterogeneous validator bandwidth, and shifting hotspots, with negligible overhead when load is balanced.The prototype implements ordering-layer measurement and migration decisions; Byzantine safety of the migration-commit lifecycle is established analytically.Source: §1 · p. 2

2 DAG-BASED BFT CONSENSUS

DAG-based BFT protocols decouple transaction dissemination from consensus, allowing nodes to build transaction graphs concurrently and derive a common order from local views. Certified blocks support availability and causality, while performance remains sensitive to workload skew and resource heterogeneity.

2 DAG-BASED BFT CONSENSUS

  • Validators broadcast blocks concurrently into a DAG, and each node derives the total order independently from its local graph without an additional communication phase.DAG construction proceeds asynchronously to the total order, so consensus no longer blocks transaction dissemination.Source: §2 · p. 2
  • A node advances rounds after receiving n−f certificates, and each Proof of Availability certifies that at least f+1 honest validators stored the block.Quorum intersection prevents equivocation, and certified prior-round references support availability and causality.Source: §2 · pp. 2–3
  • Replicas commit blocks reachable from an elected leader’s block and thereby derive the same total order; executor workers then execute transactions against their shards.Blocks not yet ordered are committed in later waves.Source: §2 · p. 3, Figure 2 · p. 3
  • Throughput and latency degrade sharply when client load is skewed or nodes differ in capacity, motivating balance across ordering and execution.The section’s performance motivation is illustrated by Narwhal and Tusk under workload and resource imbalance.Source: §2 · p. 3

3 FLAMINGO OVERVIEW

Flamingo runs validator- and executor-level load balancing alongside consensus. It uses committed migration records to change client assignments and deterministic scheduling to distribute execution while preserving the committed order.

3 FLAMINGO OVERVIEW

  • Validator-level balancing migrates excess client load using certified DAG signals, with assignments changing only after committed evidence and the target validator’s committed acceptance.A bounded relay fallback keeps accounts serviceable when their assigned validator is unresponsive.Source: §3 · p. 3
  • Every executor worker receives the committed batch and independently runs the same deterministic scheduler, so workers derive identical assignments without a central dispatcher.The scheduler preserves the consensus-determined order even when validators have different numbers of executor workers.Source: §3 · p. 3
  • Flamingo schedules transactions across workers to balance execution load while minimizing data movement for transactions spanning multiple workers.Transactions accessing multiple workers require the relevant state to be transferred among them.Source: §3 · p. 3
  • The prototype builds on Narwhal and Tusk, whose certified DAG and multi-worker architecture provide the structure Flamingo uses.The design requires certified-DAG properties.Source: §3 · p. 3

4 VALIDATOR LEVEL LOAD BALANCING

Flamingo rebalances validator assignments using certified DAG signals, with assignment changes gated by committed protocol state. Its signal model and migration lifecycle address divergent DAG views and Byzantine misreporting while running off the critical path.

4.1 Signal Model and Trust Classification

  • Certified headers carry proposal timestamps, queue delays, and per-account counts; counts are recomputable, while clock-derived estimates assume bounded skew and self-reported delays affect shedding magnitude, not assignment safety.The tracking window excludes the unstable frontier; a larger stability parameter yields more consistent but staler signals.Source: §4 · p. 4, §4.1 · p. 5

4.2 Load Balancing Algorithm

  • Donors must exceed declared capacity and a queue-delay threshold; migration estimates combine observed and inferred excess, cap shedding, then assign heavy accounts to capacity-qualified receivers with the lowest client latency.Queue delay is used because it grows under sustained overload regardless of its root cause, while the migration cap limits the effect of inflated self-reports.Source: §4.2 · pp. 5–6

4.3 Migration Protocol

  • Committed matching decisions and receiver acceptance gate assignment changes; deterministic transitions preserve agreement, while relay fallback admits requests when the assignee is unresponsive.A Byzantine assignee can throttle clients: fallback is rate-limited, and relay-only accounts’ zero validated counts exclude them from migration candidates; forced migration is left for future work.Source: §4.3 · pp. 6–7

5 EXECUTOR LEVEL LOAD BALANCING

Flamingo schedules committed transactions across executor workers to balance load while preserving consensus order and limiting cross-worker data movement. Its decentralized scheduler uses evolving ownership state, with the trade-off that every executor worker ingests the full committed stream.

5 EXECUTOR LEVEL LOAD BALANCING

  • Skewed access can leave executor workers with unequal transaction loads, while distributed transactions and finer sharding increase cross-worker coordination challenges.The scheduler must preserve consensus-determined order even when validators use different numbers of executor workers.Source: §5 · p. 7
  • Flamingo assigns each committed transaction to a designated master worker, which pulls remote inputs and installs writes locally, avoiding a write-back to originating workers.This reduces distributed-transaction cost to one one-way transfer; later transactions assigned to the same master can avoid transfers when accessing recently fused state.Source: §5 · p. 7
  • Every executor independently schedules the full committed batch, avoiding a centralized dispatcher and producing identical assignments from the same inputs.The scheduler updates a batch-local overlay after each assignment; the final overlay becomes the next batch’s base partition map.Source: §5 · pp. 7–8
  • Each executor worker ingests the full stream, making its LAN ingress m times that of a sub-batch design; the authors target m≤10 where LAN capacity can absorb this in-cast.The stated condition is that per-executor LAN ingress bandwidth exceeds worker WAN egress bandwidth by at least a factor of m.Source: §5 · pp. 7–8
  • The scheduler processes transactions in consensus order, using ownership votes, capacity limits, affinity, and deterministic tie-breaking to assign workers.It takes the fast path when the read/write set maps to one worker with capacity, otherwise favors the highest-vote worker with capacity, then falls back to the least-loaded worker.Source: §5 · p. 8

6 EVALUATION

The evaluation measures Flamingo’s load-balancing effects separately at the ordering and execution layers, which have different bottlenecks and baselines. It evaluates the ordering signal-and-decision path and the decentralized full-batch execution scheduler.

6 EVALUATION

  • The evaluation quantifies mitigation of load-imbalance degradation, comparing ordering-layer performance with vanilla Narwhal and execution scheduling with layer-specific baselines.At execution, it measures throughput with scheduling disabled and the scheduling-cost versus remote-read trade-off against Hermes-style prescient routing.Source: §6 · p. 8
  • Flamingo’s ordering prototype adds per-account validated transaction counts, proposal timestamps, and average batch queue delay to block headers and certificates, so decisions use DAG metadata without a dedicated metric-exchange round.The prototype exercises misreported self-declared signals; migration-commit lifecycle guarantees are established analytically, while execution uses decentralized full-batch scheduling.Source: §6 · p. 8

6.1 Experimental Setup

Experiments use CloudLab xl170 nodes with shaped WAN conditions and resource caps to evaluate Flamingo under controlled submission patterns. SmallBank workloads begin balanced and then switch to configured skewness.

6.1 Experimental Setup

  • Experiments ran on CloudLab xl170 nodes with Xeon E5-2640 v4 processors, 64 GB memory, SSD storage, and shaped WAN bandwidth and 100 ms RTT.Primary and worker bandwidth were capped at 300 Mbps and 600 Mbps, respectively; CPU sets were pinned separately for workers, primary, clients, and the OS.Source: §6.1 · p. 8
  • The SmallBank benchmark uses 1 M users, with one client per validator submitting transactions for its region’s accounts at a fixed rate and configured skewness.Account ranges map to co-located validators; transaction payloads are padded to the configured size, and clients buffer requests in an unbounded channel.Source: §6.1 · p. 9
  • The baseline uses four single-worker validators, and ordering load balancing runs every 60 rounds over a 30-round window with a migration cap of four.A 30 ms minimum queue-delay threshold filters network jitter; capacity is estimated from egress bandwidth because broadcast fan-out is expected to saturate the network before CPU or disk.Source: §6.1 · p. 9
  • Each run begins with four minutes of balanced submissions before switching to configured skewness, and lasts 15 minutes unless otherwise stated.Committed throughput is binned at 10-second granularity and smoothed over three bins; latency measures submission to consensus commitment under high load.Source: §6.1 · p. 9

6.2 Validator Level Load Balancing

The evaluation tests validator-level load balancing across submission rates, workload skew, bandwidth heterogeneity, committee sizes, shifting hotspots, and misreporting. Flamingo recovers performance across these conditions, with negligible overhead when no migration is needed.

6.2.1 Impact of Submission Rate.

  • At higher submission rates, Flamingo dissipates the skew-induced backlog and recovers throughput and latency, whereas the baseline remains degraded.At 20 ktps, even 90% concentration remains below the overloaded validator’s processing capacity, so Flamingo migrates no accounts.Source: §6.2.1 · p. 9, §6.2 · p. 9

6.2.5 Adaptivity to Shifting Hotspots.

  • When the hotspot shifts from v0 to v1, Flamingo issues a second migration burst and recovers throughput again, while the baseline remains degraded.The experiment shifts the hotspot at 10 minutes during a 110 ktps, 90%-skew run.Source: Figure 6 · p. 10, §6.2.5 · p. 11

6.2.2 Impact of Workload Skewness.

  • Across 60%, 90%, and 99% skew at 110 ktps, Flamingo’s recovered throughput approaches the balanced-phase level, while the baseline remains degraded.Greater skew requires more migrations and longer backlog draining; the 99%-skew run converges roughly two minutes later than the 60%-skew run.Source: §6.2.2 · pp. 9–10, Figure 5 · p. 10

6.2.3 Impact of Bandwidth Heterogeneity.

  • With f bandwidth-limited validators, a second migration wave restores throughput near the offered rate and mean latency to its balanced-phase level.With f+1 slow validators, Flamingo cannot restore the balanced-bandwidth commit rate, but latency returns near the balanced-phase level by the run’s end as backlog drains.Source: §6.2.3 · p. 10

6.2.4 Scalability with Number of Validators.

  • Across 4, 10, 16, and 21 validators, Flamingo recovers throughput to 90 ktps and mean latency to the balanced-phase level; recovery takes longer as committee size increases.The per-donor excess and per-anchor migration cap shrink as committee size grows, reducing load shed per invocation.Source: §6.2.4 · pp. 10–11

6.2.6 Robustness to Misreporting Validators.

  • Under skew, only inflated capacity degrades performance: it triggers one bounded migration burst, then throughput and latency remain degraded for the rest of the epoch.The harm is bounded by per-anchor migration targets and the epoch boundary, when capacity is recommitted; affected clients retain relay fallback progress.Source: Figure 7 · p. 11, §6.2.6 · p. 11

6.3 Executor Level Load Balancing

Flamingo’s execution-layer scheduler scales throughput under executor skew and trades some remote-read locality against substantially lower scheduling cost. Its evaluation compares scale-out performance and scheduler behavior with PilotFish and Hermes.

6.3.1 Scalability Experiment.

  • The scalability experiment stresses executor imbalance by assigning 50% of transactions initially to one worker and varying executor and validator workers from 1 to 8.Distributed transactions touch two accounts; the microbenchmark instead uses synthetic key sets with controlled transaction size and temporal overlap, comparing scheduler runtime and remote reads in a simulator.Source: §6.3.1 · pp. 11–12, §6.3.2 · p. 12
  • At m=8, Flamingo reaches ∼154 ktps (about a 6.9× speedup over m=1), while PilotFish saturates near 100 ktps in the single-shard workload.Flamingo outperforms PilotFish across worker counts in both single-shard and 20% distributed workloads.Source: Figure 8 · p. 12, §6.3.1 · p. 12

6.3.2 Scheduler Microbenchmark.

  • Roughly 2 ms per batch of 1000, Flamingo’s scheduler is about three orders of magnitude faster than Hermes, whose runtime reaches the multi-second range.Flamingo makes one deterministic forward pass that preserves committed order; Hermes iteratively reroutes a permuted batch.Source: Figure 9 · p. 12, §6.3.2 · p. 12
  • Hermes incurs roughly 20–30% fewer remote reads for light and medium transactions, with a narrower gap for heavy transactions, while Flamingo reduces scheduling time by ∼1000×.The trade-off reflects Hermes’s use of reordering to exploit future locality, which Flamingo cannot use.Source: §6.3.2 · p. 12, Figure 10 · p. 12
  • Flamingo’s deterministic scheduler runs as a single forward pass, preserving the agreed transaction order while balancing work across executor workers.The results support running the scheduler independently on every executor worker.Source: §6.3.2 · p. 12

6.4 End-to-End Evaluation

The end-to-end evaluation tests validator, executor, and combined 90% imbalances. Results show that each load-balancing layer addresses its corresponding bottleneck, while full Flamingo restores end-to-end performance under combined imbalance.

6.4 End-to-End Evaluation

  • Under combined imbalance, only full Flamingo restores E2E performance to the offered rate; addressing just one layer shifts the bottleneck to the other.Validator-only balancing admits and commits the full rate but leaves an execution backlog; executor-only balancing and the baseline remain bottlenecked at ordering.Source: Figure 11 · p. 13, §6.4 · p. 13
  • The full-pipeline test uses four validators, three executor workers per validator, a 110 ktps submission rate, and 90% validator, executor, or combined imbalance.It measures committed performance and end-to-end performance, defined as transactions committed and executed.Source: §6.4 · p. 13
  • With validator-level imbalance, only full Flamingo and validator-only balancing dissipate the backlog and return committed and E2E throughput to the offered rate, with latency returning to balanced-phase levels.Executor-only balancing tracks the baseline because post-commit scheduling cannot relieve an overloaded ordering path.Source: §6.4 · p. 13
  • With executor-level imbalance, all variants sustain the offered committed rate, but only full Flamingo and executor-only balancing match E2E throughput to that rate with flat latency.Without executor balancing, execution backlog lowers E2E throughput and increases E2E latency despite unaffected consensus.Source: §6.4 · p. 13

7 RELATED WORK

The related work distinguishes Flamingo from approaches that rebalance consensus roles, redistribute data, or schedule execution. Its design targets client-to-validator assignments and ordered execution within a certified DAG-based BFT system.

Validator level load balancing

  • Stratus [25] forwards excess microblocks to a lightly loaded proxy, but the paper reports this adds a relay step rather than removing load in certified DAG mempools.The authors’ implementation of the proxy approach did not yield improvements.Source: §7 · p. 13
  • Shoal, Shoal++, and HammerHead [53] [59] reassign consensus roles, while Flamingo instead rebalances client demand over certified DAG mempools using existing DAG metadata.Marlin redistributes data ownership across multiple BFT instances; Flamingo migrates client-to-validator assignments within one leaderless DAG-BFT instance through the existing BFT log.Source: §7 · p. 13

Time-derived signals under Byzantine faults

  • Flamingo’s header timestamps and queue delays are migration signals only, unlike systems where time-derived signals affect ordering; misreporting may degrade migration quality but cannot affect ordering safety.The signals are filtered by medians and capped by certified throughput.Source: §7 · p. 14

Executor level load balancing

  • Among the compared execution schemes, Hermes and Flamingo perform load-aware scheduling; Flamingo preserves committed order and supports validators with different executor-worker counts.Table 1 compares bandwidth, lock-holding window, scheduling cost, and load balancing; PilotFish [37] fixes object-to-worker placement at dispatch.Source: §7 · p. 14, Table 1 · p. 14

8 CONCLUSION

The conclusion presents Flamingo as a two-layer load-balancing mechanism for certified DAG-based BFT protocols. It reports performance recovery across several imbalance settings and finds both layers necessary to address their respective bottlenecks.

8 CONCLUSION

  • Flamingo dynamically rebalances client-validator assignments using load signals from the certified DAG and a committed migration protocol.The protocol preserves consistent assignments and serviceability under Byzantine faults.Source: §8 · p. 14
  • At execution, a deterministic, order-preserving scheduler balances work across executor workers while minimizing data movement.Source: §8 · p. 14
  • On Narwhal and Tusk, Flamingo recovers performance under workload skew, validator heterogeneity, and shifting hotspots, with negligible overhead when load is balanced.The end-to-end results show that both mechanisms compose effectively and both layers must be addressed to remove their bottlenecks.Source: §8 · p. 14
Loading 2609.28361v2…