Show simple item record

dc.contributor.advisorFariña Figueredo, Federicoes_ES
dc.contributor.advisorCórdoba Izaguirre, Albertoes_ES
dc.creatorCastillo Latorre, María Antoniaes_ES
dc.date.accessioned2018-06-05T18:09:10Z
dc.date.available2018-06-05T18:09:10Z
dc.date.issued2017
dc.date.submitted2017-09-21
dc.identifier.urihttps://hdl.handle.net/2454/28828
dc.description.abstractEn 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.es_ES
dc.format.extent568 p.es_ES
dc.format.mimetypeapplication/pdfen
dc.language.isospaen
dc.relation.urihttps://biblioteca.unavarra.es/abnetopac/abnetcl.cgi?TITN=493379es
dc.subjectAlgoritmoses_ES
dc.subjectInterbloqueoses_ES
dc.subjectCoste lineales_ES
dc.subjectCarácter dinámicoes_ES
dc.titleUn algoritmo distribuido de detección y resolución de interbloqueo con coste lineal y carácter dinámicoes_ES
dc.typeTesis doctoral / Doktoretza tesiaes
dc.typeinfo:eu-repo/semantics/doctoralThesisen
dc.contributor.departmentUniversidad Pública de Navarra. Departamento de Ingeniería Matemática e Informáticaes_ES
dc.contributor.departmentNafarroako Unibertsitate Publikoa. Matematika eta Informatika Ingeniaritza Sailaeu
dc.rights.accessRightsAcceso abierto / Sarbide irekiaes
dc.rights.accessRightsinfo:eu-repo/semantics/openAccessen
dc.description.doctorateProgramPrograma Oficial de Doctorado en Ingeniería y Arquitectura (RD 1393/2007)es_ES
dc.description.doctorateProgramIngeniaritzako eta Arkitekturako Doktoretza Programa Ofiziala (ED 1393/2007)eu


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record