Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/312| Análisis de algoritmos auto-estabilizantes para elección de líder Analysis of self-stabilizing algorithms for leader election | |
| Juan Paulo Alvarado Magaña | |
| Jose Alberto Fernandez Zepeda | |
| Acceso Abierto | |
| Atribución | |
| Auto-Estabilización,Elección de líder | |
| La auto-estabilización es un paradigma de tolerancia a fallas, en donde un sistema distribuido puede llegar a un estado global válido a partir de cualquier estado arbitrario inválido en un número ?nito de pasos. El tema de investigación de esta tesis son los algoritmos auto-estabilizantes para elección de líder en un árbol. Eligir un líder en cualquier grafo es asignar atributos particulares y únicos a un solo nodo del grafo. Un sistema distribuido puede perder su líder cuando sufre alguna perturbación, es obligación del algoritmo auto-estabilizante detectar el error y enseguida ejecutarse para elegir un líder nuevo. En este trabajo de tesis se estudia en particular el algoritmo auto-estabilizante para elección de líder de Xu y Srimani (Xu y Srimani, 2005). Este algoritmo elige un líder en O(n4) pasos (donde n es el número total de nodos en el árbol) utilizando siempre el peor de los casos con un calendarizador adversario, lo cual resulta muy costoso. El objetivo de la investigación es demostrar que el algoritmo de Xu y Srimani (Xu y Srimani, 2005) para elegir un líder requiere en promedio mucho menos pasos que O(n4). Para lograr esto se propone el calendarizador justo. Se analiza el desempeño del algoritmo en diferentes árboles con topologías muy estudiadas en la literatura utilizando el calendarizador propuesto y se comprueba que en promedio se requieren O(nlog2 n) pasos para estabilizar dichos árboles. Adicionalmente, se proponen cuatro métodos diferentes para generar árboles arbitrarios donde se utiliza el calendarizador justo y así estudiar el desempeño del algoritmo en estos árboles. Aqui también se demuestra que en promedio se requieren O(nlog2 n) pasos para estabilizar estos árboles, en la mayoría de los casos. También se propone una modi?cación del algoritmo para permitir que los nodos ejecuten sus operaciones en paralelo, de esta manera el algoritmo se acelera considerablemente y el calendarizador se elimina por completo. Se demuestra que para este caso se requiren en promedio O(klogn) pasos para estabilizar un árbol, donde k es el diámetro del árbol. El calendarizador justo funciona utilizando procedimientos aleatorios. En este trabajo de tesis se demuestra que los resultados obtenidos con el calendarizador justo se logran con alta probabilidad. Self-stabilization is a paradigm for fault tolerance in which a distributed system can reach a global valid state from any arbitrary invalid state in a ?nite number of steps. The research topic of this thesis is self-stabilizing algorithms for leader election in a tree. Choosing a leader in any graph is to assign unique attributes to one speci?c node of the graph. A distributed system can loose its leader by su?ering a disturbance, it is the obligation of the self-stabilizing algorithm to detect the error and immediately choose a new leader. Xu and Srimani’s self-stabilizing algorithm for leader election (Xu y Srimani, 2005) is the main research topic of this thesis. This algorithm can choose a leader in O(n4) steps (where n is the total number of nodes in the tree) with an adverse daemon (worst case), this execution time is very costly. The objective is to demonstrate that Xu and Srimani’s algorithm requires on average less then O(n4) steps. To reach this objective a fair daemon is proposed. The algorithm’s performance on typical tree con?gurations is analyzed using the fair daemon and it is proven that on average, the algorithm uses O(nlog2 n) steps to stabilize. Additionally, four methods to generate arbitrary tree graphs are proposed, where the fairdaemonis also used andtheperformance ofthealgorithmisanalyzed. Itis also proven that on average the algorithm uses O(nlog2 n) steps on many of these cases. Some modi?cations to the algorithm are also proposed to allow the nodes to execute their operations in parallel. By doing so, the execution time of the algorithm is greatly improved and the daemon is completely eliminated. It is proven that for these cases, the algorithm uses on average O(klogn) steps to stabilize a tree of diameter k. The fair daemon uses a probabilistic method. It is proven in this thesis that the results given by the fair daemon occur with a high probability. | |
| CICESE | |
| 2006 | |
| Tesis de maestría | |
| Español | |
| Alvarado Magaña,J.P.2006.Análisis de algoritmos auto-estabilizantes para 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.81 pp. | |
| CIENCIA DE LOS ORDENADORES | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 173201.pdf | Versión completa de la tesis | 503.91 kB | Adobe PDF | Visualizar/Abrir |