2025 · 15 citations · 24 references
ComputingComputer EngineeringComputer ScienceDistributed SystemsFault-tolerant ComputingFault-tolerant SystemsConsensus ProtocolsDistributed ComputingDistributed ConsensusLatency OptimizationReliable Distributed SystemsScalable Algorithm DesignCommitCommit ProtocolsConsensus ScalabilityLatency MetricsLatency MinimizationLatency TradeoffsReliable BroadcastThroughput
Directed Acyclic Graph (DAG) based BFT protocols balance consensus efforts across different parties and maintain high throughput even when some designated parties fail. However, existing DAG-based BFT protocols exhibit long latency to commit decisions, primarily because they have a leader every 2 or more “rounds”. Recent works, such as Shoal (FC'23) and Mysticeti, have deemed supporting a leader vertex in each round particularly difficult, if not impossible. Consequently, even under honest leaders, these protocols require high latency (or communication complexity) to commit the proposal submitted by the leader (leader vertex) and additional latency to commit other proposals (non-leader vertices). In this work, we present Sailfish, the first DAG-based BFT that supports a leader vertex in each round. Under honest leaders, Sailfish maintains a commit latency of one reliable broadcast (RBC) round plus round plus <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$1\delta$</tex> to commit to commit the leader vertex (where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\delta$</tex> is the actual transmission latency of a message) and only an additional RBC round to commit non-leader vertices. We also extend Sailfish to Multi-leader Sailfish, which facilitates multiple leaders within a single round and commits all leader vertices in a round with a latency of one RBC round plus <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$1\delta$</tex>. Our experimental evaluation demonstrates that our protocols introduce significantly lower latency overhead compared to existing DAG-based protocols, with similar throughput.
24
Consensus in the presence of partial synchrony
Cynthia Dwork, Nancy Lynch, Larry Stockmeyer · Journal of the ACM · 1988 · 1.9K citations · Full text
Short Signatures from the Weil Pairing
Dan Boneh, Ben Lynn, Hovav Shacham · Journal of Cryptology · 2004 · 1.4K citations · Full text
Maofan Yin, Dahlia Malkhi, Michael K. Reiter et al. · 2019 · 944 citations · Full text
The Honey Badger of BFT Protocols
Andrew Miller, Yu Xia, Kyle Croman et al. · 2016 · 802 citations · Full text
Asynchronous Byzantine agreement protocols
Gabriel Bracha · Information and Computation · 1987 · 432 citations