World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

On the Versatility of Bracha’s Byzantine Reliable Broadcast Algorithm

    G. Bracha presented in 1987 a simple and efficient reliable broadcast algorithm for n-process asynchronous message-passing systems, which tolerates up to t<n/3 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 (t), 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 ts (for safety) and t 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. G. Bracha, Asynchronous Byzantine agreement protocols, Information and Computation 75(2) (1987) 130–143. Crossref, ISIGoogle Scholar
    • 2. G. Bracha and S. Toueg, Asynchronous consensus and broadcast protocols, Journal of the ACM, 32(4) (1985) 824–840. Crossref, ISIGoogle Scholar
    • 3. G. Guerraoui, J. Komatovic, P. Kuznetsov, P. A. Pignolet, D.-A. Seredinschi and A. Tonkikh, 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. G. Guerraoui, P. Kuznetsov, M. Monti, M. Pavlovic and D.-A. Seredinschi, 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. M. Hirt, A. Kastrato and C.-D. Liu-Zhang, 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. D. Imbs and M. Raynal, Trading t-resilience for efficiency in asynchronous Byzantine reliable broadcast, Parallel Processing Letters 26(4) (2016) 8 pages. Link, ISIGoogle Scholar
    • 8. L. Lamport, R. Shostack and M. Pease, The Byzantine generals problem, ACM Transactions on Programming Languages and Systems 4(3) (1982) 382–401. Crossref, ISIGoogle Scholar
    • 9. D. Malkhi, K. Nayak and L. Ren, Flexible Byzantine fault tolerance, Proc. ACM SIGSAC Conference on Computer and Communications Security (CCS’19) (ACM Press, 2019), pp. 1041–1053. CrossrefGoogle Scholar
    • 10. F. J. Meyer and D. K. Pradhan, Consensus with dual failure modes, IEEE Transactions on Parallel and Distributed Systems 2(2) (1991) 214–222. Crossref, ISIGoogle Scholar
    • 11. K. Nayak, L. Ren, E. Shi, N. H. Vaidya and Z. Xiang, 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. M. Pease, R. Shostak and L. Lamport, Reaching agreement in the presence of faults, Journal of the ACM 27 (1980) 228–234. Crossref, ISIGoogle Scholar
    • 13. M. Raynal, Fault-Tolerant Message-Passing Distributed Systems: An Algorithmic Approach (Springer, 2018), 480 pages, ISBN 978-3-319-94140-0. CrossrefGoogle Scholar