Avances en Algoritmos de Exclusión Mutua en Sistemas Distribuidos

Autores/as

  • Daniel Sánchez Ruiz Facultad de Ciencias de la Computación, Benemérita Universidad Autónoma de Puebla, Av San Claudio y 14 Sur, Cd Universitaria, Puebla, Puebla, México, C.P. 72592
  • Hilda Castillo Zacatelco Facultad de Ciencias de la Computación, Benemérita Universidad Autónoma de Puebla, Av San Claudio y 14 Sur, Cd Universitaria, Puebla, Puebla, México, C.P. 72592
  • Claudia Zepeda Cortés Facultad de Ciencias de la Computación, Benemérita Universidad Autónoma de Puebla, Av San Claudio y 14 Sur, Cd Universitaria, Puebla, Puebla, México, C.P. 72592
  • Rafael de la Rosa Flores Facultad de Ciencias de la Computación, Benemérita Universidad Autónoma de Puebla, Av San Claudio y 14 Sur, Cd Universitaria, Puebla, Puebla, México, C.P. 72592
  • Ana Patricia Cervantes Máquez Facultad de Ciencias de la Computación, Benemérita Universidad Autónoma de Puebla, Av San Claudio y 14 Sur, Cd Universitaria, Puebla, Puebla, México, C.P. 72592
  • Misael Limón Martínez Facultad de Ciencias de la Computación, Benemérita Universidad Autónoma de Puebla, Av San Claudio y 14 Sur, Cd Universitaria, Puebla, Puebla, México, C.P. 72592
  • José Luis Carballido Carranza Facultad de Ciencias de la Computación, Benemérita Universidad Autónoma de Puebla, Av San Claudio y 14 Sur, Cd Universitaria, Puebla, Puebla, México, C.P. 72592

DOI:

https://doi.org/10.30973/progmat/2019.11.1/3

Palabras clave:

Exclusión mutua, Sistema Distribuido, Tolerancia a Fallas

Resumen

En este artículo se presenta un análisis de algunos trabajos recientes sobre algoritmos de exclusión mutua en sistemas distribuidos. Estos algoritmos pueden clasificarse en algoritmos basados en permisos y algoritmos basados en tokens. En este trabajo se analizan únicamente los que están basados en tokens por la diversidad que existe de ellos. Para cada algoritmo analizado se exponen ventajas y desventajas las cuales dan pie a nuevas investigaciones. Además, se presentan aplicaciones en donde estos algoritmos son utilizados y se realiza una comparación entre las propuestas.

Biografía del autor/a

Daniel Sánchez Ruiz, Facultad de Ciencias de la Computación, Benemérita Universidad Autónoma de Puebla, Av San Claudio y 14 Sur, Cd Universitaria, Puebla, Puebla, México, C.P. 72592

Estudió la Licenciatura en Ingeniería en Ciencias de la Computación en la Benemérita Universidad Autónoma de Puebla (BUAP), y la Maestría en Ciencias de la Computación en la línea de investigación de Sistemas Distribuidos también en la BUAP. En su tesis de maestría trabajó en el área de Reconocimiento de Patrones y Métodos Estocásticos. Sus temas de interés son Aprendizaje Automático, Visión artificial y Reconocimiento de Patrones mediante métodos estadísticos, con especial atención en ámbitos médicos y análisis de personalidad. Actualmente, se encuentra realizando los trámites necesarios para ingresar al programa de doctorado en Ciencias Computacionales en el Instituto Nacional de Astrofísica, Óptica y Electrónica (INAOE).

Hilda Castillo Zacatelco, Facultad de Ciencias de la Computación, Benemérita Universidad Autónoma de Puebla, Av San Claudio y 14 Sur, Cd Universitaria, Puebla, Puebla, México, C.P. 72592

Estudió la Licenciatura en Computación en la Benemérita Universidad Autónoma de Puebla (BUAP), posteriormente estudió la Maestría en Ciencias de la Computación en la BUAP, y el doctorado en Ciencias Computacionales en el Centro de Investigación y Desarrollo Tecnológico (CENIDET) de Cuernavaca. Es Profesor-Investigador en la Facultad de Ciencias de la Computación, BUAP; es miembro de la academia de Programación y de la de Software de base, e imparte cursos de estas áreas; forma parte del cuerpo académico Cómputo Distribuido. Actualmente sus temas de interés son los Objetos de Aprendizaje, los Sistemas Distribuidos, el problema de Bin Packing y el Diseño de Algoritmos.

Claudia Zepeda Cortés, Facultad de Ciencias de la Computación, Benemérita Universidad Autónoma de Puebla, Av San Claudio y 14 Sur, Cd Universitaria, Puebla, Puebla, México, C.P. 72592

Estudió la Licenciatura en Computación en la Benemérita Universidad Autónoma de Puebla, posteriormente estudió la maestría en Ciencias con Especialidad en Sistemas Computacionales en la Universidad de las Américas Puebla, y el doctorado en Ciencias Computacionales en conjunto entre el INSA de Lyon-Francia y la Universidad de las Américas Puebla. Es ProfesorInvestigador en la Facultad de Ciencias de la Computación, BUAP; es miembro de la academia de Matemáticas y de la de Teoría de la Computación, e imparte cursos de estas áreas; forma parte del cuerpo académico Cómputo Distribuido. Actualmente sus temas de interés son los Objetos de Aprendizaje y las aplicaciones en Programación Lógica. 

Rafael de la Rosa Flores, Facultad de Ciencias de la Computación, Benemérita Universidad Autónoma de Puebla, Av San Claudio y 14 Sur, Cd Universitaria, Puebla, Puebla, México, C.P. 72592

Estudió la Licenciatura en Computación en la Benemérita Universidad Autónoma de Puebla (BUAP), posteriormente estudió la Maestría en Ciencias de la Computación en la BUAP, y el doctorado en Ciencias Computacionales en el Centro de Investigación y Desarrollo Tecnológico (CENIDET) de Cuernavaca. Es Profesor-Investigador en la Facultad de Ciencias de la Computación, BUAP; es miembro de la academia de Bases de datos e Ingeniería de Software y de la de Software de base, e imparte cursos de estas áreas; forma parte del cuerpo académico Cómputo Distribuido. Actualmente sus temas de interés son los Objetos de Aprendizaje, los Sistemas Distribuidos, el problema de Bin Packing y los Dispositivos Móviles.

Ana Patricia Cervantes Máquez, Facultad de Ciencias de la Computación, Benemérita Universidad Autónoma de Puebla, Av San Claudio y 14 Sur, Cd Universitaria, Puebla, Puebla, México, C.P. 72592

Estudió la Licenciatura en Computación en la Benemérita Universidad Autónoma de Puebla (BUAP), posteriormente estudió la maestría en Ciencias con Especialidad en Sistemas Computacionales en la Universidad de las Américas Puebla. Actualmente es Profesor-Investigador en la Facultad de Ciencias de la Computación, BUAP, imparte cursos del área de programación básica y software de base, y está realizando su doctorado en la Universidad Popular Autónoma del Estado de Puebla en el área de Ingeniería de Software. Es colaboradora del cuerpo académico de Cómputo Distribuido. Sus temas de interés son los Objetos de Aprendizaje, la Calidad en Uso y el Diseño de Algoritmos.

Misael Limón Martínez, Facultad de Ciencias de la Computación, Benemérita Universidad Autónoma de Puebla, Av San Claudio y 14 Sur, Cd Universitaria, Puebla, Puebla, México, C.P. 72592

Estudiante de la Ingeniería en Ciencias de la Computación en la Facultad de Ciencias de la Computación de la Benemérita Universidad Autónoma de Puebla (BUAP). Ha participado en varios programas de Haciendo Ciencia en apoyo a proyectos de investigación de la BUAP. Cursa actualmente el sexto cuatrimestre de la carrera. Sus temas de interés son los Objetos de Aprendizaje y los Sistemas Operativos.

José Luis Carballido Carranza, Facultad de Ciencias de la Computación, Benemérita Universidad Autónoma de Puebla, Av San Claudio y 14 Sur, Cd Universitaria, Puebla, Puebla, México, C.P. 72592

Estudió su doctorado en Matemáticas en la Facultad de Ciencias Físico Matemáticas, con la tesis titulada “Fundamentos Matemáticos de la Semántica P-stable en Programación Lógica”.

Citas

Tanenbaum, A. S.; Van Steen, M., Distributed systems: principles and paradigms. Prentice-Hall. 2007.

Velazquez, M. G., A survey of distributed mutual exclusion algorithms. Colorado State University. 1993.

Saxena, P. C.; Rai, J., A survey of permissionbased distributed mutual exclusion algorithms. Computer standards & interfaces. 2003, 25(2), 159-181. https://doi.org/10.1016/S0920-5489(02)00105-8

Maekawa, M.; Oldehoeft, A.E.; Oldehoeft, R.R., Operating Systems, Advanced Concepts. Benjamin-Cummings. 1987.

Silberschatz, A; Peterson, J. L., Operating System Concepts. Addison-Wesley, Alternate Edition. 1998.

Raynal, M., A simple taxonomy for distributed mutual exclusion algorithms. Operating Systems Review. 1991, 25(2), 47-49. https://doi.org/10.1145/122120.122123

Singhal, M., A heuristically-aided algorithm for mutual exclusion in distributed systems. IEEE Transactions on Computers. 1989, 38(5), 651-662. https://doi.org/10.1109/12.24268

Agrawal, D.; El Abbadi, A., An efficient and fault-tolerant solution for distributed mutual exclusion. ACM Transactions on Computer Systems. 1991, 9(1), 1-20. https://doi.org/10.1145/103727.103728

Chandy, K. M.; Lamport, L., Distributed snapshots: Determining global states of distributed systems. ACM Transactions on Computer Systems. 1985, 3(1), 63-75. https://doi.org/10.1145/214451.214456

Foster, I., Designing and building parallel programs. Addison Wesley Publishing Company, 1995.

Maekawa, M., An algorithm for mutual exclusion in decentralized systems. ACM Transactions on Computer Systems. 1985, 3(2), 145-159. https://doi.org/10.1145/214438.214445

Manivannan, D.; Singhal, M., Decentralized token generation scheme for token-based connecting mesh. International Journal of Advanced Research in Computer Science. 2013, 4( 10).

Mellor-Crummey, J. M.; Scott, M. L., Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Transactions on Computer Systems. 1991, 9(1), 21-65. https://doi.org/10.1145/103727.103729

Neilsen, M. L.; Mizuno, M., A dag-based algorithm for distributed mutual exclusion. In Distributed Computing Systems, 11th International Conference on, IEEE. 1991, 354- 360. https://doi.org/10.1109/ICDCS.1991.148689

Singhal, M., A taxonomy of distributed mutual exclusion. Journal of Parallel and Distributed Computing. 1993, 18(1), 94-101. https://doi.org/10.1006/jpdc.1993.1048

Sunderam, V. S., PVM: A framework for parallel distributed computing. Concurrency: practice and experience. 1990, 2(4), 315-339. https://doi.org/10.1002/cpe.4330020404

Suzuki, I; Kasami T., A distributed mutual exclusion algorithm. ACM Transactions on Computer Systems. 1985, 3(4), 344-349. A distributed mutual exclusion algorithm

Raymond, K., A tree-based algorithm for distributed Mutual Exclusion. ACM Transactions on Computer Systems. 1989, 7(1), 61-77. https://doi.org/10.1145/58564.59295

Naimi, M; Trehel, M., How to detect a failure and regenerate the token in the log(n) distributed algorithm for mutual exclusion. Proc. Of the Second Workshop on Distributed Algorithms, Lecture Notes in CS. 1987, 155-166. https://doi.org/10.1007/BFb0019802

Lamport, L., Time, clocks, and the ordering of events in a distributed system. Communications of the ACM. 1978, 21(7), 558- 565. https://doi.org/10.1145/3335772.3335934

Ricart, G; Agrawala, A., An optimal algorithm for mutual exclusion in computer networks. Communications of the ACM. 1981, 24(1), 9-17.

Khah, Hussein N.; Mazrae, A. A.; Koroupi, F., Presenting a new algorithm for management mutual exclusion in distributed systems by Connecting MESH. International Journal of Advanced Research in Computer Science . Sep/Oct2013, Vol. 4 Issue 10, p44-48. 5p.

Kanrar, S., Chattopadhyay, S., & Chaki, N. A New Link Failure Resilient Priority Based Fair Mutual Exclusion Algorithm for Distributed Systems. Journal of network and systems management. 2013, 21(1), 1-24. https://doi.org/10.1007/s10922-011-9218-9

Razzaque, M. A.; Hong, C. S., Multi-token distributed mutual exclusion algorithm. Advanced Information Networking and Applications, AIN, 22nd International Conference on, IEEE. 2008, 963-970. https://doi.org/10.1109/AINA.2008.38

Neamatollahi, P.; Sedaghat, Y.; Naghibzadeh, M., A simple token-based algorithm for the mutual exclusion problem in distributed systems. The Journal of Supercomputing. 2017, 1-18. mutual exclusion algorithms. Computer Systems Science and Engineering 1996, 11(1), 45-54. https://doi.org/10.1007/s11227-017-1985-y

Khanna, A.; Singh, A. K.; Swaroop, A., A Token-Based Solution to Group Local Mutual Exclusion Problem In Mobile Ad Hoc Networks. Arabian Journal for Science and Engineering. 2016, 41(12), 5181-5194. https://doi.org/10.1007/s13369-016-2199-y

Lejeune, J.; Arantes, L.; Sopena, J.; Sens, P., A fair starvation-free prioritized mutual exclusion algorithm for distributed systems. Journal of Parallel and Distributed Computing. 2015, 83, 13-29. https://doi.org/10.1016/j.jpdc.2015.04.002

Bindahman, S.; Yong, C. H., Performance enhancement for Distributed Lock Manager using Hybrid Multicast and Ring algorithm. In Digital Information and Communication Technology and it's Applications. 2012 Second International Conference on. IEEE, 2012, 388- 393. https://doi.org/10.1109/DICTAP.2012.6215390

Descargas

Publicado

28-02-2019

Cómo citar

Sánchez Ruiz, D., Castillo Zacatelco, H., Zepeda Cortés, C., de la Rosa Flores, R., Cervantes Máquez, A. P., Limón Martínez, M., & Carballido Carranza, J. L. (2019). Avances en Algoritmos de Exclusión Mutua en Sistemas Distribuidos. Programación matemática Y Software, 11(1), 15–25. https://doi.org/10.30973/progmat/2019.11.1/3

Número

Vol. 11 Núm. 1 (2019): Febrero de 2019

Sección

Artículos

Licencia

Derechos de autor 2019 Programación Matemática y Software

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.

Usted es libre de:

Compartir — compartir y redistribuir el material publicado en cualquier medio o formato.
Adaptar — combinar, transformar y construir sobre el material para cualquier propósito, incluso comercialmente.

Bajo las siguientes condiciones:

Atribución — Debe otorgar el crédito correspondiente, proporcionar un enlace a la licencia e indicar si se realizaron cambios. Puede hacerlo de cualquier manera razonable, pero de ninguna manera que sugiera que el licenciador lo respalda a usted o a su uso.
  Sin restricciones adicionales: no puede aplicar términos legales o medidas tecnológicas que restrinjan legalmente a otros a hacer cualquier cosa que permita la licencia.