Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/2463| Algoritmos auto-estabilizantes para sistemas basados en preferencias Self-stabilizing algorithms for preference -based systems | |
| Daniel Fajardo Delgado | |
| Jose Alberto Fernandez Zepeda | |
| Acceso Abierto | |
| Atribución | |
| Algoritmo, Fallas de sistema, Sistemas distribuidos | |
| En el presente trabajo se estudian los algoritmos auto-estabilizantes para sistemas distribuidos con el enfoque basado en preferencias. Bajo este enfoque, se define a la preferencia de un proceso como un indicador acerca de la calidad de servicio que dicho proceso puede proveer en el sistema. El estudio se divide en tres fases. La primera fase consiste en la generación de un historial de fallas que permita definir las preferencias de los procesos de una cadena lineal orientada; en este caso, la preferencia de cada proceso se vincula al número de fallas incurridas individualmente. Se diseña un algoritmo que utiliza el coloreado auto-estabilizante de grafos para añadir las características de detección, corrección y registro de fallas en el sistema; la suposición principal es que el cambio de color en un proceso representa una falla incurrida en el mismo. Se demuestra que el algoritmo propuesto es correcto y se establece el tiempo de ejecución. La segunda fase del estudio se enfoca al problema de elección de líder autoestabilizante bajo el enfoque basado en preferencias. El objetivo es garantizar que el líder electo siempre sea el proceso con la mayor preferencia en el sistema. En esta fase, se supone que cada proceso “conoce” de antemano su preferencia y que ésta puede variar constantemente en el tiempo. Inicialmente se diseña un algoritmo auto-estabilizante de elección de líder basado en sólo dos preferencias para cadenas lineales anónimas. Posteriormente, se diseña un algoritmo aleatorio auto-estabilizante que funciona para árboles anónimos con dos o más preferencias. Este último algoritmo garantiza la elección de líder incluso en configuraciones simétricas en el que todas las preferencias son iguales. Se demuestra que el algoritmo tiene un tiempo promedio de ejecución óptimo y se corroboran estos resultados mediante simulaciones experimentales. Finalmente, la tercera fase del estudio consiste en explorar el enfoque basado en preferencias para sistemas distribuidos desde el punto de vista de la teoría de juegos. En esta fase se plantea un juego al que se denomina el Problema de Asignación de Guardaespaldas (PAG), que ilustra el comportamiento de procesos con objetivos individuales contradictorios en sistemas distribuidos. En particular, el juego trata sobre el conflicto de intereses entre dos clases de procesos que maximizan/minimizan su distancia a un proceso especial denominado raíz. Una solución del PAG es un árbol de expansión enraizado en el que existe una condición de equilibrio con el máximo bienestar social. Se analiza la ineficiencia de los equilibrios del juego con base en un enfoque enteramente cooperativo y otro enteramente no-cooperativo. Por otro lado, se diseñan dos algoritmos, CBAP y DBAP, que proveen de soluciones aproximadas para el juego del PAG. Se demuestra que estos algoritmos siempre terminan en una configuración de equilibrio y se analiza el tiempo de ejecución con base en el enfoque de cooperación utilizado. Se realizan simulaciones experimentales para comparar la calidad de los equilibrios obtenidos por los algoritmos propuestos. Adicionalmente, se diseña una versión auto-estabilizante del algoritmo DBAP, denominado DBAP-st, que funciona bajo el enfoque enteramente no-cooperativo. Este algoritmo garantiza el restablecimiento de un equilibrio para el PAG en un sistema distribuido, incluso después de alguna perturbación en la configuración del mismo. In this work, we study self-stabilizing algorithms for distributed systems with the preference-based approach. Under this approach, processes have preferences that represent indicators of the quality of service that each one can provide in the system. We divide this study in three phases. The first phase of this work consists on the generation of a fault record to define the preferences of each process in an oriented linear chain; for this, we assume that the preference of any process relates directly to the number of faults incurred individually in it. We design an algorithm that use a self-stabilizing method for coloring graphs to add to the chain, characteristics of local detection and recovery. We assume that the change on the color of any process represents a fault incurred in it. We prove the correctness of the proposed algorithm and determine its running time. The second phase of this work comprises the study of the leader election problem under the preference-based approach, where the algorithm always selects as leader to the process with the highest preference in the system. In this phase, we assume that any process previously “knows” the value of its preference and that the preferences of the processes change over time. Initially, we design a self-stabilizing leader election algorithm for nonymous linear chains with only two preferences in their processes. Later, we design a new randomized self-stabilizing leader election algorithm for anonymous trees with two or more preferences. The algorithm is able to solve problems with symmetric configurations where each preference is the same. We prove that this last algorithm has an optimal average time complexity and we also performed experimental simulations to corroborate these results. Finally, the third phase of this work corresponds to the study of the preference-based approach in distributed systems from a game-theoretic point of view. We introduce the Bodyguard Allocation Problem (BAP) game, that illustrates the behavior of processes with contradictory individual goals in distributed systems. In particular, the game deals with the conflict of interest between two classes of processes that maximize/minimize their distance to a special process called the root. A solution of the BAP game represents a rooted spanning tree in which there exists a condition of equilibrium with maximum social welfare. We analyze the inefficiency of equilibria of the game based on both: a completely cooperative and non-cooperative approaches. On the other hand, we design two algorithms, CBAP and DBAP, that provide approximated solutions to the BAP game. We prove that both algorithms always terminate in a iv equilibrium configuration and we analyze their running time based on some approaches of cooperation. We performed experimental simulations to compare the overall quality of equilibria obtained by the proposed algorithms. Additionally, we design a self-stabilizing version of the algorithm DBAP, called DBAP-st, that works under the entirely noncooperative approach. This algorithm guarantees the re-establishment of equilibrium for the BAP game in a distributed system after any perturbation on it. | |
| CICESE | |
| 2011 | |
| Tesis de doctorado | |
| Español | |
| Fajardo Delgado, D.2011.Algoritmos auto-estabilizantes para sistemas basados en preferencias.Tesis de Maestría en Ciencias.Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California.152 pp. | |
| TECNOLOGÍA DE LOS ORDENADORES | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Tamaño | Formato | |
|---|---|---|---|
| 187891.pdf | 5.38 MB | Adobe PDF | Visualizar/Abrir |