Um algoritmo de Membership para o modelo Síncrono Particionado (SPA) de Sistemas Distribuídos com particionamento forte
Resumo
Serviços de comunicação em grupo são importantes blocos de construção para sistemas distribuídos tolerantes a falhas. Neste serviço, o membership faz a gestão da composição do grupo de comunicação considerando grupos dinâmicos com processos entrando e saindo. Têm sido apresentados algoritmos para solucionar o membership em sistemas distribuídos síncronos e parcialmente síncronos, tolerando falhas, tendo sido provada a impossibilidade do membership em sistemas assíncronos. Modelos de sistemas distribuídos híbridos, com componentes síncronos e assíncronos, têm sido estudados, sendo relevantes por representar sistemas atuais, tais como sistemas baseados em IoT, integrando, por exemplo, plantas industriais através da internet. Neste artigo apresentamos um algoritmo que resolve o problema de membership no modelo de sistemas distribuídos SPA (Síncrono Particionado). O algoritmo proposto permite a existência de diversos grupos com interseção entre eles. Além do algoritmo, apresentamos provas formais de suas propriedades e resultados de implementação em ambiente simulado.
Referências
Anceaume, E., Charron-Bost, B., Minet, P., and Toueg, S. (1995). On the Formal Specification of Group Membership Services. Research Report RR-2695, INRIA. Projet REFLECS.
Chandra, T. D., Hadzilacos, V., Toueg, S., and Charron-Bost, B. (1996). On the impossibility of group membership. In Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, pages 322–330.
Chandra, T. D. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM (JACM), 43(2):225–267.
Chockler, G. V., Keidar, I., and Vitenberg, R. (2001). Group communication specifications: a comprehensive study. ACM Computing Surveys (CSUR), 33(4):427–469.
Cristian, F. (1991). Reaching agreement on processor-group membrship in synchronous distributed systems. Distributed Computing, 4(4):175–187.
Cristian, F. and Fetzer, C. (1999). The timed asynchronous distributed system model. IEEE Transactions on Parallel and Distributed Systems, 10(6):642–657.
Ezhilchelvan, P. D., Macêdo, R. A., and Shrivastava, S. K. (1995). Newtop: a faulttolerant group communication protocol. In Proceedings of 15th International Conference on Distributed Computing Systems, pages 296–306. IEEE.
Fetzer, C. and Cristian, F. (1997). A failure aware membership service. In Proceedings of the 16th Symposium on Reliable Distributed Systems, page 157. IEEE.
Fischer, M. J., Lynch, N. A., and Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), 32(2):374–382.
Gorender, S., Macedo, R., and Raynal, M. (2005). A hybrid and adaptive model for fault-tolerant distributed computing. In 2005 International Conference on Dependable Systems and Networks (DSN’05), pages 412–421. IEEE.
Gorender, S. and Macêdo, R. J. d. A. (2011). Consenso distribuído eficiente no modelo síncrono particionado. In Anáis do XXIX Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos (SBRC), pages 587–600.
Gorender, S., Macedo, R. J. d. A., and Raynal, M. (2007). An adaptive programming model for fault-tolerant distributed computing. IEEE Transactions on Dependable and Secure Computing, 4(1):18–31.
Keidar, I., Sussman, J., Marzullo, K., and Dolev, D. (2002). Moshe: A group membership service for wans. ACM Transactions on Computer Systems, 20.
Lim, L. and Conan, D. (2014). Partitionable group membership for mobile ad hoc networks. Journal of Parallel and Distributed Computing, 74(8):2708–2721.
lin, k. and Hadzilacos, V. (1999). Asynchronous group membership with oracles. In Proceedings of the 13th International Symposium on Distributed Computing, pages 70–93.
Macêdo, R. J. d. A. and Freitas, A. E. S. (2009). A generic group communication approach for hybrid distributed systems. In IFIP International Conference on Distributed Applications and Interoperable Systems, pages 102–115. Springer.
Macêdo, R. J. d. A., Freitas, A. E. S., et al. (2011). A self-manageable group commuIn 2011 5th Latinnication protocol for partially synchronous distributed systems. American Symposium on Dependable Computing, pages 146–155. IEEE.
Macêdo, R. J. d. A. and Gorender, S. (2008). Detectores perfeitos em sistemas distribuídos não síncronos. In Anais do IX Workshop de Teste e Tolerância a Falhas (WTF 2008).
Macêdo, R. J. d. A. and Gorender, S. (2009). Perfect failure detection in the partitioned synchronous distributed system model. In 2009 International Conference on Availability, Reliability and Security, pages 273–280. IEEE.
Macêdo, R. J. d. A. and Gorender, S. (2012). Exploiting partitioned synchrony to implement accurate failure detectors. International Journal of Critical Computer-Based Systems 4, 3(3):168–186.
Park, S., Yoo, S., Kim, Y., Lee, S., and Kim, D. (2016). A message efficient group membership protocol in synchronous distributed systems. In Information Technology: New Generations, pages 1249–1254. Springer.
Schiper, A. (2006). Dynamic group communication. Distributed Computing, 18(5):359–374.
Schiper, A. and Toueg, S. (2006). From set membership to group membership: A separation of concerns. IEEE Transactions on Dependable and Secure Computing, 3(1):2–12.
Silva Freitas, A. E. and de Araújo Macêdo, R. J. (2014). A performance evaluation tool for hybrid and dynamic distributed systems. ACM SIGOPS Operating Systems Review, 48(1):11–18.
Veríssimo, P. and Casimiro, A. (2002). The timely computing base model and architecture. IEEE Transactions on Computers, 51(8):916–930.
Chandra, T. D., Hadzilacos, V., Toueg, S., and Charron-Bost, B. (1996). On the impossibility of group membership. In Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, pages 322–330.
Chandra, T. D. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM (JACM), 43(2):225–267.
Chockler, G. V., Keidar, I., and Vitenberg, R. (2001). Group communication specifications: a comprehensive study. ACM Computing Surveys (CSUR), 33(4):427–469.
Cristian, F. (1991). Reaching agreement on processor-group membrship in synchronous distributed systems. Distributed Computing, 4(4):175–187.
Cristian, F. and Fetzer, C. (1999). The timed asynchronous distributed system model. IEEE Transactions on Parallel and Distributed Systems, 10(6):642–657.
Ezhilchelvan, P. D., Macêdo, R. A., and Shrivastava, S. K. (1995). Newtop: a faulttolerant group communication protocol. In Proceedings of 15th International Conference on Distributed Computing Systems, pages 296–306. IEEE.
Fetzer, C. and Cristian, F. (1997). A failure aware membership service. In Proceedings of the 16th Symposium on Reliable Distributed Systems, page 157. IEEE.
Fischer, M. J., Lynch, N. A., and Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), 32(2):374–382.
Gorender, S., Macedo, R., and Raynal, M. (2005). A hybrid and adaptive model for fault-tolerant distributed computing. In 2005 International Conference on Dependable Systems and Networks (DSN’05), pages 412–421. IEEE.
Gorender, S. and Macêdo, R. J. d. A. (2011). Consenso distribuído eficiente no modelo síncrono particionado. In Anáis do XXIX Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos (SBRC), pages 587–600.
Gorender, S., Macedo, R. J. d. A., and Raynal, M. (2007). An adaptive programming model for fault-tolerant distributed computing. IEEE Transactions on Dependable and Secure Computing, 4(1):18–31.
Keidar, I., Sussman, J., Marzullo, K., and Dolev, D. (2002). Moshe: A group membership service for wans. ACM Transactions on Computer Systems, 20.
Lim, L. and Conan, D. (2014). Partitionable group membership for mobile ad hoc networks. Journal of Parallel and Distributed Computing, 74(8):2708–2721.
lin, k. and Hadzilacos, V. (1999). Asynchronous group membership with oracles. In Proceedings of the 13th International Symposium on Distributed Computing, pages 70–93.
Macêdo, R. J. d. A. and Freitas, A. E. S. (2009). A generic group communication approach for hybrid distributed systems. In IFIP International Conference on Distributed Applications and Interoperable Systems, pages 102–115. Springer.
Macêdo, R. J. d. A., Freitas, A. E. S., et al. (2011). A self-manageable group commuIn 2011 5th Latinnication protocol for partially synchronous distributed systems. American Symposium on Dependable Computing, pages 146–155. IEEE.
Macêdo, R. J. d. A. and Gorender, S. (2008). Detectores perfeitos em sistemas distribuídos não síncronos. In Anais do IX Workshop de Teste e Tolerância a Falhas (WTF 2008).
Macêdo, R. J. d. A. and Gorender, S. (2009). Perfect failure detection in the partitioned synchronous distributed system model. In 2009 International Conference on Availability, Reliability and Security, pages 273–280. IEEE.
Macêdo, R. J. d. A. and Gorender, S. (2012). Exploiting partitioned synchrony to implement accurate failure detectors. International Journal of Critical Computer-Based Systems 4, 3(3):168–186.
Park, S., Yoo, S., Kim, Y., Lee, S., and Kim, D. (2016). A message efficient group membership protocol in synchronous distributed systems. In Information Technology: New Generations, pages 1249–1254. Springer.
Schiper, A. (2006). Dynamic group communication. Distributed Computing, 18(5):359–374.
Schiper, A. and Toueg, S. (2006). From set membership to group membership: A separation of concerns. IEEE Transactions on Dependable and Secure Computing, 3(1):2–12.
Silva Freitas, A. E. and de Araújo Macêdo, R. J. (2014). A performance evaluation tool for hybrid and dynamic distributed systems. ACM SIGOPS Operating Systems Review, 48(1):11–18.
Veríssimo, P. and Casimiro, A. (2002). The timely computing base model and architecture. IEEE Transactions on Computers, 51(8):916–930.
Publicado
16/08/2021
Como Citar
SANTOS, Maria Clara Aderne dos; GORENDER, Sérgio.
Um algoritmo de Membership para o modelo Síncrono Particionado (SPA) de Sistemas Distribuídos com particionamento forte. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 22. , 2021, Uberlândia.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2021
.
p. 43-56.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2021.17203.
