Minimizing Commit Rules for DAG-based Atomic Broadcast

Minimizing Commit Rules for DAG-based Atomic Broadcast Petr Kuznetsov Télécom Paris, Institut Polytechnique de Paris, France

Maxence Perion # Université Paris-Saclay, CEA, List, France

Sara Tucci-Piergiovanni Université Paris-Saclay, CEA, List, France

arXiv:2608.18029v1 [cs.DC] 18 Aug 2026

Abstract A popular class of Byzantine fault-tolerant atomic broadcast protocols rely on directed acyclic graphs (DAGs) that represent causal relations between broadcast messages. Each process applies a protocol-specific commit rule on its local DAG to determine which vertices can be delivered in a total order. Intuitively, commit rules that impose fewer conditions on the DAG to order its vertices imply more efficient protocols, as the broadcast messages are delivered with lower latency. In this paper, we define commit rules on an uncertified round-based DAG construction, and introduce a sub-rule relation between them: a commit rule cr1 is a sub-rule of a commit rule cr2 if, for any DAG, the set of vertices committed by cr1 contains all vertices committed by cr2 . We use the sub-rule relation to determine a minimal commit rule in an eventually synchronous model and a minimal commit rule in an asynchronous model, namely, two commit rules that require the least conditions on the DAG to safely commit any set of vertices in their respective models. To the best of our knowledge, no existing DAG-based atomic broadcast protocol relies on such minimal commit rules: we introduce Minnow, a new protocol for DAG-based atomic broadcast, which can be instantiated in both eventually synchronous (S-Minnow) and asynchronous networks (A-Minnow). 2012 ACM Subject Classification Theory of computation → Distributed algorithms; Computer systems organization → Dependable and fault-tolerant systems and networks Keywords and phrases Atomic Broadcast, DAG, Commit Rule, Optimality Category Draft: please read with caution, some proofs are missing and the content may change

1

Introduction

Atomic Broadcast ensures that correct processes agree on a totally ordered sequence of broadcast messages. A prolific line of recent protocols ([6, 11, 7, 2, 1, 5], to name a few) rely on constructing an ever-growing DAG, where the vertices represent the messages (or blocks) to be ordered and edges represent causal dependencies between them. Processes use some slots, i.e., certain positions of the DAG, as leaders (or anchors), which are common reference points for all processes to order the vertices of the DAG in the total order. Leader slots are typically selected either deterministically, e.g., in a round-robin fashion, or randomly, e.g., using a common coin. Correct processes needs to agree on which vertices to commit in the total order, despite Byzantine failures that may, for instance, cause correct processes to see different vertices in the same leader slot; and despite network delays that may cause, for instance, correct processes to see different vertices in the same time window. To this end, a process commits vertices only when a protocol-specific commit rule is enabled in its local DAG for a vertex in a leader slot, i.e, when some conditions on the DAG are satisfied for that vertex. For instance, the commit rule of DAG-Rider [6], requires, among other things, that there is 2f + 1 paths to a vertex in a leader slot, where f is the number of Byzantine processes.

2

Minimizing Commit Rules for DAG-based Atomic Broadcast

On one hand, the commit rule restricts when a vertex can be committed in order to safely produce a common total order; and on the other hand, less restrictive conditions imply that more vertices are committed faster, which leads to lower latency and higher throughput. In this paper, we characterize what a minimal commit rule is, i.e., the weakest conditions on local DAGs to safely commit any vertex. To do so, we focus on a communication component shared by many recent protocols ([7, 2, 1, 5], for instance), where processes use best-effort broadcast to issue vertices in rounds: each vertex has an edge to at least 2f + 1 vertices issued by distinct processes in the previous round, where f is the number of Byzantine processes. In order to aim for minimal latency, local DAGs are uncertified: no mechanism in the communication component prevents Byzantine processes from issuing two vertices in the same round, contrarily to certified DAGs where processes use byzantine reliable broadcast to issue vertices. We define commit rules on top of this communication component as functions that take a local DAG as input and return a sequence of committed vertices. A commit rule is defined by a pattern, i.e., the template vertices that are required to appear in the DAG to commit a vertex v. A leader vertex is committed if and only if we can find the pattern as a sub-DAG of the local DAG, up to renaming some vertices. We introduce the sub-rule relation between commit rules, the technical tool that allows us to prove that a commit rule is minimal. Intuitively, a minimal commit rule for Byzantine Atomic Broadcast must be both sufficient, i.e., it should solve the problem, and necessary, i.e., no sufficient commit rule imposes weaker conditions on the DAG. Informally, we say that a commit rule cr1 is a sub-rule of a commit rule cr2 if, for any DAG, the set of vertices committed by cr1 contains all vertices committed by cr2 . This is achieved when the pattern of cr1 defines sub-DAGs of the DAGs defined by the pattern of cr2 , and then cr1 provably imposes weaker conditions on the DAG to commit vertices than cr2 . In practice, finding a sub-rule leads to lower latency and higher throughput: if a cr1 is a sub-rule of cr2 , then cr2 may require more rounds than cr1 to commit the same vertices, hence a lower latency; and/or there may be some executions where cr2 is not enabled for some vertices, while cr1 is enabled, hence a higher throughput. We determine a surprisingly simple commit rule that we show to be minimal for the eventually synchronous model: it only requires 2f + 1 edges pointing to the same vertex in the previous round, where f is the number of Byzantine processes, and that each concurrent leader vertex is already decided (either committed or skipped, i.e., will never be committed). Intuitively, this rule is minimal because relaxing the first condition would allow a Byzantine process to issue two different vertices in the same round such that two partitions of the correct processes commit a different vertex first; and relaxing the second condition would allow a correct process to commit a vertex v first and then v ′ , while another correct process ignores if v can be committed and commits v ′ first, which violates the agreement property of atomic broadcast. Regarding asynchronous networks, we adapt the minimal commit rule from eventual synchrony: instead of requiring 2f + 1 edges in the next round pointing to the same leader vertex, we require 2f + 1 paths starting from a vertex in the next two rounds (issued by distinct processes) and leading to the same leader vertex. Indeed, this extra round is required in asynchrony to prevent an adversary from systematically manipulating the DAG to never satisfy the commit rule for any vertex, thus preventing the liveness of the protocol. To the best of our knowledge, no existing DAG-based protocol uses such minimal conditions: we introduce Minnow, a new DAG-based atomic broadcast protocol, which comes in two flavors, eventually synchronous (S-Minnow) and asynchronous (A-Minnow). In the eventually synchronous model, S-Minnow commits vertices following the minimal commit

P. Kuznetsov, M. Perion, and S. Tucci-Piergiovanni

rule for this model and a deterministic sequence, e.g., round-robin, of l leaders each round. In the asynchronous model, A-Minnow uses the minimal commit rule for the asynchronous model but the leaders of round r are computed from a common coin and are revealed at round r + 3. The leaders are revealed one extra round after the expected conditions of the commit rule are already formed (or not) in the DAG, for each potential leader, in order to prevent the adversary from systematically manipulating the DAG to never satisfy the commit rule for a leader vertex [10]. To sum up, we make the following contributions: We define the class of commit rules for DAG-based atomic broadcast protocols (Section 3); We introduce a comparison relation between commit rules and use it to define minimal commit rules (Section 4) for both eventually synchronous and asynchronous networks; We introduce Minnow, a new protocol for DAG-based atomic broadcast that uses the minimal commit rules in each model (Section 5). We discuss the generality of this approach in Section 6 and conclude in Section 7. This document is only a draft: we leave related work and some proofs for a later version of the paper.

2

Communication Model

Model. We assume a distributed system of n processes. Up to f processes are prone to Byzantine faults, i.e., may deviate arbitrarily from their algorithms. A process that faithfully follows its prescribed algorithm is called correct. Informally, in a Byzantine Atomic Broadcast protocol, processes broadcast and deliver messages, so that every message broadcast or delivered by a correct process is eventually delivered by every correct processes, and correct processes deliver messages in the same order. We assume f < n/3 [9] (necessary to solve the problem) and we define Atomic Broadcast formally in Section 3.2. In the following, we define a commit rule that is minimal in both the eventually synchronous and the asynchronous models. DAG Construction. Each correct process maintains a local DAG, whose vertices represent messages and edges represent causal dependencies between them. Vertices are issued in rounds and each vertex has edges to vertices issued in the previous round. Vertices are valid only if they reference at least 2f + 1 valid vertices issued in the previous round by distinct processes. We assume that correct processes keep issuing valid vertices of the DAG. If a faulty process issues a vertex with an edge to a vertex that does not exist, then this vertex is never included in the DAG of correct processes. If a faulty process issues two valid vertices in the same round, then correct processes include both in their local DAG but when they issue their vertex for the next round, correct processes will choose (it does not matter how) only one vertex per process to add an edge to. If there is a path from ′ ′ a vertex v to a vertex v in a DAG D, we write v ⇝ v and we say that v is in the causal past of v ′ . If there is no causal path from a vertex v to a vertex v ′ and vice versa, we say that v and v ′ are concurrent. Regarding messages, we assume that every vertex issued or delivered by a correct process is eventually received by all correct processes, which can be guaranteed without assuming a byzantine reliable broadcast mechanism, but rather using a gossip protocol for instance. When we consider a partially synchronous network, we assume that correct processes wait for a ∆ time before moving to the next round, such that, after some unknown global stabilization time (GST), the vertex issued by a correct process in round r will include an edge to the vertex issued by each correct process in round r − 1. We

3

4

Minimizing Commit Rules for DAG-based Atomic Broadcast

denote by D the set of all DAGs that can be constructed by correct processes following these rules, and we call communication component the protocol responsible for building such DAGs. Correct processes only communicate using the vertices of the communication component and they compute the output of the atomic broadcast protocol by applying a commit rule (defined next) to their local DAG. Leaders DAG-based atomic broadcast protocols typically rely on a sequence of leader (or anchor) vertices: this sequence determines the order in which the protocol considers proposed vertices for commitment. Protocols designed for eventually synchronous networks usually use a deterministic, pre-defined, sequence of anchors; and protocols for asynchronous networks use a global coin to circumvent the FLP impossibility [4]. We assume that the commit rule has access to a function leaders that returns a sequence of leader slots that is consistent at all correct processes. A slot is a pair (p, r) that identifies a proposal, i.e., a vertex issued by process p in round r (but there may be no, or many such vertices if p is faulty). The commit rule iteratively considers the leader slots in the order defined by leaders and commits vertices when some conditions on the slot are satisfied in the DAG. When we compare two commit rules cr1 and cr2 using the sub-rule relation , we assume that they use a compatible leaders function for a given DAG D, i.e., cr1 ⪯ cr2 is possible only if the sequence s2 returned by leaders cr2 at round r is a subsequence of the sequence s1 returned by cr1 at round r.

3

Characterizing Commit Rules

3.1

Defining Commit Rules

We use the notion of witnesses, patterns and embeddings to define commit rules. Informally, witnesses are a set of vertices per round that are required to appear in the DAG to commit a vertex v, which forms a round-based structure also called a “wave”, and an embedding of the witnesses in an actual DAG D is a mapping of the witnesses into a sub-DAG of D. Finally, a pattern is the combination of some witnesses and additional constraints on the embedding of the witnesses in an actual DAG, for instance, that a leader vertex is in the causal past of the vertex to be committed or there is enough edges pointing to it. We say that a pattern is enabled for a vertex v if there exists an embedding of the witnesses on v in the DAG and the additional constraints are satisfied, and disabled otherwise. A commit rule is a function that, given a pattern P , follows the order defined by leaders and commits iteratively the leader vertices when P is enabled such that the output sequence of committed vertices is monotonic and grows eventually with the vertices issued by every correct process. For liveness [10], the commit rule may test at any time if the pattern is enabled for an undecided leader vertex, e.g., after receiving “old” vertices issued at a previous round, not only at the end of the current round. Formal definitions follow. ▶ Definition 1 (Witnesses). Some witnesses W are a finite collection W [0], W [1], . . . , W [k] with a distinguished vertex r such that W [0] = {r}. ▶ Definition 2 (Embedding). Let round(v) be the round of a vertex v in an actual DAG D = (VD , ED ). An embedding of some witnesses W on a vertex v in D is an injective map ϕ such that ϕ(r) = v, ∀i ∈ [0, k], ϕ(W [i]) ⊆ VD and ∀i ∈ [0, k], ∀u ∈ W [i], round(ϕ(u)) = round(v) + i. ▶ Definition 3 (Pattern). A pattern P = (W, Φ) is a tuple with some witnesses W and a predicate Φ of additional constraints on embeddings ϕ such that fresh variables are vertices

P. Kuznetsov, M. Perion, and S. Tucci-Piergiovanni

before or at the round of r in D1 . P is enabled for a vertex v in a DAG D if there exists an embedding ϕ of W on v in D such that Φ is satisfied; and disabled otherwise. ▶ Definition 4 (Commit Rule). Given a pattern P , a commit rule cr is a function that takes a DAG D ∈ D as input and returns a sequence of vertices cr(D) that are committed in D, such that: a leader vertex l is committed if and only if the pattern P is enabled for l in D; cr(D) is ordered by the leader sequence leaders; if a non-leader vertex v is in cr(D), then there is a leader vertex l in cr(D) such that v ⇝ l; Additionally, a commit rule can satisfy the following properties: Safe-Commit: for any DAG such that D ⊆ D′ ∈ D, cr(D) is a prefix of cr(D′ ), i.e., if P is enabled for a leader vertex l in D, then for all leader l′ < l in leaders, if P is enabled for l′ in D then it is also enabled for l′ in D′ , and if P is disabled for l′ in D then it is also disabled for l′ in D′ . Live-Commit: in every execution of the given model, for every vertex v issued by a correct process i, i will eventually have a DAG D such that v ∈ cr(D) (with probability 1 for the asynchronous model), i.e., v will be in the past or be a leader vertex for which the pattern is enabled. A commit rule is called safe if it satisfies Safe-Commit, and live if it satisfies Live-Commit. We show next that any safe and live commit rule can be used to solve atomic broadcast, and that any atomic broadcast protocol can be transformed into a safe and live commit rule. For instance, we can interpret the commit rule of Black Marlin [1] as some witnesses WBM on v such that: 1. W [0] is a single vertex v; 2. W [1] is a set of 2f + 1 vertices with a distinguished vertex u; 3. W [2] is another set of 2f + 1 vertices. Additionnally, the predicate ΦBM requires that the image of u in the embedding is the next leader after v in the leader sequence, i.e., ϕ(v) < ϕ(u) in leaders ∧ ̸ ∃v ′ : ϕ(v) < v ′ < ϕ(u) in leaders, that all vertices of W [1] have an edge to v, and that all vertices of W [2] have an edge to u.

3.2

Equivalence with Atomic Broadcast

Atomic Broadcast In the atomic broadcast problem [6, 5], processes may broadcast a message m by invoking a-broadcast(m), and the protocol outputs messages through a-deliver(m) events such that: Agreement: If a message m is a-delivered by some correct process, then m is eventually a-delivered by every correct process. Total-order: Let m and m′ be two messages such that i and j are correct processes that a-deliver m and m′ . If i a-delivers m before m′ , then j also a-delivers m before m′ . Validity: If a correct process a-broadcasts a message m, then every correct process eventually a-delivers m. Integrity: For any message m, every correct process a-delivers m at most once.

1

We intentionnaly restrict the scope of the predicate in order to prevent defining the whole commit rule with a predicate and to explicitly define the scope of the commit rule in the DAG, through the witnesses.

5

6

Minimizing Commit Rules for DAG-based Atomic Broadcast

In the asynchronous case, we refer to a probabilistic version of Byzantine Atomic Broadcast, where Agreement and Validity hold only with probability 1 [4]. We show using Algorithm 1 that any safe and live commit rule, on top of a communication component, can be transformed to solve atomic broadcast. Messages to a-broadcast are collected in a buffer and issued as part of the vertex of the next round, and messages are a-deliver when they belong to a vertex satisfying the commit rule. Algorithm 1 Atomic broadcast from a commit rule cr 1: procedure a-broadcast(m) 2:

to-issue := to-issue ∪ {m}

3: upon round r is completed do

a-deliver({m : m ∈ v, v ∈ cr(D)}) such that m is not yet a-delivered (messages part of a same vertex are a-delivered in the same order at all processes) 5: add the messages of to-issue to the vertex of round r + 1 and to-issue := ∅ 4:

▶ Theorem 5. Any (safe and live) commit rule on top of a communication component achieves atomic broadcast. Proof. Let cr be any safe and live commit rule on top of a communication component. We show that Algorithm 1 satisfies the properties of atomic broadcast: Agreement: Let i be a correct process that delivered a message m and let j be another correct process. Because m was delivered by i, m was part of some vertex v. Let Di be the local DAG of i such that v ∈ cr(Di ). Because of the communication component, v will eventually be in the DAG of j, and similarly for every vertex in Di , so eventually j will have a DAG Dj such that Di ⊆ Dj . By Safe-Commit, cr(Di ) is a prefix of cr(Dj ), so v ∈ cr(Dj ) and m is also delivered at j. Total-order: Let m and m′ be two messages delivered by two correct proccess i and j. Because they are delivered, m and m′ are part of some vertices v and v ′ respectively (if v = v ′ then m and m′ are delivered in the same order by Algorithm 1). Let Di be a DAG of i such that v, v ′ ∈ cr(Di ) and let Dj be a DAG of j such that v, v ′ ∈ cr(Dj ). Then, let D = Di ∪ Dj . By Safe-Commit v, v ′ ∈ cr(D), and both cr(Di ) and cr(Dj ) are prefixes of cr(D). Thus, cr(Di ) is a prefix of cr(Dj ) or vice versa, which implies that the messages of v and v ′ are delivered in the same order at i and j. Validity: Let m be a message broadcast by a correct process i. By Algorithm 1, m is part of some vertex v issued by i. Live-Commit implies that there is a DAG D′ such that D ⊆ D′ and v ∈ cr(D′ ), which means that i delivers m. By Agreement, every correct process will eventually deliver m. Integrity: Every message is delivered at least once by Algorithm 1. ◀ Conversely, we show that any atomic broadcast protocol P can define a safe and live commit rule. The commit rule is defined in Algorithm 2: when a process a-delivers a vertex v, it adds v to its local DAG and adds it to the output of the commit rule; when a process a-delivers n − f vertices for round r, it issues a vertex for round r + 1 with edges to the collected vertices in the DAG. ▶ Theorem 6. Any safe and live commit rule cr can be implemented by a protocol for atomic broadcast.

P. Kuznetsov, M. Perion, and S. Tucci-Piergiovanni

Algorithm 2 Commit rule from an atomic broadcast protocol P 1: upon P a-delivers a vertex v do

add v to the local DAG, respecting its causal dependencies (ignore v if one of its edges is missing) 3: cr(D) := cr(D).v 4: upon P a-delivers n − f vertices for round r do add a vertex v for round r + 1 with edges to n − f vertices of round r in the local DAG 5: 6: a-broadcast v 2:

Proof. Let P be an atomic broadcast protocol. We show that Algorithm 2 satisfies the properties of a safe and live commit rule. Let us note that if a correct process a-broadcast a vertex v, then every correct process that a-delivers v will have a-delivered v’s causal dependencies before due to total order of P . Since there is at least n − f correct processes, correct processes will keep a-broadcasting vertices for each round, and thus the block DAG will keep growing with valid vertices. We have: Safe-Commit: Due to total order of P , vertices of cr(D) are a-delivered in the same order at all processes, and thus cr(D) is always a prefix of cr(D′ ). Live-Commit: Let v be a vertex issued by a correct process in a DAG D. Since correct processes a-broadcast their vertices, and P satisfies validity and agreement, there is a DAG D′ such that D ⊆ D′ and v is a-delivered by P . Vertices that are a-delivered are outputted by cr. ◀ Theorem 5 implies that designing and proving a new protocol for atomic broadcast can be reduced to designing a new commit rule satisfying Safe-Commit and Live-Commit; and Theorem 6 implies that the sub-rule relation (defined next) can be used to compare directly atomic broadcast protocols through the commit rules they define.

4

Minimizing Commit Rules

4.1

The Sub-rule Relation

We now introduce a relation between commit rules that allows us to compare them and determine a minimal commit rule. Intuitively, the set of vertices committed by a commit rule cr1 is always a subset of the set of vertices committed by a commit rule cr2 . To be more formal, we compare the respective conditions on the DAG that cr1 and cr2 impose to commit vertices, through the notion of patterns and embeddings defined in Section 3. Assuming a communication component such as described in Section 2, the sub-rule relation ⪯ imposes a partial order on commit rules: ▶ Definition 7 (Sub-rule). Let P1 = (W1 , Φ1 ) and P2 = (W2 , Φ2 ) be two patterns, and let cr1 and cr2 be two safe and live commit rules defined by P1 and P2 , respectively. cr1 is a sub-rule of cr2 , denoted cr1 ⪯ cr2 , if and only if there exists an embedding ϕ of W1 on W2 and there exist a leader sequence such that when Φ2 is satisfied by ϕ(W2 ) on D then Φ1 is satisfied by ϕ(W1 ) on D. We want to show that cr1 being a sub-rule of cr2 means that for any DAG D ∈ D, cr1 commits as many or more vertices than cr2 , i.e., the set of vertices committed by cr1 , denoted set(cr1 (D)), is a superset of the set of vertices committed by cr2 .

7

8

Minimizing Commit Rules for DAG-based Atomic Broadcast

▶ Theorem 8 (Sub-rule commitment). Let cr1 and cr2 be two safe and live commit rules. Then, there exists a leader sequence such that cr1 ⪯ cr2 ⇐⇒ ∀D ∈ D, set(cr1 (D)) ⊇ set(cr2 (D)). Proof. Let cr1 and cr2 be two safe and live commit rules such that cr1 ⪯ cr2 . Let D ∈ D be a DAG and let v be a vertex such that v ∈ cr2 (D). Then, by definition of a commit rule, there exists a pattern P2 = (W2 , Φ2 ) such that P2 is enabled for v in D, i.e., there exists an embedding ϕ of W2 on v in D and Φ2 is satisfied by ϕ(W2 ) on D. By definition of a sub-rule, there exists an embedding ϕ of W1 on W2 and for every embedding ϕ of W2 such that Φ2 is satisfied by ϕ(W2 ) on D then Φ1 is satisfied by ϕ(W1 ) on D. Thus, P1 is also enabled for v in D, and by definition of a commit rule, v ∈ cr1 (D). On the other hand, let cr1 and cr2 be two safe and live commit rules such that ∀D ∈ D, set(cr1 (D)) ⊇ set(cr2 (D)). Let P1 = (W1 , Φ1 ) and P2 = (W2 , Φ2 ) be the patterns defining cr1 and cr2 , respectively. For any DAG D ∈ D, and any vertex v ∈ set(cr2 (D)), we have v ∈ set(cr1 (D)). Thus, P1 is enabled for v in D whenever P2 is enabled for any v in any D, and in particular when D = W2 , so W1 is a sub-DAG of W2 (up to renaming some vertices) and can be embedded on W2 . Additionally, if P2 is enabled for v in any D, then P1 is also enabled for v in any D, which implies that Φ1 is satisfied whenever Φ2 is satisfied. Thus, it also implies that cr1 ⪯ cr2 . ◀ Note that the sub-rule relation compares the conditions on the DAG to commit vertices, but the occurrence of these conditions during concrete executions depends on the network assumptions. In particular, a commit rule cr1 may be a sub-rule of a commit rule cr2 but cr1 may not be live under the same network assumptions as cr2 . On the other hand, comparing commit rules designed for the same network assumptions captures the fact that cr1 commits more vertices than cr2 or that cr1 commits the same vertices with a lower latency than cr2 , while still satisfying Safe-Commit. From our interpretation of such protocols, a simple example of a sub-rule relation is the asynchronous variant of Cordial Miners [7] and Mahi-Mahi [5]: the commit rule of the asynchronous variant of Cordial Miners has witnesses of depth 5 where 2f + 1 vertices point to the leader vertex, and each of these vertices is pointed by 2f + 1 vertices, while the commit rule of Mahi-Mahi can have witnesses of depth 4 (with the proper parameter), and similarly, requires that 2f + 1 vertices point to the leader vertex, and each of these vertices is pointed by 2f + 1 vertices. Thus, the witnesses of Mahi-Mahi can be embedded on the witnesses of the asynchronous variant of Cordial Miners because it requires one less round in the witnesses. Mahi-Mahi uses a sub-rule of the asynchronous variant of Cordial Miners, and in practice, Mahi-Mahi may commit vertices faster because it saves one round of latency (through the witnesses).

4.2

Minimal Commit Rule for Eventual Synchrony

We now propose a function crs∗ , which we show to be a safe and live commit rule in eventual synchrony. Intuitively, crs∗ commits a leader vertex v if it is pointed by a quorum of vertices in the next round, and if all the leaders that are concurrent to it and ordered before it in leaders are also decided (committed or skipped). We then show that crs∗ is minimal because any rule that relaxes either of these two conditions is not safe or not live. Figure 1 illustrates the commit rule crs∗ . ▶ Definition 9 (Minimal Commit Rule for Eventual Synchrony). We define the commit rule crs∗ for any DAG D via its pattern Ps∗ = (Ws∗ , Φ∗s ). The witnesses Ws∗ for a leader vertex l are such that Ws∗ [0] = l and Ws∗ [1] is a set Q of 2f + 1 vertices issued by distinct processes. Then, Φ∗s is a predicate that is satisfied when the following two conditions are satisfied:

P. Kuznetsov, M. Perion, and S. Tucci-Piergiovanni

r v0

ℓ1

v1

ℓ2

v2

ℓ3

v3

ℓ4 propose

r+1

≥ 2f +1 edges to ℓ1

vote

Figure 1 Minnow Commit rule: a leader vertex of round r is committed if it is pointed by 2f + 1 vertices in round r + 1, and if all the leaders that are concurrent to it and ordered before it in leaders are also decided (committed or skipped). Here, assuming ℓ1 < ℓ2 < ℓ3 < ℓ4 in the leader sequence, only ℓ1 is committed. Indeed, ℓ2 and ℓ3 are not committed due to not being referenced by 2f + 1 vertices. ℓ3 could have been committed if ℓ2 was committed (for instance by adding an edge from v3 at round r + 1), but here we cannot know if ℓ2 is committed between ℓ1 and ℓ3 in the view of some process, so it is not safe to commit ℓ3 yet.

Quorum: l is pointed to by all vertices in Q. Non-conflicting leaders: when for each slot s′ that precedes the slot of ϕ(l) in leaders, there is a vertex v ′ in slot s′ in D such that v ′ ⇝ ϕ(l) in D, or if ϕ(l) and v ′ are concurrent: Committed: v ′ ∈ crs∗ (D)2 ; Skip: or there are 2f + 1 vertices that do not have an edge to v ′ in round r + 1; All non-leader vertices that are in the causal past of a leader vertex l for which Ps∗ is satisfied are also committed, and crs∗ (D) is sorted by any deterministic order extending leaders and ⇝. ▶ Lemma 10 (crs∗ is safe). The commit rule crs∗ is safe. Proof (Sketch). First, let us note that if Ps∗ (v, D) = true for a vertex v in a DAG D, then there is no other vertex v ′ in any DAG D′ that is in the same slot as v and such that Ps∗ (v ′ , D′ ) = true. This is because correct processes issue vertices which points to at most one vertex per slot. Now, assume by contradiction that D ⊆ D′ but crs∗ (D) is not a prefix of crs∗ (D′ ). Since D ⊆ D′ and crs∗ does not remove committed vertices (the sets dc and ic can only grow) then {crs∗ (D)} ⊆ {crs∗ (D′ )}. So if crs∗ (D) = v0 . . . vz then there is a vertex vk ∈ crs∗ (D′ ) such that crs∗ (D′ ) = v0 . . . vk . . . vz . . . and vk ̸∈ crs∗ (D). Without loss of generality, vk is a committed leader in D′ (the set ic grow if and only if dc grows) and then vk is in the past of 2f + 1 processes in D′ . Since vz is also in the past of 2f + 1 processes in D then vk must also be in D (by the causality of the correct process in common). Since vk < vz in crs∗ (D′ ) then vk ⇝ vz or they are concurrent and vk < vz by leaders. This is a contradiction because if vk ⇝ vz in D then vk is also committed by indirect commit in crs∗ (D), or if they are concurrent then vk < vz by leaders and vz is not committed in crs∗ (D) because Ps∗ (vk , D) = false. ◀ 2

As required by the definition, v ′ ∈ crs∗ (D) can be written recursively as a predicate using only fresh variables in the past of l, but we write it this way for clarity.

9

10

Minimizing Commit Rules for DAG-based Atomic Broadcast

▶ Lemma 11 (crs∗ is live). The commit rule crs∗ is live, assuming an eventually synchronous network. Proof (Sketch). Any vertex v issued by a correct process will eventually be in the past of a leader vertex l issued by a correct process (the adversary can only delay messages for a finite amount of time between correct processes), and thus v will be indirectly committed if l is committed: it is sufficient to prove that such a leader vertex l will eventually be committed. After GST, all vertices issued by correct processes will satisfy the quorum condition of Ps∗ , and thus the only reason for a leader vertex l to not be committed is that the non-conflicting leaders condition is not satisfied, meaning that there is a concurrent leader vertex l′ such that l′ < l in leaders and l′ is not committed nor skipped. Applying the quorum argument recursively (vertices issued by correct processes cannot be skipped after GST), this implies that there is a leader vertex l′′ is issued by a faulty process such that l′′ < l in leaders. We argue that l′′ is eventually decided (committed or skipped) because either all correct processes will issue a vertex that does not point to l′ (and thus l′ is “skipped” by the second condition of P ∗ ) or there will be a vertex issued by a correct process in the causal future of l′ that satisfies P ∗ (we can show that there is a round such that all faulty leaders will either be skipped or included in the causal past of the “first” correct leader of the round, but we leave the details to a later version). ◀ ▶ Lemma 12 (crs∗ is minimal). There is no safe commit rule cr ̸= crs∗ such that cr ⪯ crs∗ and cr is live in an eventually synchronous network. Proof. Assume by contradiction that there is a commit rule cr with pattern P = (W, Φ) such that there is an embedding ϕ of W on W ∗ that is strictly injective. This implies that there is less than 2f + 1 vertices pointing to a leader vertex v in W . Then, a faulty leader can have issued a different vertex v ′ in the same slot as v and v ′ is also committed by cr for another process, which violates Safe-Commit. Thus, we can assume that there is a bijection ψ between W and W ∗ and there exists an embedding ϕ of W ∗ such that Φ is satisfied by ϕ(ψ(W ∗ )) but Φ∗ is not satisfied by ϕ(W ). If Φ∗ is not satisfied by ϕ(W ), then it is because either: Committed: there is a concurrent leader vertex v2 such that v2 < v1 in leaders and v2 ̸∈ crs∗ (D), then we can have another DAG D′ such that v1 ∈ crs∗ (D) and v1 ̸∈ crs∗ (D′ ); and v2 ∈ crs∗ (D′ ) but v2 ̸∈ crs∗ (D). Let D = D ∪ D′ : v1 , v2 must be in crs∗ (D) by Safe-Commit. If v1 < v2 in crs∗ (D) then crs∗ (D′ ) is not a prefix of crs∗ (D); and if v2 < v1 in crs∗ (D) then crs∗ (D) is not a prefix of crs∗ (D). Skip: there are no 2f + 1 vertices pointing to v1 in D, then cr is not live. ◀ ▶ Theorem 13 (Minimality of crs∗ in Eventual Synchrony). crs∗ is a minimal commit rule for eventual synchrony. Proof. crs∗ is a commit rule by Lemma 10 and 11; and is minimal by Lemma 12.

4.3

◀

Minimal Commit Rule for Asynchrony

We now propose a function cra∗ , which we show to be a safe and live commit rule in asynchrony. Intuitively, cra∗ is similar to crs∗ but adapted for asynchrony: it commits a leader vertex v if it can be reached by a quorum of paths in the next two rounds, and if all the leaders that are concurrent to it and ordered before it in leaders are also decided (committed or skipped). We leave the proofs for a later version, but the intuition is similar to the proofs for crs∗ .

P. Kuznetsov, M. Perion, and S. Tucci-Piergiovanni

▶ Definition 14 (Minimal Commit Rule for Asynchrony). We define the commit rule cra∗ for any DAG D via its pattern Pa∗ = (Wa∗ , Φ∗a ). The witnesses Wa∗ for a leader vertex l are such that Wa∗ [0] = l and Wa∗ [1] and Wa∗ [2] are sets of 2f + 1 vertices issued by distinct processes. Then, Φ∗a is a predicate that is satisfied when the following two conditions are satisfied: Quorum: there is 2f + 1 paths to l starting from a vertex issued by a distinct process (in Wa∗ [1] or in Wa∗ [2]). Non-conflicting leaders: when for each slot s′ that precedes the slot of ϕ(l) in leaders, there is a vertex v ′ in slot s′ in D such that v ′ ⇝ ϕ(l) in D, or if ϕ(l) and v ′ are concurrent: Committed: v ′ ∈ cra∗ (D)3 ; Skip: or there are 2f + 1 vertices that do not have an edge to v ′ in round ϕ(Wa∗ [2]). All non-leader vertices that are in the causal past of a leader vertex l for which Pa∗ is satisfied are also committed, and cra∗ (D) is sorted by any deterministic order extending leaders and ⇝.

5

Minnow Protocol

Protocol We instantiate the minimal commit rules into a concrete protocol, called Minnow, for atomic broadcast under eventual synchrony (S-Minnow) and asynchrony (A-Minnow). In both variants, l leaders can be committed in each round, where l is a parameter of the protocol. Intuitively, not all vertices of a round can satisfy the commit condition, and a large l may lead to head-of-line blocking, delaying the commitment of future leaders [5]. In eventual synchrony, S-Minnow instantiates the leaders function with a deterministic, pre-defined, sequence, e.g., round-robin, of l leaders each round. Leaders are committed following the crs∗ commit rule, and the correctness of S-Minnow follows from the correctness of crs∗ under the eventual synchrony assumption. Algorithm 3 S-Minnow 1: upon a valid vertex v is received do 2: 3: 4:

while one of v’s edges is missing then buffer v until all its edges are received add v to the local DAG

5: upon n − f vertices for round r are received and a timer expires do

▷ round r is completed 6: apply crs∗ to the local DAG and a-deliver all new committed vertices issue a vertex v for round r + 1 with edges to all vertices of round r in the local DAG 7: A-Minnow instantiates the leaders function with a random sequence of l leaders each round, computed from a common coin that requires 2f + 1 shares4 to be revealed, e.g., using

As required by the definition, v ′ ∈ cra∗ (D) can be written recursively as a predicate using only fresh variables in the past of l, but we write it this way for clarity. 4 Minnow would still be safe and live if leaders were revealed using only f + 1 shares, but we consider a threshold of 2f + 1 shares because, regardless of the expected number of shares, completing a round requires waiting for 2f + 1 vertices in the previous round. In particular, the attack described in [10] cannot be applied because the commit rule considers the whole DAG, not only the last 3 rounds that were completed. Thus, the DAG that allowed a correct process to commit a vertex will eventually be delivered to all other correct processes, which will then commit. 3

11

12

Minimizing Commit Rules for DAG-based Atomic Broadcast

a secure threshold signature scheme whose shares are sent within the vertices. For A-Minnow, leaders are committed following the cra∗ commit rule, and the leaders of round r are revealed in round r + 3. This additional round allows to ensure liveness because there is a positive probability that the adversary fails to guess the leaders of round r from information in round r + 2 and thus cannot always prevent the conditions of cra∗ to appear for some leader vertex in round r. We leave the detailled proofs for a later version of this paper. Algorithm 4 A-Minnow 1: upon a valid vertex v is received do 2: 3: 4:

while one of v’s edges is missing then buffer v until all its edges are received add v to the local DAG

5: upon n − f vertices for round r are received do

▷ round r is completed reveal the leaders of round r − 3 using the common coin shares in the vertices of round r−1 7: apply cra∗ to the local DAG and a-deliver all new committed vertices 8: issue a vertex v for round r + 1 with edges to all vertices of round r in the local DAG, with the shares of the common coin for round r − 2 6:

Comparison with existing protocols At first sight, S-Minnow may appear similar to Black Marlin [1], since both use a condition based on 2f + 1 incoming edges to commit vertices. However, the two protocols use this condition differently. Let LR denote the leader vertex of round r (or the first leader of round r in Minnow). In Black Marlin, LR is committed only if the leader vertex LR+1 of round r + 1 points to LR , and LR+1 is itself pointed to by 2f + 1 vertices in round r + 2. By contrast, in Minnow, committing LR does not require any condition involving round r + 2. If LR+1 points to LR , then LR can be committed; if LR+1 does not point to LR , then it is LR+1 , rather than LR , that cannot be committed. Therefore, whenever Black Marlin commits LR , the condition required by Minnow to commit LR is already satisfied, while Black Marlin imposes an additional condition on LR+1 in round r + 2. In this sense, Minnow’s commit rule requires no more DAG information than the condition used by Black Marlin for committing the same leader. Moreover, Minnow considers multiple leaders per round, whereas Black Marlin considers a single leader per round. For A-Minnow, the closest existing rule is the one used by Mahi-Mahi [5]. Unlike Black Marlin, which uses the next leader as an intermediate step, Mahi-Mahi directly requires a vertex in round r to be pointed to by 2f + 1 vertices in round r + 1 in order to be committed. However, as in Black Marlin, it imposes an additional condition involving round r + 2: these 2f + 1 vertices must all be pointed to by 2f + 1 vertices in round r + 2. A-Minnow relaxes Mahi-Mahi’s conditions to only 2f + 1 paths from distinct processes, which may not require 2f + 1 vertices in round r + 2 to point to each vertex in round r + 1. Therefore, whenever Mahi-Mahi commits a vertex, the condition required by A-Minnow to commit the same vertex is already satisfied. In this sense, A-Minnow requires no more DAG information than Mahi-Mahi for committing the same vertex.

P. Kuznetsov, M. Perion, and S. Tucci-Piergiovanni

6

Discussion

The sub-rule relation on any DAG-based protocol Currently, we applied the sub-rule relation only to DAG-based protocols using the same uncertified, round-based communication component. We claim that it is possible to transform the commit rule of any DAG-based protocol, irrespectively to the original communication component, to be applicable on an arbitrary DAG that represent the distributed traces (happened-before) of all messages issued by this protocol. This would allow us to compare any DAG-based protocols using the sub-rule relation on arbitrary DAGs, but the transformation of the commit rule is error prone and requires a careful analysis of the original protocol. we focused on protocols using uncertified DAGs because they have a lower amortized latency than protocols using byzantine reliable broadcast, and we claim that uncertified commit rules are sub-rule of certified commit rules, when transformed to be applicable on the same DAGs.

7

Conclusion

We defined commit rules, the class of functions that allows for solving atomic broadcast, on top of an uncertified, round-based DAG communication component. We introduced the sub-rule relation between commit rules, that allows to compare them and that we used to determine minimal commit rules for eventual synchrony and asynchrony. We leverage each minimal commit rule into a new protocol called Minnow, which we instantiated for eventual synchrony and asynchrony. Some open questions remain, such as the implementation and evaluation of Minnow in practice. This approach could also be applied to variation of atomic broadcast, such as ones requiring fairness properties on the total order [3, 8]. The sub-rule relation may also be used to compare any protocol for atomic broadcast, including non DAG-based ones, but it would require transforming the protocol and its commit rule to the uncertified, round-based DAG communication component, which seems less straightforward. References 1

2

3

4

Ignacio Amores-Sesar, Viktor Grøndal, Adam Holmgård, and Mads Ottendal. DAG It Off: Latency Prefers No Common Coins. In Dariusz R. Kowalski, editor, 39th International Symposium on Distributed Computing (DISC 2025), volume 356 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:17, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/ 10.4230/LIPIcs.DISC.2025.5, doi:10.4230/LIPIcs.DISC.2025.5. Kushal Babel, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris KokorisKogias, Arun Koshy, Alberto Sonnino, and Mingwei Tian. Mysticeti: Reaching the latency limits with uncertified dags. In 32nd Annual Network and Distributed System Security Symposium, NDSS 2025, San Diego, California, USA, February 24-28, 2025. The Internet Society, 2025. URL: https://www.ndss-symposium.org/ndss-paper/ mysticeti-reaching-the-latency-limits-with-uncertified-dags/. Christian Cachin, Jovana Mićić, Nathalie Steinhauer, and Luca Zanolini. Quick order fairness. In Financial Cryptography and Data Security: 26th International Conference, FC 2022, Grenada, May 2–6, 2022, Revised Selected Papers, page 316–333, Berlin, Heidelberg, 2022. Springer-Verlag. doi:10.1007/978-3-031-18283-9_15. Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374–382, April 1985. doi:10.1145/3149. 214121.

13

14

Minimizing Commit Rules for DAG-based Atomic Broadcast

5

6

7

8 9 10

11

Philipp Jovanovic, Lefteris Kokoris-Kogias, Bryan Kumara, Alberto Sonnino, Pasindu Tennage, and Igor Zablotchi. Mahi-mahi: Low-latency asynchronous BFT dag-based consensus. In 45th IEEE International Conference on Distributed Computing Systems, ICDCS 2025, Glasgow, United Kingdom, July 21-23, 2025, pages 549–559. IEEE, 2025. doi:10.1109/ICDCS63083. 2025.00060. Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman. All you need is dag. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC’21, page 165–175, New York, NY, USA, 2021. Association for Computing Machinery. doi:10.1145/3465084.3467905. Idit Keidar, Oded Naor, Ouri Poupko, and Ehud Shapiro. Cordial Miners: Fast and Efficient Consensus for Every Eventuality. In Rotem Oshman, editor, 37th International Symposium on Distributed Computing (DISC 2023), volume 281 of Leibniz International Proceedings in Informatics (LIPIcs), pages 26:1–26:22, Dagstuhl, Germany, 2023. Schloss Dagstuhl – LeibnizZentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/ LIPIcs.DISC.2023.26, doi:10.4230/LIPIcs.DISC.2023.26. Petr Kuznetsov, Maxence Perion, and Sara Tucci-Piergiovanni. Wait-free replicated data types and fair reconciliation, 2025. URL: https://arxiv.org/abs/2508.18193, arXiv:2508.18193. Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382–401, July 1982. doi:10.1145/357172.357176. Victor Shoup. Blue fish, red fish, live fish, dead fish. In 2025 IEEE International Conference on Blockchain and Cryptocurrency, ICBC 2025, Pisa, Italy, June 2-6, 2025, pages 1–7. IEEE, 2025. doi:10.1109/ICBC64466.2025.11114699. Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias. Bullshark: DAG BFT Protocols Made Practical. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS ’22, page 2705–2718, New York, NY, USA, 2022. Association for Computing Machinery. doi:10.1145/3548606.3559361.

Related documents

• NotDec: WebAssembly Decompilation With Inter-Procedural Type Recovery#429456
• AppEval: A Unified Benchmark for LLM-Based Mobile Application Repair in ArkTS, Swift, and Kotlin#467192
• The Ogg Encapsulation Format Version 0#193158
• JITterFlip: Uncovering Fault Attack Surfaces in JIT-Compiled LLM Serving#622463
• HiCRAB: Provably Safe Deployment of Adaptive Security#107761