Good-case Latency of Byzantine Broadcast
Authors:
Open Access
- 21 July 2021
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 331-341
Abstract
This paper explores the good-case latency of Byzantine fault-tolerant broadcast, motivated by the real-world latency and performance of practical state machine replication protocols. The good-case latency measures the time it takes for all non-faulty parties to commit when the designated broadcaster is non-faulty. We provide a complete characterization of tight bounds on good-case latency, in the authenticated setting under synchrony, partial synchrony and asynchrony. Some of our new results may be surprising, e.g., 2-round PBFT-style partially synchronous Byzantine broadcast is possible if and only if n ≥ 5ƒ-1, and a tight bound for good-case latency under n/3 < ƒ < n/2 under synchrony is not an integer multiple of the delay bound.Keywords
This publication has 21 references indexed in Scilit:
- Bosco: One-Step Byzantine Asynchronous Consensus2008
- Zyzzyva2007
- Fast Byzantine ConsensusIEEE Transactions on Dependable and Secure Computing, 2006
- On Expected Constant-Round Protocols for Byzantine Agreement2006
- Dynamic fault-tolerant clock synchronizationJournal of the ACM, 1995
- Early stopping in Byzantine agreementJournal of the ACM, 1990
- Consensus in the presence of partial synchronyJournal of the ACM, 1988
- Asynchronous Byzantine agreement protocolsInformation and Computation, 1987
- Authenticated Algorithms for Byzantine AgreementSIAM Journal on Computing, 1983
- A lower bound for the time to assure interactive consistencyInformation Processing Letters, 1982