Exclusão Mútua Distribuída e Robusta para k Recursos Compartilhados
Resumo
Este trabalho apresenta uma solução robusta de k-exclusão mútua em sistemas distribuídos sujeitos a falhas de crash. O algoritmo proposto é baseado no algoritmo de Raymond. Para propagar as mensagens de requisição de forma escalável, foi desenvolvido um algoritmo de árvore geradora mínima. A árvore é criada de forma distribuída, com base nas informações fornecidas por um mecanismo auxiliar de monitoramento de estados dos processos. A solução proposta melhora a eficiência do algoritmo de Raymond na obtenção de recursos e garante o seu funcionamento para até n-1 processos falhos.Referências
Agrawal, D. e El Abbadi, A. (1989). Efficient solution to the distributed mutual exclusion problem. In Proc. of the 8th ACM Symp. on Princ. Distr. Comp., pages 193–200.
Agrawal, D. e El Abbadi, A. (1991). An efficient and fault-tolerant solution for distributed mutual exclusion. ACM Trans. Comput. Syst., 9:1–20.
Avresky, D. R. (1999). Embedding and reconfiguration of spanning trees in faulty hypercubes. IEEE Transactions on Parallel and Distributed Systems, 10(3):211–222.
Bertsekas, D. P., Ozveren, C., Stamoulis, G. D., Tseng, P. e Tsitsiklist, J. N. (1991). Optimal communication algorithms for hypercubes. J. P. Distr. Com., 11:263–275.
Boehm, H.-J. e Adve, S. V. (2012). You don’t know jack about shared variables or memory models. Commun. ACM, 55(2):48–54.
Bouillaguet, M., Arantes, L. e Sens, P. (2008). Fault tolerant k-mutual exclusion algorithm using failure detector. In Int’l Symp. on Parallel and Distr. Comp., pages 343–350.
Bouillaguet, M., Arantes, L. e Sens, P. (2009). A timer-free fault tolerant k-mutual exclusion algorithm. In 4th Latin-American Symp. on Dep. Comp., pages 41–48.
Bulgannawar, S. e Vaidya, N. (1995). A distributed k-mutual exclusion algorithm. In Proceedings of the 15th Int’l Conf. on Distr. Comp. Systems, pages 153–160.
Delporte-Gallet, C., Fauconnier, H., Guerraoui, R. e Kouznetsov, P. (2005). Mutual exclusion in asynchronous systems with failure detectors. J. P. Distr. Comp., 65:492–505.
Duarte Jr., E. P. e Nanya, T. (1998). A hierarchical adaptive distributed system-level diagnosis algorithm. IEEE Transactions on Computers, 47(1):34–45.
Gallager, R. G., Humblet, P. A. e Spira, P. M. (1983). A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst., 5:66–77.
Garcia-Molina, H. e Barbara, D. (1985). How to assign votes in a distributed system. J. ACM, 32:841–860.
Kruskal Jr., J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. In Proc. of the American Mathematical Society, pages 48–50.
Lamport, L. (1978). Time clocks, and the ordering of events in a distributed system. Commun. ACM, 21:558–565.
Le Lann, G. (1977). Distributed systems - towards a formal approach. In IFIP Congress, pages 155–160.
Naimi, M. (1996). Distributed mutual exclusion on hypercubes. SIGOPS Oper. Syst. Rev., 30:46–51.
Naimi, M., Trehel, M. e Arnold, A. (1996). A log (n) distributed mutual exclusion algorithm based on path reversal. J. Parallel Distrib. Comput., 34:1–13.
Prim, R. C. (1957). Shortest connection networks and some generalizations. Bell System Technical Journal, 36(6):1389–1401.
Raymond, K. (1989a). A distributed algorithm for multiple entries to a critical section. Inf. Process. Lett., 30:189–193.
Raymond, K. (1989b). A tree-based algorithm for distributed mutual exclusion. ACM Trans. Comput. Syst., 7:61–77.
Raynal, M. (1991). A simple taxonomy for distributed mutual exclusion algorithms. SIGOPS Oper. Syst. Rev., 25:47–50.
Raynal, M. e Beeson, D. (1986). Algorithms for mutual exclusion. MIT Press, Cambridge, MA, USA.
Ricart, G. e Agrawala, A. K. (1981). An optimal algorithm for mutual exclusion in computer networks. Commun. ACM, 24:9–17.
Rodrigues, L. A. e Jansh-Pôrto, I. E. (2008). Ampliação do framework neko para a simulação de defeitos em algoritmos distribuı́dos. In Proc. 7th I2TS, pages 1–8.
Romano, P. e Rodrigues, L. (2009). An efficient weak mutual exclusion algorithm. In 8th Int’l Symp. on Parallel and Distributed Computing, pages 205 –212.
Sanders, B. A. (1987). The information structure of distributed mutual exclusion algorithms. ACM Trans. Comput. Syst., 5:284–299.
Suzuki, I. e Kasami, T. (1985). A distributed mutual exclusion algorithm. ACM Trans. Comput. Syst., 3:344–349.
Urbán, P., Défago, X. e Schiper, A. (2002). Neko: A single environment to simulate and prototype distributed algorithms. Journal of Inf. Science and Eng., 18(6):981–997.
Agrawal, D. e El Abbadi, A. (1991). An efficient and fault-tolerant solution for distributed mutual exclusion. ACM Trans. Comput. Syst., 9:1–20.
Avresky, D. R. (1999). Embedding and reconfiguration of spanning trees in faulty hypercubes. IEEE Transactions on Parallel and Distributed Systems, 10(3):211–222.
Bertsekas, D. P., Ozveren, C., Stamoulis, G. D., Tseng, P. e Tsitsiklist, J. N. (1991). Optimal communication algorithms for hypercubes. J. P. Distr. Com., 11:263–275.
Boehm, H.-J. e Adve, S. V. (2012). You don’t know jack about shared variables or memory models. Commun. ACM, 55(2):48–54.
Bouillaguet, M., Arantes, L. e Sens, P. (2008). Fault tolerant k-mutual exclusion algorithm using failure detector. In Int’l Symp. on Parallel and Distr. Comp., pages 343–350.
Bouillaguet, M., Arantes, L. e Sens, P. (2009). A timer-free fault tolerant k-mutual exclusion algorithm. In 4th Latin-American Symp. on Dep. Comp., pages 41–48.
Bulgannawar, S. e Vaidya, N. (1995). A distributed k-mutual exclusion algorithm. In Proceedings of the 15th Int’l Conf. on Distr. Comp. Systems, pages 153–160.
Delporte-Gallet, C., Fauconnier, H., Guerraoui, R. e Kouznetsov, P. (2005). Mutual exclusion in asynchronous systems with failure detectors. J. P. Distr. Comp., 65:492–505.
Duarte Jr., E. P. e Nanya, T. (1998). A hierarchical adaptive distributed system-level diagnosis algorithm. IEEE Transactions on Computers, 47(1):34–45.
Gallager, R. G., Humblet, P. A. e Spira, P. M. (1983). A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst., 5:66–77.
Garcia-Molina, H. e Barbara, D. (1985). How to assign votes in a distributed system. J. ACM, 32:841–860.
Kruskal Jr., J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. In Proc. of the American Mathematical Society, pages 48–50.
Lamport, L. (1978). Time clocks, and the ordering of events in a distributed system. Commun. ACM, 21:558–565.
Le Lann, G. (1977). Distributed systems - towards a formal approach. In IFIP Congress, pages 155–160.
Naimi, M. (1996). Distributed mutual exclusion on hypercubes. SIGOPS Oper. Syst. Rev., 30:46–51.
Naimi, M., Trehel, M. e Arnold, A. (1996). A log (n) distributed mutual exclusion algorithm based on path reversal. J. Parallel Distrib. Comput., 34:1–13.
Prim, R. C. (1957). Shortest connection networks and some generalizations. Bell System Technical Journal, 36(6):1389–1401.
Raymond, K. (1989a). A distributed algorithm for multiple entries to a critical section. Inf. Process. Lett., 30:189–193.
Raymond, K. (1989b). A tree-based algorithm for distributed mutual exclusion. ACM Trans. Comput. Syst., 7:61–77.
Raynal, M. (1991). A simple taxonomy for distributed mutual exclusion algorithms. SIGOPS Oper. Syst. Rev., 25:47–50.
Raynal, M. e Beeson, D. (1986). Algorithms for mutual exclusion. MIT Press, Cambridge, MA, USA.
Ricart, G. e Agrawala, A. K. (1981). An optimal algorithm for mutual exclusion in computer networks. Commun. ACM, 24:9–17.
Rodrigues, L. A. e Jansh-Pôrto, I. E. (2008). Ampliação do framework neko para a simulação de defeitos em algoritmos distribuı́dos. In Proc. 7th I2TS, pages 1–8.
Romano, P. e Rodrigues, L. (2009). An efficient weak mutual exclusion algorithm. In 8th Int’l Symp. on Parallel and Distributed Computing, pages 205 –212.
Sanders, B. A. (1987). The information structure of distributed mutual exclusion algorithms. ACM Trans. Comput. Syst., 5:284–299.
Suzuki, I. e Kasami, T. (1985). A distributed mutual exclusion algorithm. ACM Trans. Comput. Syst., 3:344–349.
Urbán, P., Défago, X. e Schiper, A. (2002). Neko: A single environment to simulate and prototype distributed algorithms. Journal of Inf. Science and Eng., 18(6):981–997.
Publicado
30/04/2012
Como Citar
RODRIGUES, Luiz A.; DUARTE JR., Elias P.; ARANTES, Luciana.
Exclusão Mútua Distribuída e Robusta para k Recursos Compartilhados. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 13. , 2012, Ouro Preto/MG.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2012
.
p. 43-56.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2012.23079.
