Um Serviço de Multicast Confiável Hierárquico com o Vcube

• Luiz A. Rodrigues UNIOESTE
• Elias P. Duarte Jr. UFPR
• Luciana Arantes Sorbonne Universités / UPMC Université

DOI: https://doi.org/10.5753/wtf.2015.22939

Resumo

Multicast é um serviço fundamental de comunicação em grupo para o desenvolvimento de soluções distribuídas, tais como replicação de dados ou exclusão mútua, pois permite o envio simultâneo de mensagens a um grupo de processos. Este trabalho apresenta uma solução para a difusão seletiva confiável de mensagens (reliable multicast) hierárquico com base na topologia virtual mantida pelo VCube. A topologia é construída e adaptada dinamicamente com base nas informações de falhas obtidas de um sistema subjacente de monitoramento, formando um hipercubo completo quando não há falhas. As mensagens são propagadas por uma árvore geradora criada dinamicamente sobre os enlaces mantidos pelo VCube. Os processos podem falhar por crash e uma falha é permanente. O VCube se auto-reconfigura após cada falha, tolerando até n−1 processos falhos. Resultados experimentais confirmam a eficiência do algoritmo proposto quando comparado com outras soluções da literatura.

Referências

Bista, B. (2005). A fault-tolerant scheme for multicast communication protocols. In: 11th Asia-Pacific Conference on Communications, APCC’05, pp. 289–293.

Bolton, C. e Lowe, G. (2004). Analyses of the reverse path forwarding routing algorithm. In: Int’l Conf. on Dependable Systems and Networks, DSN’04, pp. 485–494.

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

Duarte, Jr., E. P., Bona, L. C. E. e Ruoso, V. K. (2014). VCube: A provably scalable distributed diagnosis algorithm. In: 5th Work. on Latest Advances in Scalable Algorithms for Large-Scale Systems, ScalA’14, pp. 17–22, Piscataway, USA. IEEE Press.

Freiling, F. C., Guerraoui, R. e Kuznetsov, P. (2011). The failure detector abstraction. ACM Computing Surveys, 43:9:1–9:40.

Hadzilacos, V. e Toueg, S. (1993). Fault-tolerant broadcasts and related problems. In: Distributed systems, pp. 97–145. ACM Press, New York, NY, USA, 2 ed.

Irwin, R. e Basu, P. (2013). Reliable multicast clouds. In: IEEE Military Communications Conference, MILCOM’13, pp. 1087–1092.

Khazan, R., Fekete, A. e Lynch, N. (1998). Multicast group communication as a base for a load-balancing replicated data service. In: Kutten, S., editor, Distributed Computing, v. 1499 de LNCS, pp. 258–272. Springer Berlin Heidelberg.

Kshemkalyani, A. D. e Singhal, M. (2008). Message ordering and group communication, In: Distributed Computing: Principles, Algorithms, and Systems. Cambridge University Press, New York, NY, USA, 1 ed.

Lau, P. (2006). A fault-tolerant best-effort multicast algorithm. In: IEEE Int’l Conf. on Communication Technology, ICCT’06, pp. 1–4.

Popescu, A., Constantinescu, D., Erman, D. e Ilie, D. (2007). A survey of reliable multicast communication. In: 3rd Conference on Next Generation Internet Networks, EuroNGI’07, pp. 111–118.

Rahimi, M. e Sarsar, N. (2008). Load balanced multicast with multi-tree groups. In: 14th Asia-Pacific Conference on Communications, APCC’08, pp. 1–5.

Rodrigues, L. A., Duarte Jr., E. P. e Arantes, L. (2014a). Árvores geradoras mínimas distribuídas e autonômicas. In: XXXII Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos, SBRC’14.

Rodrigues, L. A., Duarte Jr., E. P. e Arantes, L. (2014b). Uma solução autonômica para a criação de quóruns majoritários baseada no VCube. In: Anais do XV Workshop de Testes e Tolerância a Falhas, WTF’14, pp. 74–87.

Ruoso, V. K. (2013). Uma estratégia de testes logarítmica para o algoritmo Hi-ADSD. Dissertação de Mestrado, Universidade Federal do Paraná.

Schiper, A. e Sandoz, A. (1993). Uniform reliable multicast in a virtually synchronous environment. In: 13th Int’l Conf. on Distrib. Comput. Syst., ICDCS’93, pp. 561–568.

Sutra, P. e Shapiro, M. (2008). Fault-tolerant partial replication in large-scale database systemsIn: Luque, E., Margalef, T. e Benítez, D., editores, Euro-Par, v. 5168 de LNCS, pp. 404–413. Springer Berlin Heidelberg.

Urbán, P., Défago, X. e Schiper, A. (2002). Neko: A single environment to simulate and prototype distributed algorithms. Journal of Inf. Science and Eng., 18(6):981–997.