SmartGossip: Difusão Probabilística Inteligente de Mensagens em Redes de Topologia Arbitrária

  • Wellington Souza UFPR
  • Aurora Pozo UFPR
  • Elias P. Duarte Jr. UFPR

Resumo


A difusão de mensagens é uma das abstrações mais poderosas de sistemas distribuídos, permitindo que uma mensagem seja transmitida de um para todos os processos do sistema, sendo necessária para a execução de diversos tipos de tarefas e aplicações. Esse trabalho apresenta o algoritmo SmartGossip, para a difusão probabilística e inteligente de mensagens em redes de topologia arbitrária, inspirada em uma estratégia de otimização baseada em colônias de formigas, mais especificamente pelo conceito de comunicação por estigmergia. O algoritmo SmartGossip é especificado e avaliado através de simulação no OMNeT++. Foram executados experimentos medindo o número de mensagens utilizadas e o número de rodadas necessárias para completar a difusão em redes de até 1024 processos com conectividades diversas. O SmartGossip é comparado com algoritmos baseados em inundação (Flooding) e em difusão probabilística (Gossip tradicional). Os resultados mostram que o número médio de mensagens utilizadas pelo SmartGossip é sempre menor que dos demais algoritmos, além de apresentarem baixa dispersão na medida em que o tamanho do sistema e conectividade variam.

Referências

Banzi, A. S., Jr., E. P. D., and Pozo, A. R. (2011). An approach based on swarm intelligence for event dissemination in dynamic networks. In IEEE SRDS, pages 121-126.

Cachin, C., Guerraoui, R., and Rodrigues, L. (2011). Introduction to Reliable and Secure Distributed Programming (2nd Ed). Springer.

De Campos Jr, A., Pozo, A. T., and Duarte Jr, E. P. (2013). Evaluation of asynchronous multi-swarm particle optimization on several topologies. Concurrency and Computation: Practice and Experience, 25(8):1057-1071.

De Campos Jr, A., Pozo, A. T., and Duarte Jr, E. P. (2019). Parallel multi-swarm pso strategies for solving many objective optimization problems. Journal of Parallel and Distributed Computing, 126:13-33.

Dorigo, M., Birattari, M., and Stutzle, T. (2006). Ant colony optimization. IEEE computational intelligence magazine, 1(4):28-39.

Dorigo, M., Bonabeau, E., and Theraulaz, G. (2000). Ant algorithms and stigmergy. Future Generation Computer Systems, 16(8):851-871.

Duarte Jr, E. and Mattos, G. (2000). Diagnóstico em redes de topologia arbitrária: Um algoritmo baseado em inundação de mensagens. In II Workshop de Testes e Tolerância a Falhas (WTF), pages 82-87. SBC.

Duarte Jr, E. P., Pozo, A. T., and Nassu, B. T. (2010). Fault diagnosis of multiprocessor systems based on genetic and estimation of distribution algorithms: a performance evaluation. International Journal on Artificial Intelligence Tools, 19(01):1-18.

Eugster, P., Guerraoui, R., Kermarrec, A.-M., and Massoulié, L. (2004). Epidemic information dissemination in distributed systems. IEEE Computer, 37:60-67.

Muteeh, A., Sardaraz, M., and Tahir, M. (2021). Mrlba: multi-resource load balancing algorithm for cloud computing using ant colony optimization. Cluster Computing, 24(4):3135-3145.

Nassu, B. T., Duarte Jr, E. P., and Ramirez Pozo, A. T. (2005). A comparison of evolutionary algorithms for system-level diagnosis. In Proceedings of the 7th annual conference on Genetic and evolutionary computation, pages 2053-2060.

Nassu, B. T., Nanya, T., and Duarte, E. P. (2007). Topology discovery in dynamic and decentralized networks with mobile agents and swarm intelligence. In Int. Conf. Intellinget Sys. Design and Apps. (ISDA), pages 685-690.

Ramamoorthy, R. and Thangavelu, M. (2021). An enhanced hybrid ant colony optimization routing protocol for vehicular ad-hoc networks. Journal of Ambient Intelligence and Humanized Computing, pages 1-32.

Rodrigues, L., Arantes, L., and Duarte, E. (2014). An autonomic implementation of reliable broadcast based on dynamic spanning trees. In EDCC, pages 1-12. IEEE.
Publicado
27/05/2022
SOUZA, Wellington; POZO, Aurora; DUARTE JR., Elias P.. SmartGossip: Difusão Probabilística Inteligente de Mensagens em Redes de Topologia Arbitrária. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 23. , 2022, Fortaleza. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 1-14. ISSN 2595-2684. DOI: https://doi.org/10.5753/wtf.2022.223006.