Seamless Reconfiguration for DAG-BFT (Technical Report)
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Seamless Reconfiguration for DAG-BFT (Technical Report)".
Jane: Here's the gist of the paper. In this work, a seamless reconfiguration protocol for asynchronous Directed Acyclic Graph (DAG)-based Byzantine Atomic Broadcast is presented, allowing membership and quorum thresholds to change without halting dissemination.
Tom: This is achieved by extending multi-configuration operation to the DAG itself, where every block records its configuration history, pending reconfiguration status, and enabled configurations for each round.
Jane: The key contributions are: 1.
Tom: Defining Dynamic DAG-structured Byzantine Broadcast (Dynamic DAGBB), a reconfigurable dissemination abstraction whose integrity and consistency are maintained during transitions.
Paper summary: Tom: So, looking at the paper "Seamless Reconfiguration for DAG-BFT (Technical Report)", it's basically presenting a provably correct way to run these DAG based protocols when the membership isn't static. The main point is that you can change who is in the group without stopping everything >
Jane: It’s about moving from static systems to dynamic ones, and they’ve defined this Dynamic DAG-structured Byzantine Broadcast abstraction which handles integrity even during those transitions >
Lu: They provide a concrete protocol with a four round transition window and state transfer that lets joining processes synchronize their state without pausing the main broadcast flow >
Meng: For deployment, this means our systems could handle node churn much more gracefully, which is exactly what we need for large scale operations where things are always changing >
Lalam: The authors show how leader election can be scoped to a single configuration using perfect coins and how they maintain total order across different configurations through a backward scan mechanism >
Tom: It moves the discussion forward by showing that you don't have to throw away the safety properties just because your membership set is fluid, provided you follow their specific rules for those transitions >
Jane: The implications are that we can build more resilient distributed systems where nodes join and leave constantly, without sacrificing the core guarantees of atomic broadcast >
Conclusion: Tom: So we've been looking at this paper called "Seamless Reconfiguration for DAG-BFT," and it’s about making sure a distributed system based on a Directed Acyclic Graph can change its members—add or remove nodes—without stopping the whole broadcast process.
Jane: I mean, that sounds like you could have a huge network of computers running, and you want to take one off without everyone freezing. So what is the core idea here for someone who isn't deep in blockchain stuff?
Tom: The core idea is they figured out how to reconfigure the system while it’s still broadcasting data. They extended the operation itself onto the graph structure so that every block remembers its history and what configurations are active right now.
Lu: What that means practically is, when you want to change who's in the group or how many nodes you need for a quorum, you don't have to halt everything just to get the new rules settled. It’s built into the structure itself.
Meng: For us on the engineering side, it’s about deployment. If we have a cluster that needs scaling or maintenance, being able to handle those membership changes without downtime is a massive win for reliability and keeping things operational at scale.
Lalam: I see what they did with their leader election too. They adapted the way leaders are chosen based on the current configuration requirement, which is key because it keeps things consistent even when you're in different states.
Jane: It seems like the big takeaway is that you don't have to sacrifice safety guarantees just because your group of participants isn't fixed from day one. They show a way to maintain consistency during those transitions.
Tom: Exactly. They built this dynamic abstraction, and they proved that as long as you follow their rules for switching configurations, the system stays correct even when things are shifting under the hood. Next up, we’re going to look at how they proved that progress actually happens reliably in these changing conditions.
National University of Singapore · University of Stavanger, Norway · Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany
cs.DC
Submitted: 2026-10-01
Updated: 2026-11-15
Comments: Accepted to OPODIS 26
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 100/100
The gist: In this work, a seamless reconfiguration protocol for asynchronous Directed Acyclic Graph (DAG)-based Byzantine Atomic Broadcast is presented…
Key concepts
- Dynamic DAGBB
- This is an abstraction for reconfigurable dissemination that maintains integrity and consistency even when the network's membership changes. It ensures that data flow remains reliable throughout any reconfiguration process, preventing interruptions during threshold updates.
- Dynamic DAG Byzantine Atomic Broadcast
- This is the main protocol built on top of Dynamic DAGBB. It defines the guarantees for a system where membership and quorum rules are constantly shifting. The paper explicitly states which standard Byzantine broadcast properties must be given up when these changes occur.
- Configuration-scoped perfect coin
- This is a randomized leader election method adapted for changing membership. Instead of one static coin, the process uses coins specific to the current configuration's quorum requirements. This ensures that leader selection is valid relative to the current state, maintaining correctness during transitions.
Terminology
Summary
In this work, a seamless reconfiguration protocol for asynchronous Directed Acyclic Graph (DAG)-based Byzantine Atomic Broadcast is presented, allowing membership and quorum thresholds to change without halting dissemination. p. 0 This is achieved by extending multi-configuration operation to the DAG itself, where every block records its configuration history, pending reconfiguration status, and enabled configurations for each round. p. 1
The key contributions are:
-
Defining Dynamic DAG-structured Byzantine Broadcast (Dynamic DAGBB), a reconfigurable dissemination abstraction whose integrity and consistency are maintained during transitions. p. 2
-
Defining Dynamic DAG Byzantine Atomic Broadcast on top of this abstraction, explicitly stating which guarantees of the static problem must be sacrificed under changing membership and why. p. 2
-
Providing a seamless reconfiguration protocol implementing configuration-scoped reliable broadcast, a four-round transition window, and state transfer admitting joining processes without pausing dissemination. p. 2
-
Adapting DAG-Rider’s randomized leader election to changing membership by scoping its perfect coin to a single configuration, with proofs confirming the composition satisfies the definitions. p. 2
Consistency is maintained by ensuring blocks are admissible based on metadata that includes checks on pending reconfiguration messages and enabled configurations. p. 2 Transitions occur via a sequence of authenticated reconfiguration messages, where each transition is defined by an install round chosen by the process, ensuring well-spacing of transitions and guaranteeing correct processes eventually advance through infinitely many stable waves with probability one. Leader election utilizes configuration-scoped perfect coins based on current quorum requirements, while total order across configurations is maintained via a backward scan mechanism. p. 2 The overall correctness proof establishes Dynamic DAG Byzantine Atomic Broadcast under the assumption that the dealer follows a specific issuance rule. p. 5
The protocol details reconfiguration procedures (Algorithm 4), involving waiting for admissible blocks and invoking transition-specific operations like DAG-Transition-Append, alongside procedures for joining processes to synchronize state. Finalization uses configuration-scoped leader election to establish a total order of leader blocks across configurations. p. 2
Detailed analysis involves several lemmas and corollaries establishing the protocol's properties:
-
Agreement Maintenance: Lemmas 16 and 17 ensure that agreement through round r preserves alignment of round- (r+1) enabled-configs values, provided a correct process in configuration R l still enables R l.
-
Process Behavior During Removal: Corollary 29 bounds the installation transition round (a h) for a removed process relative to the earliest correct install transition round (t'), ensuring its removal does not compromise quorum certificates in subsequent rounds.
-
Leader Election and Progress: Lemmas 30 through 40 detail how processes (old members, joining processes) advance through transition rounds (InstallTransition) based on discovery rounds (u), showing tight bounds on these round numbers (e.g., t in [u-1, u+1]). Lemma 47 confirms that a valid transition establishes completion, departure, progress, and the BRB Agreement premise for the next induction step. p. 9
-
Probabilistic Progress: Theorem 72 establishes Probabilistic Progress by relying on corollaries 66 and 67 (which ensure infinitely many stable waves under RL) and the conditional probability bound from Lemma 18. This ensures that with probability one, every active correct member eventually finalizes infinitely many blocks. p. 9
-
Integrity and Total Order: The deterministic Integrity and Total Order conclusions are verified by showing that the underlying Dynamic DAG-structured Byzantine Broadcast (Lemma 51), integrity checks (Corollary 64), and nested canonical leader prefixes (Lemmas 62, 63) hold.
The proof structure confirms that the deterministic conclusions do not rely on the Unpredictability or Fairness properties of the configuration-scoped perfect coin, while Probabilistic Progress relies on corollaries ensuring infinitely many stable waves under RL, Lemma 18's conditional probability bound, and Theorem 72.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Seamless Reconfiguration Capability: The system can change membership and quorum thresholds while dissemination continues without halting operations, allowing correct processes to
continue producing blocks and advancing rounds while the membership and its quorum thresholds change.
-
Dynamic DAG Structured Byzantine Broadcast: The protocol implements a
repeated, round-indexed broadcast abstraction over the finite configuration sequence R1, . . . , RL,
ensuring thatDAG-Integrity
andDAG-Consistency
hold even while correct processes are at different stages of a transition. -
Configuration Scoped Leader Election: Leader election is scoped to configurations, meaning
instances of different configurations use separate keys, and their shares are never combined,
which ensures that only one configuration can have sufficient leader-voting blocks in a wave, even during reconfiguration. -
Transition Progress and Completion: The protocol guarantees that
Every valid transition eventually completes at every correct retained or joining process,
providing a mechanism for processes to leave gracefully after completing the transition tasks. -
Joining Process Functionality: A joining process can successfully integrate into the system by
repeatedly requesting admissible blocks from every identity in knownj and sends another request after accepting a reply or when knownj changes,
eventually reaching a state where itstops producing blocks at round r + 6, and completely leaves when it sees fl+1 + 1 blocks in round r + 7.
-
Total Order Maintenance: The protocol establishes a total order of leader blocks such that
if one active correct process finalizes B before B′, no active correct process finalizes B′ without first finalizing B,
ensuring a consistent sequence of finalized leader blocks across configuration changes.
Sources
Related papers
- BatchGen: An Architecture for Scalable and Efficient Batch Inference
- ELDR: Expert-Locality-Aware Decode Routing for PD-Disaggregated MoE Serving
- iScheduler: Reinforcement Learning-Driven Continual Optimization for Large-Scale Resource Investment Problems
- TIRx: A Unified Tile Primitive ML Compiler Across Heterogeneous Backends
- AgentWeave: Efficient Distributed Agent Serving via Flow Decomposition
- RouteBalance: Fused Model Routing and Load Balancing for Heterogeneous LLM Serving