Abaixo o Líder: Um Algoritmo Hierárquico Sem-Líder para Difusão Atômica

• Lucas V. Ruchel Unioeste
• Edson T. de Camargo Unioeste
• Rogério Turchetti Unioeste
• Elias P. Duarte Jr. Unioeste
• Luciana Arantes Unioeste
• Luiz A. Rodrigues Unioeste

DOI: https://doi.org/10.5753/sbrc.2021.16708

Abstract

This work presents a hierarchical leaderless atomic broadcast algorithm with destination agreement. The algorithm is completely decentralized and all processes can send messages concurrently. The processes use spanning trees built on the VCube overlay network which reconfigures itself autonomically after the occurrence of failures. Processes fail by crashing. Trees are used to propagate local sequence numbers (timestamps) of the messages. Each process, after receiving timestamps from all the others, decides on the order in which messages are delivered. Simulation results show the advantage of the proposed solution in terms of both the number of messages and the broadcast latency when compared to a traditional all-for-all approach.

References

Birman, K. P. and Joseph, T. A. (1987). Reliable communication in the presence of failures. ACM Trans. Comput. Syst., 5(1):47–76.

Chandra, T. D. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. J. ACM, 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, E. P., Rodrigues, L. A., and Sens, P. (2019). Vcube-ps: A causal broadcast topic-based publish/subscribe system. J. Parallel Distributed Comput., 125:18–30.

Défago, X., Schiper, A., and Urbán, P. (2004). Total order broadcast and multicast algorithms: Taxonomy and survey. ACM Comput. Surv., 36(4):372–421.

Delporte-Gallet, C. and Fauconnier, C. D. I. (1999). Real-time fault-tolerant atomic broadcast. In Proceedings of the 18th IEEE Symposium on Reliable Distributed Systems, pages 48–55.

Duarte, E. P., Bona, L. C. E., and Ruoso, V. K. (2014). Vcube: A provably scalable distributed diagnosis algorithm. In 2014 5th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems, pages 17–22.

Ekwall, R., Schiper, A., and Urban, P. (2004). Token-based atomic broadcast using unreliable failure detectors. In Proceedings of the 23rd IEEE International Symposium on Reliable Distributed Systems, 2004.

Hao, W., Zeng, J., Dai, X., Xiao, J., Hua, Q., Chen, H., Li, K., and Jin, H. (2020). Towards a trust-enhanced blockchain p2p topology for enabling fast and reliable broadcast. IEEE Transactions on Network and Service Management, 17(2):904–917.

Jeanneau, D., Rodrigues, L. A., Arantes, L., and Jr., E. P. D. (2017). An autonomic hierarchical reliable broadcast protocol for asynchronous distributed systems with failure detection. J. Braz. Comput. Soc., 23(1):15:1–15:14.

Kozhaya, D., Decouchant, J., and Esteves-Verissimo, P. (2019). Rt-byzcast: Byzantine-resilient real-time reliable broadcast. IEEE Transactions on Computers, 68(3):440–454.

Kshemkalyani, A. D. and Singhal, M. (2008). Distributed Computing: Principles, Algorithms, and Systems. Cambridge University Press, USA, 1 edition.

Lamport, L. (1998). The part-time parliament. ACM Trans. Comput. Syst., 16(2):133–169.

Luan, S. . and Gligor, V. D. (1990). A fault-tolerant protocol for atomic broadcast. IEEE Transactions on Parallel and Distributed Systems, 1(3):271–285.

Milosevic, Z., Hutle, M., and Schiper, A. (2011). On the reduction of atomic broadcast to consensus with byzantine faults. In 2011 IEEE 30th International Symposium on Reliable Distributed Systems, pages 235–244.

Paznikov, A. A., Gurin, A. V., and Kupriyanov, M. S. (2020). Implementation in actor model of leaderless decentralized atomic broadcast. In 2020 9th Mediterranean Conference on Embedded Computing (MECO).

Pedone, F., Guerraoui, R., and Schiper, A. (1998). Exploiting atomic broadcast in replicated databases. In Pritchard, D. and Reeve, J., editors, Euro-Par’98 Parallel Processing, pages 513–520, Berlin, Heidelberg. Springer Berlin Heidelberg.

Poke, M., Hoeer, T., and Glass, C. W. (2017). Allconcur: Leaderless concurrent atomic broadcast. HPDC ’17, page 205–218, New York, NY, USA. Association for Computing Machinery.

Rodrigues, L. A., Arantes, L., and Jr., E. P. D. (2014a). An autonomic implementation of reliable broadcast based on dynamic spanning trees. In EDCC, pages 1–12. IEEE Computer Society.

Rodrigues, L. A., Duarte Jr, E. P., and Arantes, L. (2014b). Árvores geradoras mínimas distribuídas e autonômicas. In SBRC, pages 1–14.

Runo, J., Verissimo, P., Arroz, G., Almeida, C., and Rodrigues, L. (1998). Fault-tolerant broadcasts in can. In Annual International Symp. on Fault Tolerant Computing FTCS.

Saramago, R. Q., Alchieri, E. A. P., Rezende, T. F., and Camargos, L. (2017). Algoritmo de difusão atômica rápido a despeito de colisões tolerante a falhas bizantinas. In SBRC, Porto Alegre, RS, Brasil. SBC.

Schneider, F. B. (1990). Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Comput. Surv., 22(4):299–319.

Srivastava, P., Chakrabarti, P., and Panwar, A. (2014). Article: Rigorous design of moving sequencer atomic broadcast with malicious sequencer. International Journal of Computer Applications, 105(7):13–18.

Terra, A., Camargo, E., and Duarte, E. P. (2020). A caminho de uma alternativa hierárquica para implementação do algoritmo de consenso paxos. In Anais do XXI W. de Testes e Tolerância a Falhas, pages 15–28, Porto Alegre, RS, Brasil. SBC.

Thanisch, P. (2000). Atomic commit in concurrent computing. IEEE Concurrency, 8(4):34–41.

Urban, P., Defago, X., and Schiper, A. (2001). Neko: a single environment to simulate and prototype distributed algorithms. In Proceedings 15th International Conference on Information Networking, pages 503–511.