Search papers, labs, and topics across Lattice.
This paper introduces a novel approach to minimizing commit rules in DAG-based atomic broadcast protocols, focusing on the efficiency of message delivery in both eventually synchronous and asynchronous models. By defining a sub-rule relation among commit rules, the authors identify minimal commit rules that impose the least conditions necessary for safely committing vertices in a DAG. The resulting protocol, Minnow, significantly reduces latency in message delivery compared to existing protocols, marking a substantial advancement in Byzantine fault tolerance.
Minnow achieves unprecedented efficiency in DAG-based atomic broadcast by minimizing commit rules, slashing message delivery latency in both synchronous and asynchronous environments.
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).
