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

Resumo

Este trabalho apresenta um algoritmo hierárquico de difusão atômica sem-líder com acordo no destino, i.e. a ordem de entrega das mensagens é definida pelos processos destinatários. O algoritmo é totalmente descentralizado e todos os processos transmitem suas mensagens concorrentemente. Os processos utilizam árvores de difusão construídas através da rede de sobreposição VCube que, após a ocorrência de falhas, se reconfigura autonomicamente. Processos podem falhar por parada. As árvores são utilizadas para propagar os números de sequência (timestamps) locais das mensagens. Cada processo, após receber os timestamps de todos os demais, decide pela ordem de entrega das mensagens. Resultados de simulação mostram a maior eficiência da solução proposta em termos tanto do número de mensagens quanto da latência de difusão quando comparada com uma abordagem tradicional todos-para-todos.

Referências

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.