Um algoritmo de Membership para o modelo Síncrono Particionado (SPA) de Sistemas Distribuídos com particionamento forte.

• Maria Clara Aderne dos Santos UFBA
• Sérgio Gorender UFBA

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

Abstract

Group communication services are important building blocks for fault-tolerant distributed systems. In such a service, membership protocols manages the composition of the communication group considering dynamic groups with incoming and outgoing processes. Algorithms have been presented to solve membership in synchronous and partially synchronous distributed systems, tolerating failures, and the impossibility of membership in asynchronous systems has been proven. Hybrid distributed system models, with synchronous and asynchronous components, have been studied, being relevant for representing current systems, such as systems based on IoT, integrating, for example, industrial plants through the internet. In this paper we present an algorithm that solves the membership problem in the distributed systems model SPA (Synchronous Partitioned). The proposed algorithm allows the existence of several intersecting groups. In addition to the algorithm, we present formal proofs of its properties and implementation results in a simulated environment.

References

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.