On the Versatility of Bracha’s Byzantine Reliable Broadcast Algorithm
Abstract
G. Bracha presented in 1987 a simple and efficient reliable broadcast algorithm for -process asynchronous message-passing systems, which tolerates up to Byzantine processes. Following an idea recently introduced by Hirt, Kastrato and Liu-Zhang (OPODIS 2020), instead of considering the upper bound on the number of Byzantine processes , the present short article considers two types of Byzantine behavior: the ones that can prevent the safety property from being satisfied, and the ones that can prevent the liveness property from being satisfied (a Byzantine process can exhibit only one or both types of failures). This Byzantine differentiated failure model is captured by two associated upper bounds denoted (for safety) and for liveness). The article shows that only the threshold values used in the predicates of Bracha’s algorithm must be modified to obtain an algorithm that works with this differentiated Byzantine failure model.
Communicated by Joffroy Beauquier
References
- 1. , Asynchronous Byzantine agreement protocols, Information and Computation 75(2) (1987) 130–143. Crossref, ISI, Google Scholar
- 2. , Asynchronous consensus and broadcast protocols, Journal of the ACM, 32(4) (1985) 824–840. Crossref, ISI, Google Scholar
- 3. , Dynamic Byzantine reliable broadcast, Proc. 24th Int’l Conference on Principles of Distributed Systems (OPODIS’20), LIPIcs Vol. 184, Article 23 (2020), 18 pages. Google Scholar
- 4. , Scalable Byzantine reliable broadcast Proc. 33rd Int’l Symposium on Distributed Computing (DISC’19), LIPIcs Vol. 146, Article 22 (2019), 16 pages. Google Scholar
- 5. V. Hadzilacos and S. Toueg, A modular approach to fault-tolerant broadcasts and related problems, Tech Report 94-1425, 83 pages, Cornell University, Ithaca (1994). Google Scholar
- 6. , Multi-threshold asynchronous reliable broadcast and consensus, Proc. 24th Int’l Conference on Principles of Distributed Systems (OPODIS’20), LIPICs Vol. 184, Article 6 (2020), 16 pages. Google Scholar
- 7. , Trading t-resilience for efficiency in asynchronous Byzantine reliable broadcast, Parallel Processing Letters 26(4) (2016) 8 pages. Link, ISI, Google Scholar
- 8. , The Byzantine generals problem, ACM Transactions on Programming Languages and Systems 4(3) (1982) 382–401. Crossref, ISI, Google Scholar
- 9. , Flexible Byzantine fault tolerance, Proc. ACM SIGSAC Conference on Computer and Communications Security (CCS’19) (ACM Press, 2019), pp. 1041–1053. Crossref, Google Scholar
- 10. , Consensus with dual failure modes, IEEE Transactions on Parallel and Distributed Systems 2(2) (1991) 214–222. Crossref, ISI, Google Scholar
- 11. , Improved extension protocols for Byzantine broadcast and agreement, Proc. 34rd Int’l Symposium on Distributed Computing (DISC’20), LIPIcs Vol. 179, Article 28 (2020), 16 pages. Google Scholar
- 12. , Reaching agreement in the presence of faults, Journal of the ACM 27 (1980) 228–234. Crossref, ISI, Google Scholar
- 13. , Fault-Tolerant Message-Passing Distributed Systems: An Algorithmic Approach (Springer, 2018), 480 pages, ISBN 978-3-319-94140-0. Crossref, Google Scholar


