Eleição de Líder com Qualidade de Serviço para o Modelo Falha-e-Recuperação

• Vinícius Reis UFSCar
• Gustavo Vieira UFSCar

DOI: https://doi.org/10.5753/sbrc_estendido.2018.14176

Resumo

Um dos objetivos de um sistema distribuído é prover poder computacional e persistência de dados mesmo na presença de falhas de um subconjunto de enlaces e processos. Para determinar quais são os processos defeituosos deste sistema e abstrair o conceito de tempo, estes sistemas utilizam os serviços de um detector de falhas não confiável, encapsulado em um algoritmo de eleição de líder. Embora a literatura sobre a qualidade de serviço (QoS) oferecida por detectores de falhas seja abundante, ela é escassa quando se trata da QoS oferecida por algoritmos de eleição de líder. Nesta dissertação propomos um algoritmo de eleição de líder para o modelo falha-e-recuperação denominado NFD-L, que segue as especificações de QoS originalmente apresentadas em [Chen et al. 2002]. Utilizamos NFD-L em uma aplicação para replicação, como mecanismo de eleição de coordenador para Paxos e apresentamos uma análise da QoS observada, comparando o seu comportamento com um algoritmo de eleição de líder que não foi projetado explicitamente para prover garantias de QoS.

Referências

Chandra, T. D. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. J. ACM, 43(2):225–267.

Chen, W., Toueg, S., and Aguilera, M. (2002). On the quality of service of failure detectors. Computers, IEEE Transactions on, 51(5):561–580.

Fischer, M. J., Lynch, N. A., and Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374–382.

Garcia-Molina, H. (1982). Elections in a distributed computing system. IEEE Trans. Comput., 31(1):48–59.

Guerraoui, R. (2000). Indulgent algorithms (preliminary version). In Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, PODC ’00, pages 289–297, New York, NY, USA. ACM.

Lamport, L. (1998). The part-time parliament. ACM Trans. Comput. Syst., 16(2):133–169.

Ma, T., Hillston, J., and Anderson, S. (2010). On the quality of service of crash-recovery failure detectors. IEEE Trans. Dependable Secur. Comput., 7(3):271–283.

Nunes, R. C. and Jansch-Porto, I. (2004). QoS of timeout-based self-tuned failure detec tors: The effects of the communication delay predictor and the safety margin. In Proceedings of the 2004 International Conference on Dependable Systems and Networks, DSN ’04, pages 753–, Washington, DC, USA. IEEE Computer Society.

Reis, V. A. (2017). Eleição de líder com qualidade de serviço para o modelo falha-erecuperação. Master’s thesis, Universidade Federal de São Carlos, Sorocaba, Brasil.

Reis, V. A. and Vieira, G. M. D. (2017). Quality of service of an asynchronous crashrecovery leader election algorithm. In SBRC ’17: Proc. of the 35th Brazilian Symposium on Computer Networks and Distributed Systems, pages 1089–1102, Belém, Brazil.

Schiper, N. and Toueg, S. (2008). A robust and lightweight stable leader election service for dynamic systems. In Dependable Systems and Networks With FTCS and DCC, 2008. DSN 2008. IEEE International Conference on, pages 207–216. IEEE.

Sotoma, I. andMadeira, E. R.M. (2006). A markov model for providing quality of service for failure detectors under message loss bursts. Technical Report IC-06-013, Institute of Computing, University of Campinas.

Vieira, G. M. D. and Buzato, L. E. (2008). Treplica: Ubiquitous replication. In SBRC ’08: Proc. of the 26th Brazilian Symposium on Computer Networks and Distributed Systems, Rio de Janeiro, Brasil.