Minimizing Commit Rules for DAG-based Atomic Broadcast
2026-08-18 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors study how to order messages in systems where some participants might behave badly, using special graph structures called DAGs. They focus on rules that decide when messages can be safely delivered, aiming to find the simplest such rules that still work correctly under different network conditions. They define a way to compare these rules and identify the minimal ones that require the least conditions to commit messages safely. Then, they introduce a new protocol called Minnow that uses these minimal rules for more efficient message delivery in both eventually synchronous and fully asynchronous networks.
Byzantine fault toleranceatomic broadcastdirected acyclic graphcommit rulecausal relationseventually synchronous modelasynchronous modelmessage orderingdistributed systemsprotocol design
Authors
Petr Kuznetsov, Maxence Perion, Sara Tucci-Piergiovanni
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 \emph{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 $cr_1$ is a sub-rule of a commit rule $cr_2$ if, for any DAG, the set of vertices committed by $cr_1$ contains all vertices committed by $cr_2$. 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 \emph{Minnow}, a new protocol for DAG-based atomic broadcast, which can be instantiated in both eventually synchronous (S-Minnow) and asynchronous networks (A-Minnow).