Serviço de Líder em Sistemas Dinâmicos com Memória Compartilhada

• Cátia Khouri UESB / UFBA
• Fabíola Greve UFBA

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

Abstract

In spite of the importance of dynamic distributed environments, such as SANs (storage area networks) and multicore architectures, we found very few proposals of models and protocols for implementing eventual leader election. This abstraction is fundamental to the implementation of consistency and fault-tolerance requirements. Most approaches for electing a leader consider static systems, where processes communicate by message passing, satisfying timing constraints. This paper presents a leader election service, of class Ω, for a dynamic asynchronous system subject to crash failures, where processes communicate through atomic shared registers following a memory access pattern, free of temporal requirements.

References

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.