Algoritmo de Consenso Genérico em Memória Compartilhada
Resumo
O consenso é um problema fundamental para o desenvolvimento de sistemas distribuídos confiáveis. Porém, em ambientes assíncronos sujeitos a falhas, é preciso estender o sistema com algum mecanismo que forneça o sincronismo mínimo necessário para contornar a impossibilidade do consenso. Neste artigo, apresentamos um algoritmo de consenso genérico para um sistema assíncrono com memória compartilhada que pode ser instanciado com um detector de falhas ◊S ou Ω. O algoritmo é ótimo quanto ao número de registradores que utiliza e tolera (n − 1) falhas. Essa solução para memória compartilhada favorece o uso do consenso em aplicações modernas desenvolvidas, por exemplo, sobre arquiteturas multicore e Storage Area Networks (SAN).
Referências
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.
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.
Delporte-Gallet, C. and Fauconnier, H. (2009). Two consensus algorithms with atomic registers and failure detector omega. In Proceedings of the 10th International Conference on Distributed Computing and Networking, ICDCN ’09, pages 251–262, Berlin, Heidelberg. Springer-Verlag.
Delporte-Gallet, C., Fauconnier, H., Guerraoui, R., Hadzilacos, V., Kouznetsov, P., and Toueg, S. (2004). The weakest failure detectors to solve certain fundamental problems in distributed computing. In Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, PODC ’04, pages 338–346, New York, NY, USA. ACM.
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.
Guerraoui, R. and Raynal, M. (2003). The information structure of indulgent consensus. IEEE Transactions on Computers, 53:2004.
Guerraoui, R. and Raynal, M. (2007). The alpha of indulgent consensus. Comput. J., 50(1):53–67.
Khouri, C., Greve, F., and Tixeuil, S. (2012). Consenso com participantes desconhecidos em memoria compartilhada. 30o SBRC, Porto Alegre, RS, Brasil. SBC.
Lamport, L. (1986). On interprocess communication. Distributed Computing, 1(2):77–101.
Lo, W.-K. and Hadzilacos, V. (1994). Using failure detectors to solve consensus in asynchronous shared-memory systems (extended abstract). In Proceedings of the 8th International Workshop on Distributed Algorithms, WDAG ’94, pages 280–295, London, UK. Springer-Verlag.
Loui, M. C. and Abu-Amara, H. H. (1987). Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing Research, 4:163–183.
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.
Delporte-Gallet, C. and Fauconnier, H. (2009). Two consensus algorithms with atomic registers and failure detector omega. In Proceedings of the 10th International Conference on Distributed Computing and Networking, ICDCN ’09, pages 251–262, Berlin, Heidelberg. Springer-Verlag.
Delporte-Gallet, C., Fauconnier, H., Guerraoui, R., Hadzilacos, V., Kouznetsov, P., and Toueg, S. (2004). The weakest failure detectors to solve certain fundamental problems in distributed computing. In Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, PODC ’04, pages 338–346, New York, NY, USA. ACM.
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.
Guerraoui, R. and Raynal, M. (2003). The information structure of indulgent consensus. IEEE Transactions on Computers, 53:2004.
Guerraoui, R. and Raynal, M. (2007). The alpha of indulgent consensus. Comput. J., 50(1):53–67.
Khouri, C., Greve, F., and Tixeuil, S. (2012). Consenso com participantes desconhecidos em memoria compartilhada. 30o SBRC, Porto Alegre, RS, Brasil. SBC.
Lamport, L. (1986). On interprocess communication. Distributed Computing, 1(2):77–101.
Lo, W.-K. and Hadzilacos, V. (1994). Using failure detectors to solve consensus in asynchronous shared-memory systems (extended abstract). In Proceedings of the 8th International Workshop on Distributed Algorithms, WDAG ’94, pages 280–295, London, UK. Springer-Verlag.
Loui, M. C. and Abu-Amara, H. H. (1987). Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing Research, 4:163–183.
Publicado
06/05/2013
Como Citar
KHOURI, Cátia; GREVE, Fabíola.
Algoritmo de Consenso Genérico em Memória Compartilhada. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 14. , 2013, Brasília/DF.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2013
.
p. 47-60.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2013.23015.
