Un algoritmo distribuido de detección y resolución de interbloqueo con coste lineal y carácter dinámico

Abstract

En esta tesis se presenta un algoritmo para la detección y resolución de interbloqueos en sistemas distribuidos para el modelo de solicitud único recurso. El algoritmo resuelve todos los interbloqueos que aparecen en el sistema con coste O(n) en número de mensajes, siendo n el número de procesos interbloqueados. Una de las características más notables del algoritmo propuesto es que se adapta a las modificaciones del medio (aparición y desaparición de esperas entre procesos) sin que ello incremente el coste de la computación. Dotar de dinamismo a la solución propuesta supone un claro avance porque facilita su aplicación a escenarios cambiantes como es cualquier sistema en que se quiera resolver los interbloqueos detectados.

En la tesis se analizan las similitudes que existen entre el problema de elección de líder y el de detección y resolución de interbloqueo en sistemas distribuidos. En realidad, se puede decir que la resolución de interbloqueo distribuido es una versión dinámica del problema de elección de líder. La relación entre ambos problemas se mantiene cuando se analizan sus soluciones. Los algoritmos edge-chasing para resolución de interbloqueo pueden verse como versiones dinámicas de ciertos algoritmos de elección de líder en un anillo. Esto es cierto incluso si se considera la complejidad de ambos tipos de algoritmos. Los de interbloqueo mantienen la complejidad cuadrática de los algoritmos de elección de líder cuando trabajan en una configuración estática del sistema. En base a esta similitud, se diseña un nuevo algoritmo que adapta a comportamientos dinámicos un algoritmo de elección de líder de complejidad lineal.

La tesis estudia diferentes mecanismos que son necesarios para conseguir que el algoritmo actualice su conocimiento de las esperas del sistema, a la vez que trata de localizar la forma de resolver un interbloqueo. Algunos de ellos, como el uso de 'memoria' ya se han utilizado en trabajos previos. Otros, como la simulación de identidad de nodos que han abandonado la ejecución, son novedosos y pudieran ser de utilidad en la adaptación de otros algoritmos a sistemas dinámicos.

La corrección del algoritmo se demuestra formalmente utilizando como herramienta la teoría de Autómatas de Entrada/Salida. La demostración comprueba que el algoritmo resuelve en un tiempo finito todos los interbloqueos que aparecen en el sistema y sólo detecta un interbloqueo si éste realmente existe. En el análisis de complejidad, a diferencia de lo habitual, se han considerado todos los mensajes que el algoritmo genera. No sólo se tienen en cuenta aquéllos que permiten la detección de un interbloqueo ya formado y los necesarios para evitar falsas detecciones, sino también se contabilizan los mensajes que se generan durante el proceso de formación del interbloqueo.