Catálogo de tesis
Análisis de contención de fallas en algoritmos auto-estabilizantes de elección de líder
Clasificación
27730
Resumen
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 auto-estabilizante 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 (n
4) 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.
Nota de la tesis
Tesis para obtener el grado de Maestro en Ciencias de la Computación
Institución
Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California
Año de publicación
2010
Detalles físicos
xi, 107 hojas : ilustraciones
Comité de tesis
Temas
Auto-estabilización
Self-stabilization
Elección de líder
Leader election
Fallas
Faults
Contención
Containment
Self-stabilization
Elección de líder
Leader election
Fallas
Faults
Contención
Containment
Nota
Miembros del Comité: Fernández Zepeda José Alberto; Rodríguez Jacobo Josefina; Brizuela Rodríguez Carlos Alberto; Paniagua Chávez Carmen GuadalupeIncluye apéndice y referencias bibliográficas
Disponibilidad
| Número de inventario | Volumen | Biblioteca | Ubicación | Estado | Nota |
| 27730 | -- | CICESE | Colección de tesis | Disponible |
Cómo citar
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. xi, 107 hojas.
Opciones



