Exclusão Mútua Distribuída e Robusta para k Recursos Compartilhados

• Luiz A. Rodrigues UNIOESTE / UFPR
• Elias P. Duarte Jr. UFPR
• Luciana Arantes Université Pierre et Marie Currie

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

Abstract

This paper presents a robust k-mutual exclusion solution in distributed systems subject to crash failures. The proposed algorithm is based on Raymond’s algorithm. To propagate the request messages in a scalable way, we propose a minimum spanning tree algorithm. The tree is created in a distributed manner, based on information provided by an auxiliary monitoring system. The solution improves the efficiency of the Raymond’s algorithm in obtaining resources and works correctly for up to n-1 faulty processes.

References

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.