Biblioteca CICESE

Edificio Dr. Nicolás Grijalva y Ortiz

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
Temas
Auto-estabilización
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 Guadalupe
Incluye 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
Version en PDF de la tesis
Descargar texto completo... (20.49 MB)
 
 

CICESE

Carretera Ensenada-Tijuana No. 3918,
Zona Playitas, C.P. 22860,
Ensenada, B. C. México.

Teléfono: 01 (646) 175-05-00 ext 23044