Serviço de Líder em Sistemas Dinâmicos com Memória Compartilhada
Resumo
Apesar da importância que ambientes dinâmicos como as SANs (redes de área de armazenamento) e as arquiteturas multi-núcleo ocupam no cenário atual dos sistemas distribuídos, poucas são as propostas de modelos e protocolos para a implementação de eleição de líder após um tempo nesses contextos. Essa abstração é fundamental para a implementação dos requisitos de consistência e tolerância a falhas desses sistemas. Entretanto, a maioria das abordagens de eleição de líder considera sistemas estáticos, onde os processos se comunicam por troca de mensagens, satisfazendo requisitos temporais. Este artigo apresenta um serviço de eleição de líder, da classe Ω, para um sistema dinâmico assíncrono, sujeito a falhas por parada, em que os processos se comunicam através de registradores atômicos compartilhados e segundo um padrão de acesso à memória, livre de requisitos temporais.
Referências
Aguilera, M., Delporte-Gallet, C., Fauconnier, H., and Toueg, S. (2004). Communication-efficient leader election and consensus with limited link synchrony. In Proceedings of the Twenty-third Annual ACM Symposium on Principles of Distributed Computing, PODC ’04, pages 328–337, New York, NY, USA. ACM.
Aguilera, M. K. (2004). A pleasant stroll through the land of infinitely many creatures. SIGACT News, 35(2):36–59.
Aguilera, M. K., Delporte-Gallet, C., Fauconnier, H., and Toueg, S. (2001). Stable leader election. In Welch, J., editor, Distributed Computing, volume 2180 of Lecture Notes in Computer Science, pages 108–122. Springer Berlin Heidelberg.
Aguilera, M. K., Englert, B., and Gafni, E. (2003). On using network attached disks as shared memory. In Proceedings of the twenty-second annual symposium on Principles of distributed computing, PODC ’03, pages 315–324, New York, NY, USA. ACM.
Arantes, L., Greve, F., Sens, P., and Simon, V. (2013). Eventual leader election in envolving mobile networks. In Proceedings of the 17th International Conference on Principles of Distributed Systems, OPODIS ’13, Berlin, Heidelberg. Springer-Verlag.
Baldoni, R., Bonomi, S., Kermarrec, A.-M., and Raynal, M. (2009). Implementing a register in a dynamic distributed system. In Distributed Computing Systems, 2009. ICDCS ’09. 29th IEEE International Conference on, pages 639–647.
Chandra, T. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225–267.
Chandra, T. D., Hadzilacos, V., and Toueg, S. (1996). The weakest failure detector for solving consensus. Journal of the ACM, 43(4):685–722.
Fernández, A., Jiménez, E., and Raynal, M. (2006). Eventual leader election with weak assumptions on initial knowledge, communication reliability, and synchrony. In In DSN, pages 166–175.
Fernández, A., Jiménez, E., and Raynal, M. (2007). Electing an eventual leader in an asynchronous shared memory system. In Dependable Systems and Networks, 2007. DSN ’07. 37th Annual IEEE/IFIP International Conference on, pages 399–408.
Fernández, A., Jiménez, E., Raynal, M., and Trédan, G. (2010). A timing assumption and two t-resilient protocols for implementing an eventual leader service in asynchronous shared memory systems. Algorithmica, 56(4):550–576.
Fischer, M. J., Lynch, N. A., and Paterson, M. D. (1985). Impossibility of distributed consensus with one faulty process. Journal of ACM, 32(2):374–382.
Gafni, E. and Lamport, L. (2003). Disk paxos. Distrib. Comput., 16(1):1–20.
Guerraoui, R. and Raynal, M. (2003). The information structure of indulgent consensus. IEEE Transactions on Computers, 53:2004.
Guerraoui, R. and Raynal, M. (2006). A leader election protocol for eventually synchronous shared memory systems. In Software Technologies for Future Embedded and Ubiquitous Systems, 2006 and the 2006 Second International Workshop on Collaborative Computing, Integration, and Assurance. SEUS 2006/WCCIA 2006. The Fourth IEEE Workshop on, pages 6 pp.–.
Guerraoui, R. and Raynal, M. (2007). The alpha of indulgent consensus. Comput. J., 50(1):53–67.
Herlihy, M. P. and Wing, J. M. (1990). Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463–492.
Hutle, M., Malkhi, D., Schmid, U., and Zhou, L. (2009). Chasing the weakest system model for implementing ω and consensus. IEEE Transactions on Dependable and Secure Computing, 6(4):269–281.
Jiménez, E., Arévalo, S., and Fernández, A. (2006). Implementing unreliable failure detectors with unknown membership. Information Processing Letters, 100(2):60 – 63.
Malkhi, D., Oprea, F., and Zhou, L. (2005). ω meets paxos: Leader election and stability without eventual timely links. In Proceedings of the 19th International Conference on Distributed Computing, DISC’05, pages 199–213, Berlin, Heidelberg. Springer-Verlag.
Mostefaoui, A., Mourgaya, E., and Raynal, M. (2003). M.: Asynchronous implementation of failure detectors. In In: Proc. International IEEE Conference on Dependable Systems and Networks (DSN’03, pages 351–360.
Mostefaoui, A., Mourgaya, E., Raynal, M., and Travers, C. (2006). A time-free assumption to implement eventual leadership. Parallel Processing Letters, 16(02):189–207.
Aguilera, M. K. (2004). A pleasant stroll through the land of infinitely many creatures. SIGACT News, 35(2):36–59.
Aguilera, M. K., Delporte-Gallet, C., Fauconnier, H., and Toueg, S. (2001). Stable leader election. In Welch, J., editor, Distributed Computing, volume 2180 of Lecture Notes in Computer Science, pages 108–122. Springer Berlin Heidelberg.
Aguilera, M. K., Englert, B., and Gafni, E. (2003). On using network attached disks as shared memory. In Proceedings of the twenty-second annual symposium on Principles of distributed computing, PODC ’03, pages 315–324, New York, NY, USA. ACM.
Arantes, L., Greve, F., Sens, P., and Simon, V. (2013). Eventual leader election in envolving mobile networks. In Proceedings of the 17th International Conference on Principles of Distributed Systems, OPODIS ’13, Berlin, Heidelberg. Springer-Verlag.
Baldoni, R., Bonomi, S., Kermarrec, A.-M., and Raynal, M. (2009). Implementing a register in a dynamic distributed system. In Distributed Computing Systems, 2009. ICDCS ’09. 29th IEEE International Conference on, pages 639–647.
Chandra, T. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225–267.
Chandra, T. D., Hadzilacos, V., and Toueg, S. (1996). The weakest failure detector for solving consensus. Journal of the ACM, 43(4):685–722.
Fernández, A., Jiménez, E., and Raynal, M. (2006). Eventual leader election with weak assumptions on initial knowledge, communication reliability, and synchrony. In In DSN, pages 166–175.
Fernández, A., Jiménez, E., and Raynal, M. (2007). Electing an eventual leader in an asynchronous shared memory system. In Dependable Systems and Networks, 2007. DSN ’07. 37th Annual IEEE/IFIP International Conference on, pages 399–408.
Fernández, A., Jiménez, E., Raynal, M., and Trédan, G. (2010). A timing assumption and two t-resilient protocols for implementing an eventual leader service in asynchronous shared memory systems. Algorithmica, 56(4):550–576.
Fischer, M. J., Lynch, N. A., and Paterson, M. D. (1985). Impossibility of distributed consensus with one faulty process. Journal of ACM, 32(2):374–382.
Gafni, E. and Lamport, L. (2003). Disk paxos. Distrib. Comput., 16(1):1–20.
Guerraoui, R. and Raynal, M. (2003). The information structure of indulgent consensus. IEEE Transactions on Computers, 53:2004.
Guerraoui, R. and Raynal, M. (2006). A leader election protocol for eventually synchronous shared memory systems. In Software Technologies for Future Embedded and Ubiquitous Systems, 2006 and the 2006 Second International Workshop on Collaborative Computing, Integration, and Assurance. SEUS 2006/WCCIA 2006. The Fourth IEEE Workshop on, pages 6 pp.–.
Guerraoui, R. and Raynal, M. (2007). The alpha of indulgent consensus. Comput. J., 50(1):53–67.
Herlihy, M. P. and Wing, J. M. (1990). Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463–492.
Hutle, M., Malkhi, D., Schmid, U., and Zhou, L. (2009). Chasing the weakest system model for implementing ω and consensus. IEEE Transactions on Dependable and Secure Computing, 6(4):269–281.
Jiménez, E., Arévalo, S., and Fernández, A. (2006). Implementing unreliable failure detectors with unknown membership. Information Processing Letters, 100(2):60 – 63.
Malkhi, D., Oprea, F., and Zhou, L. (2005). ω meets paxos: Leader election and stability without eventual timely links. In Proceedings of the 19th International Conference on Distributed Computing, DISC’05, pages 199–213, Berlin, Heidelberg. Springer-Verlag.
Mostefaoui, A., Mourgaya, E., and Raynal, M. (2003). M.: Asynchronous implementation of failure detectors. In In: Proc. International IEEE Conference on Dependable Systems and Networks (DSN’03, pages 351–360.
Mostefaoui, A., Mourgaya, E., Raynal, M., and Travers, C. (2006). A time-free assumption to implement eventual leadership. Parallel Processing Letters, 16(02):189–207.
Publicado
05/05/2014
Como Citar
KHOURI, Cátia; GREVE, Fabíola.
Serviço de Líder em Sistemas Dinâmicos com Memória Compartilhada. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 15. , 2014, Florianópolis/SC.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2014
.
p. 116-129.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2014.22951.
