Uma Solução Autonômica para a Criação de Quóruns Majoritários Baseada no Vcube
Resumo
Este trabalho apresenta uma solução autonômica para a construção e manutenção de quóruns em sistemas distribuídos. Os processos são organizados em uma topologia virtual de hipercubo chamada VCube. A topologia é construída dinamicamente com base nas informações de falhas obtidas de um sistema de monitoramento. Processos falhos são eliminados do sistema e uma nova configuração é criada utilizando apenas os processos corretos. Os processos podem falhar por crash e uma falha é permanente. Os quóruns gerados possuem tamanho e carga bem distribuídos e a reconfiguração é automática, tolerando até n − 1 processos falhos. O sistema proposto foi comparado com uma solução em árvore binária. Resultados experimentais confirmam a resiliência e estabilidade dos quóruns no VCube.Referências
Abawajy, J. e Mat Deris, M. (2013). Data replication approach with data consistency guarantee for data grid. IEEE Trans. Comput., PP(99):1–1.
Abraham, I. e Malkhi, D. (2005). Probabilistic quorums for dynamic systems. Distrib. Comput., 18(2):113–124.
Agrawal, D. e El Abbadi, A. (1991). An efficient and fault-tolerant solution for distributed mutual exclusion. ACM Trans. Comput. Syst., 9(1):1–20.
Agrawal, D. e El Abbadi, A. (1992). The generalized tree quorum protocol: an efficient approach for managing replicated data. ACM Trans. Database Syst., 17(4):689–717.
Amir, Y. e Wool, A. (1996). Evaluating quorum systems over the internet. In FTCS, pages 26–, Washington, DC, USA. IEEE Computer Society.
Atreya, R., Mittal, N. e Peri, S. (2007). A quorum-based group mutual exclusion algorithm for a distributed system with dynamic group set. IEEE Trans. Parallel Distrib. Syst., 18(10):1345–1360.
Barbara, D. e Garcia-Molina, H. (1986). The vulnerability of vote assignments. ACM Trans. Comput. Syst., 4(3):187–213.
Barbara, D., Garcia-Molina, H. e Spauster, A. (1989). Increasing availability under mutual exclusion constraints with dynamic vote reassignment. ACM Trans. Comput. Syst., 7(4):394–426.
Choi, S. C. e Youn, H. Y. (2012). Dynamic hybrid replication effectively combining tree and grid topology. J. Supercomput., 59(3):1289–1311.
Freiling, F. C., Guerraoui, R. e Kuznetsov, P. (2011). The failure detector abstraction. ACM Comput. Surv., 43:9:1–9:40.
Fujita, S. (1998). A quorum based k-mutual exclusion by weighted k-quorum systems. Inf. Process. Lett., 67(4):191–197.
Garcia-Molina, H. e Barbara, D. (1985). How to assign votes in a distributed system. J. ACM, 32(4):841–860.
Gifford, D. K. (1979). Weighted voting for replicated data. In Proceedings of the Seventh ACM Symposium on Operating Systems Principles, SOSP ’79, pages 150–162, New York, NY, USA. ACM.
Guerraoui, R. e Vukolić, M. (2010). Refined quorum systems. Distributed Computing, 23(1):1–42.
Kumar, V. e Agarwal, A. (2011). Generalized grid quorum consensus for replica control protocol. In Computational Intelligence and Communication Networks (CICN), 2011 International Conference on, pages 395–400.
Lipcon, T. (2012). Quorum-based journaling in CDH4.1. Disponível em: http://blog.cloudera.com/blog/2012/10/quorum-based-journaling-in-cdh4-1/. Acessado em: 12/02/2014.
Liskov, B. e Rodrigues, R. (2006). Tolerating byzantine faulty clients in a quorum system. In ICDCS ’06, pages 34–, Washington, DC, USA. IEEE Computer Society.
Liu, T.-J., Wang, W.-C. e Tseng, C.-M. (2011). Organize metadata servers by using quorum system. In IEEE/SICE Int’l Symp. Syst. Integration, pages 1125–1130.
Maekawa, M. (1985). A √n algorithm for mutual exclusion in decentralized systems. ACM Trans. Comput. Syst., 3(2):145–159.
Malkhi, D., Reiter, M. K., Wool, A. e Wright, R. N. (2001). Probabilistic quorum systems. Information and Computation, 170(2):184–206.
Merideth, M. e Reiter, M. (2008). Write markers for probabilistic quorum systems. In Principles of Distributed Systems, volume 5401 of LNCS, pages 5–21. Springer Berlin Heidelberg.
Merideth, M. G. e Reiter, M. K. (2007). Probabilistic opaque quorum systems. In DISC’07, pages 403–419.
Merideth, M. G. e Reiter, M. K. (2010). Selected results from the latest decade of quorum systems research. In Replication, volume 5959 of LNCS, pages 185–206. Springer-Verlag, Berlin, Heidelberg.
Naimi, M. e Thiare, O. (2013). A distributed deadlock free quorum based algorithm for mutual exclusion. IJCSIS, 11(8):7–13.
Naor, M. e Wool, A. (1996). Access control and signatures via quorum secret sharing. In ACM Conference on Computer and Communications Security, pages 157–168. ACM.
Naor, M. e Wool, A. (1998). The load, capacity, and availability of quorum systems. SIAM J. Comput., 27(2):423–447.
Preguica, N. e Martins, J. L. (2001). Revisiting hierarchical quorum systems. In Proc. Int’l Conf. Distr. Comp. Syst. (ICDCS-21).
Ricart, G. e Agrawala, A. K. (1981). An optimal algorithm for mutual exclusion in computer networks. Commun. ACM, 24:9–17.
Ruoso, V. K. (2013). Uma estratégia de testes logarítmica para o algoritmo Hi-ADSD. Master’s thesis, Universidade Federal do Paraná.
Tanaka, K., Higaki, H. e Takizawa, M. (1999). Quorum-based protocol for group communication. In Proc. Int’l Workshops on Parallel Processing, pages 24–29.
Thomas, R. H. (1979). A majority consensus approach to concurrency control for multiple copy databases. ACM Trans. Database Syst., 4(2):180–209.
Vukolić, M. (2010). The origin of quorum systems. Bulletin of the EATCS, 101:125–147.
Abraham, I. e Malkhi, D. (2005). Probabilistic quorums for dynamic systems. Distrib. Comput., 18(2):113–124.
Agrawal, D. e El Abbadi, A. (1991). An efficient and fault-tolerant solution for distributed mutual exclusion. ACM Trans. Comput. Syst., 9(1):1–20.
Agrawal, D. e El Abbadi, A. (1992). The generalized tree quorum protocol: an efficient approach for managing replicated data. ACM Trans. Database Syst., 17(4):689–717.
Amir, Y. e Wool, A. (1996). Evaluating quorum systems over the internet. In FTCS, pages 26–, Washington, DC, USA. IEEE Computer Society.
Atreya, R., Mittal, N. e Peri, S. (2007). A quorum-based group mutual exclusion algorithm for a distributed system with dynamic group set. IEEE Trans. Parallel Distrib. Syst., 18(10):1345–1360.
Barbara, D. e Garcia-Molina, H. (1986). The vulnerability of vote assignments. ACM Trans. Comput. Syst., 4(3):187–213.
Barbara, D., Garcia-Molina, H. e Spauster, A. (1989). Increasing availability under mutual exclusion constraints with dynamic vote reassignment. ACM Trans. Comput. Syst., 7(4):394–426.
Choi, S. C. e Youn, H. Y. (2012). Dynamic hybrid replication effectively combining tree and grid topology. J. Supercomput., 59(3):1289–1311.
Freiling, F. C., Guerraoui, R. e Kuznetsov, P. (2011). The failure detector abstraction. ACM Comput. Surv., 43:9:1–9:40.
Fujita, S. (1998). A quorum based k-mutual exclusion by weighted k-quorum systems. Inf. Process. Lett., 67(4):191–197.
Garcia-Molina, H. e Barbara, D. (1985). How to assign votes in a distributed system. J. ACM, 32(4):841–860.
Gifford, D. K. (1979). Weighted voting for replicated data. In Proceedings of the Seventh ACM Symposium on Operating Systems Principles, SOSP ’79, pages 150–162, New York, NY, USA. ACM.
Guerraoui, R. e Vukolić, M. (2010). Refined quorum systems. Distributed Computing, 23(1):1–42.
Kumar, V. e Agarwal, A. (2011). Generalized grid quorum consensus for replica control protocol. In Computational Intelligence and Communication Networks (CICN), 2011 International Conference on, pages 395–400.
Lipcon, T. (2012). Quorum-based journaling in CDH4.1. Disponível em: http://blog.cloudera.com/blog/2012/10/quorum-based-journaling-in-cdh4-1/. Acessado em: 12/02/2014.
Liskov, B. e Rodrigues, R. (2006). Tolerating byzantine faulty clients in a quorum system. In ICDCS ’06, pages 34–, Washington, DC, USA. IEEE Computer Society.
Liu, T.-J., Wang, W.-C. e Tseng, C.-M. (2011). Organize metadata servers by using quorum system. In IEEE/SICE Int’l Symp. Syst. Integration, pages 1125–1130.
Maekawa, M. (1985). A √n algorithm for mutual exclusion in decentralized systems. ACM Trans. Comput. Syst., 3(2):145–159.
Malkhi, D., Reiter, M. K., Wool, A. e Wright, R. N. (2001). Probabilistic quorum systems. Information and Computation, 170(2):184–206.
Merideth, M. e Reiter, M. (2008). Write markers for probabilistic quorum systems. In Principles of Distributed Systems, volume 5401 of LNCS, pages 5–21. Springer Berlin Heidelberg.
Merideth, M. G. e Reiter, M. K. (2007). Probabilistic opaque quorum systems. In DISC’07, pages 403–419.
Merideth, M. G. e Reiter, M. K. (2010). Selected results from the latest decade of quorum systems research. In Replication, volume 5959 of LNCS, pages 185–206. Springer-Verlag, Berlin, Heidelberg.
Naimi, M. e Thiare, O. (2013). A distributed deadlock free quorum based algorithm for mutual exclusion. IJCSIS, 11(8):7–13.
Naor, M. e Wool, A. (1996). Access control and signatures via quorum secret sharing. In ACM Conference on Computer and Communications Security, pages 157–168. ACM.
Naor, M. e Wool, A. (1998). The load, capacity, and availability of quorum systems. SIAM J. Comput., 27(2):423–447.
Preguica, N. e Martins, J. L. (2001). Revisiting hierarchical quorum systems. In Proc. Int’l Conf. Distr. Comp. Syst. (ICDCS-21).
Ricart, G. e Agrawala, A. K. (1981). An optimal algorithm for mutual exclusion in computer networks. Commun. ACM, 24:9–17.
Ruoso, V. K. (2013). Uma estratégia de testes logarítmica para o algoritmo Hi-ADSD. Master’s thesis, Universidade Federal do Paraná.
Tanaka, K., Higaki, H. e Takizawa, M. (1999). Quorum-based protocol for group communication. In Proc. Int’l Workshops on Parallel Processing, pages 24–29.
Thomas, R. H. (1979). A majority consensus approach to concurrency control for multiple copy databases. ACM Trans. Database Syst., 4(2):180–209.
Vukolić, M. (2010). The origin of quorum systems. Bulletin of the EATCS, 101:125–147.
Publicado
05/05/2014
Como Citar
RODRIGUES, Luiz A.; DUARTE JR., Elias P.; ARANTES, Luciana.
Uma Solução Autonômica para a Criação de Quóruns Majoritários Baseada no Vcube. 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. 74-87.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2014.22948.
