A Caminho do Broadcast Hierárquico Tolerante a Falhas Bizantinas
Resumo
O broadcast confiável tolerante a falhas bizantinas é um problema central em sistemas distribuídos, garantindo a entrega de mensagens mesmo havendo processos com comportamento arbitrário na rede. Este trabalho apresenta uma estratégia de difusão bizantina confiável baseada na topologia hierárquica do VCube, combinada com o uso de assinaturas digitais para assegurar integridade e autenticidade das mensagens. A decisão de entrega do algoritmo é baseada na validação das assinaturas acumuladas ao longo da difusão. O algoritmo proposto tolera até f = (n−1)/3 processos bizantinos e emprega árvores dinâmicas construídas sobre o VCube para garantir a propagação de mensagens no sistema.Referências
Albini, L. C. P., Duarte Jr, E. P., and Ziwich, R. P. (2005). A generalized model for distributed comparison-based system-level diagnosis. JPDC, 10(3):44–56.
Amoussou-Guenou, Y., Beltrando, L., Herlihy, M., and Potop-Butucaru, M. (2026). Byzantine reliable broadcast and tendermint consensus with trusted components. Theoretical Computer Science, page 115763.
Bona, L. C., Duarte Jr, E. P., Mello, S. L., and Fonseca, K. V. (2006). Hyperbone: Uma rede overlay baseada em hipercubo virtual sobre a internet. XXIV SBRC.
Bonomi, S., Farina, G., and Tixeuil, S. (2019). Multi-hop byzantine reliable broadcast with honest dealer made practical. JPDC, 25(1):9.
Bracha, G. (1987). Asynchronous byzantine agreement protocols. Information and computation, 75(2):130–143.
Cachin, C., Guerraoui, R., and Rodrigues, L. (2011). Introduction to reliable and secure distributed programming. Springer Science & Business Media.
Cachin, C., Kursawe, K., Petzold, F., and Shoup, V. (2001). Secure and efficient asynchronous broadcast protocols. In Annual International Cryptology Conference, pages 524–541. Springer.
Chandra, T. D. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM (JACM), 43(2):225–267.
Correia, M., Neves, N. F., and Veríssimo, P. (2006). From consensus to atomic broadcast: Time-free byzantine-resistant protocols without signatures. The Computer Journal, 49(1):82–96.
de Araujo, J. P., Arantes, L., Duarte Jr, E. P., Rodrigues, L. A., and Sens, P. (2019). Vcube-ps: A causal broadcast topic-based publish/subscribe system. Journal of Parallel and Distributed Computing, 125:18–30.
De Bona, L. C. E. and Duarte Jr, E. P. (2004). A flexible approach for defining distributed dependable tests in snmp-based network management systems. Journal of electronic testing, 20(4):447–454.
Dolev, D. (1981). Unanimity in an unknown and unreliable environment. In 22nd Annual Symposium on Foundations of Computer Science (sfcs 1981), pages 159–168. IEEE.
Dolev, D. and Strong, H. R. (1983). Authenticated algorithms for byzantine agreement. SIAM Journal on Computing, 12(4):656–666.
Duarte, E. P. and De Bona, L. E. (2002). A dependable snmp-based tool for distributed network management. In Proceedings International Conference on Dependable Systems and Networks, pages 279–284. IEEE.
Duarte Jr, E. P., Rodrigues, L. A., Camargo, E. T., and Turchetti, R. C. (2023). The missing piece: a distributed system-level diagnosis model for the implementation of unreliable failure detectors. Computing, 105(12):2821–2845.
Duarte Jr, E. P., Ziwich, R. P., and Albini, L. C. (2011). A survey of comparison-based system-level diagnosis. ACM Computing Surveys (CSUR), 43(3):1–56.
Freitas, A. E. S., Rodrigues, L. A., and Duarte Jr, E. P. (2024). vcubechain: A scalable permissioned blockchain. Ad Hoc Networks, 158:103461.
Jeanneau, É., Rodrigues, L. A., Arantes, L., and Duarte Jr, E. P. (2017). An autonomic hierarchical reliable broadcast protocol for asynchronous distributed systems with failure detection. Journal of the Brazilian Computer Society, 23(1):15.
Kozhaya, D., Decouchant, J., and Esteves-Verissimo, P. (2018). Rt-byzcast: Byzantine-resilient real-time reliable broadcast. IEEE Trans. Computers, 68(3):440–454.
Lamport, L., Shostak, R., and Pease, M. (1982). The byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382–401.
Locher, T. (2024). Byzantine reliable broadcast with low communication and time complexity. arXiv preprint arXiv:2404.08070.
Rodrigues, L. A., Arantes, L., and Duarte, E. P. (2014). An autonomic implementation of reliable broadcast based on dynamic spanning trees. In EDCC, pages 1–12.
Rodrigues, L. A., Arantes, L., and Duarte, E. P. (2016). An autonomic majority quorum system. In AINA, pages 524–531. IEEE.
Rodrigues, L. A., Duarte Jr, E. P., and Arantes, L. (2018). A distributed k-mutual exclusion algorithm based on autonomic spanning trees. Journal of Parallel and Distributed Computing, 115:41–55.
Rodrigues, L. A., Jeanneau, D., Jr., E. P. D., and Arantes, L. (2017). Uma solução de difusão confiável hierárquica em sistemas distribuídos assíncronos. In XXXV SBRC.
Rodrigues, L. A., Jr., E. P. D., and Arantes, L. (2025). Distributed and autonomic minimum spanning trees. CoRR, abs/2512.02683.
Ruchel, L. V., de Camargo, E. T., Rodrigues, L. A., Turchetti, R. C., Arantes, L., and Duarte Jr, E. P. (2024). Scalable atomic broadcast: A leaderless hierarchical algorithm. Journal of Parallel and Distributed Computing, 184:104789.
Stein, G., Rodrigues, L. A., Duarte Jr, E. P., and Arantes, L. (2023). Diamond-p-vcube: An eventually perfect hierarchical failure detector for asynchronous distributed systems. In 12th LADC, pages 40–49.
Turchetti, R. C., Duarte Jr, E. P., Arantes, L., and Sens, P. (2016). A QoS-configurable failure detection service for internet applications. JISA, 7(1):9.
Ziwich, R. P. and Duarte, E. P. (2016). A nearly optimal comparison-based diagnosis algorithm for systems of arbitrary topology. IEEE Transactions on Parallel and Distributed Systems, 27(11):3131–3143.
Amoussou-Guenou, Y., Beltrando, L., Herlihy, M., and Potop-Butucaru, M. (2026). Byzantine reliable broadcast and tendermint consensus with trusted components. Theoretical Computer Science, page 115763.
Bona, L. C., Duarte Jr, E. P., Mello, S. L., and Fonseca, K. V. (2006). Hyperbone: Uma rede overlay baseada em hipercubo virtual sobre a internet. XXIV SBRC.
Bonomi, S., Farina, G., and Tixeuil, S. (2019). Multi-hop byzantine reliable broadcast with honest dealer made practical. JPDC, 25(1):9.
Bracha, G. (1987). Asynchronous byzantine agreement protocols. Information and computation, 75(2):130–143.
Cachin, C., Guerraoui, R., and Rodrigues, L. (2011). Introduction to reliable and secure distributed programming. Springer Science & Business Media.
Cachin, C., Kursawe, K., Petzold, F., and Shoup, V. (2001). Secure and efficient asynchronous broadcast protocols. In Annual International Cryptology Conference, pages 524–541. Springer.
Chandra, T. D. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM (JACM), 43(2):225–267.
Correia, M., Neves, N. F., and Veríssimo, P. (2006). From consensus to atomic broadcast: Time-free byzantine-resistant protocols without signatures. The Computer Journal, 49(1):82–96.
de Araujo, J. P., Arantes, L., Duarte Jr, E. P., Rodrigues, L. A., and Sens, P. (2019). Vcube-ps: A causal broadcast topic-based publish/subscribe system. Journal of Parallel and Distributed Computing, 125:18–30.
De Bona, L. C. E. and Duarte Jr, E. P. (2004). A flexible approach for defining distributed dependable tests in snmp-based network management systems. Journal of electronic testing, 20(4):447–454.
Dolev, D. (1981). Unanimity in an unknown and unreliable environment. In 22nd Annual Symposium on Foundations of Computer Science (sfcs 1981), pages 159–168. IEEE.
Dolev, D. and Strong, H. R. (1983). Authenticated algorithms for byzantine agreement. SIAM Journal on Computing, 12(4):656–666.
Duarte, E. P. and De Bona, L. E. (2002). A dependable snmp-based tool for distributed network management. In Proceedings International Conference on Dependable Systems and Networks, pages 279–284. IEEE.
Duarte Jr, E. P., Rodrigues, L. A., Camargo, E. T., and Turchetti, R. C. (2023). The missing piece: a distributed system-level diagnosis model for the implementation of unreliable failure detectors. Computing, 105(12):2821–2845.
Duarte Jr, E. P., Ziwich, R. P., and Albini, L. C. (2011). A survey of comparison-based system-level diagnosis. ACM Computing Surveys (CSUR), 43(3):1–56.
Freitas, A. E. S., Rodrigues, L. A., and Duarte Jr, E. P. (2024). vcubechain: A scalable permissioned blockchain. Ad Hoc Networks, 158:103461.
Jeanneau, É., Rodrigues, L. A., Arantes, L., and Duarte Jr, E. P. (2017). An autonomic hierarchical reliable broadcast protocol for asynchronous distributed systems with failure detection. Journal of the Brazilian Computer Society, 23(1):15.
Kozhaya, D., Decouchant, J., and Esteves-Verissimo, P. (2018). Rt-byzcast: Byzantine-resilient real-time reliable broadcast. IEEE Trans. Computers, 68(3):440–454.
Lamport, L., Shostak, R., and Pease, M. (1982). The byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382–401.
Locher, T. (2024). Byzantine reliable broadcast with low communication and time complexity. arXiv preprint arXiv:2404.08070.
Rodrigues, L. A., Arantes, L., and Duarte, E. P. (2014). An autonomic implementation of reliable broadcast based on dynamic spanning trees. In EDCC, pages 1–12.
Rodrigues, L. A., Arantes, L., and Duarte, E. P. (2016). An autonomic majority quorum system. In AINA, pages 524–531. IEEE.
Rodrigues, L. A., Duarte Jr, E. P., and Arantes, L. (2018). A distributed k-mutual exclusion algorithm based on autonomic spanning trees. Journal of Parallel and Distributed Computing, 115:41–55.
Rodrigues, L. A., Jeanneau, D., Jr., E. P. D., and Arantes, L. (2017). Uma solução de difusão confiável hierárquica em sistemas distribuídos assíncronos. In XXXV SBRC.
Rodrigues, L. A., Jr., E. P. D., and Arantes, L. (2025). Distributed and autonomic minimum spanning trees. CoRR, abs/2512.02683.
Ruchel, L. V., de Camargo, E. T., Rodrigues, L. A., Turchetti, R. C., Arantes, L., and Duarte Jr, E. P. (2024). Scalable atomic broadcast: A leaderless hierarchical algorithm. Journal of Parallel and Distributed Computing, 184:104789.
Stein, G., Rodrigues, L. A., Duarte Jr, E. P., and Arantes, L. (2023). Diamond-p-vcube: An eventually perfect hierarchical failure detector for asynchronous distributed systems. In 12th LADC, pages 40–49.
Turchetti, R. C., Duarte Jr, E. P., Arantes, L., and Sens, P. (2016). A QoS-configurable failure detection service for internet applications. JISA, 7(1):9.
Ziwich, R. P. and Duarte, E. P. (2016). A nearly optimal comparison-based diagnosis algorithm for systems of arbitrary topology. IEEE Transactions on Parallel and Distributed Systems, 27(11):3131–3143.
Publicado
25/05/2026
Como Citar
STEIN, Gabriela; RODRIGUES, Luiz A.; DUARTE JR., Elias P..
A Caminho do Broadcast Hierárquico Tolerante a Falhas Bizantinas. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 27. , 2026, Praia do Forte/BA.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 1-12.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2026.24108.
