Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/1892| Análisis de contención de fallas en algoritmos auto-estabilizantes de elección de líder Analysis of containment of faults in algorithms selt-stabilizing of leader election | |
| LUIS DANIEL RODRÍGUEZ ALTAMIRANO | |
| JOSE ALBERTO FERNANDEZ ZEPEDA | |
| Acceso Abierto | |
| Atribución | |
| Auto-estabilización Self-stabilization Elección de líder Leader election Fallas Faults Contención Containment | |
| "Self-stabilization is a relatively new paradigm for fault tolerance in distributed systems. The goal of self-stabilization is to maintain a system free of errors. A selfstabilizing algorithm helps a system to recover from transient faults in a finite number of steps, without involving any external agent. There are many graph problems that have been solved by self-stabilizing algorithms. This thesis deals with one of them, the leader election problem, whose definition is as follows. Given a graph G and set of nodes C of G, the idea is to elect a unique node from the set C. A fault containment technique helps self-stabilizing algorithms to recover faster from transient faults. This technique avoids that the effect of a fault propagates to healthy nodes of the graph. The objective of this thesis is to incorporate a fault containment technique to a self-stabilizing leader election algorithm. Our algorithm is restricted to run on anonymous trees. We proved the correctness of the algorithm and show that it terminates in O(n4) time, starting in any arbitrary state. Once the tree is in a legal state and a simple fault occurs, the proposed algorithm takes the tree to a legal state in constant time. The most significant aspect of the algorithm is that the fault –gap is independent of the network size." "La auto-estabilización es un paradigma de tolerancia a fallas en sistemas distribuidos. El objetivo de la auto-estabilización es mantener a un sistema libre de errores. Los algoritmos auto-estabilizantes buscan que un sistema se recupere por si solo de fallas transitorias que lo afecten en un número finito de pasos sin la intervención de agente externo alguno. Los algoritmos de elección de líder tienen el propósito de elegir a un nodo de un conjunto de nodos candidatos, en ocasiones indistinguibles entre sí. La idea de elegir un nodo como líder es que tenga privilegios sobre los demás nodos. Los algoritmos auto-estabilizantes se ayudan de la contención de fallas para recuperarse en menor tiempo de las fallas que lo afecten. La contención de fallas busca aislar las fallas para que no se propaguen y evitar que contaminen otras partes del sistema. La presente investigación busca agregar contención de fallas a un algoritmo auto estabilizante de elección de líder. Se presenta un nuevo algoritmo anónimo autoestabilizante de elección de líder con contención de fallas en grafos de árbol. Se demuestra que el algoritmo es correcto y que termina en O (n4) pasos, empezando en cualquier estado inicial arbitrario. El algoritmo no puede elegir un nodo hoja como líder. El algoritmo de elección de líder con contención de fallas confina el efecto de cualquier falla simple a los vecinos inmediatos del nodo que falla, con un tiempo esperado de recuperación de O(1). El aspecto más importante del algoritmo es que la brecha de falla, definida como el intervalo más pequeño después del cual el sistema está listo para manejar la siguiente falla con la misma eficiencia, no depende del tamaño de la red." | |
| CICESE | |
| 2010 | |
| Tesis de maestría | |
| Español | |
| Rodríguez Altamirano, L. D.2010.Análisis de contención de fallas en algoritmos auto-estabilizantes de elección de líder.Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California.52 pp. | |
| LÓGICA | |
| Aparece en las colecciones: | Artículos - Ciencias de la Computación |
Cargar archivos:
| Fichero | Tamaño | Formato | |
|---|---|---|---|
| ebiblio18328.pdf | 20.99 MB | Adobe PDF | Visualizar/Abrir |