Resumo: A principal característica de sistemas distribuídos é permitir que vários computadores, situados em diferentes localizações, trabalhem em conjunto para a realização de uma tarefa, possibilitando o compartilhamento de recursos e a distribuição dos serviços. No entanto, devido à dificuldade de se obter uma consistência global do sistema, o desenvolvimento de algoritmos distribuídos torna-se uma tarefa bastante complexa. Visando facilitar o controle, algoritmos distribuídos necessitam, muitas vezes, de um processador que exerça uma função diferenciada dos demais numa dada aplicação. Este processador é normalmente chamado de coordenador ou líder, e o problema de eleição de líder consiste em criar um algoritmo distribuído para uma dada rede de processadores tal que, ao terminar a execução deste algoritmo um, e apenas um, dos processadores seja designado líder. Esta dissertação apresenta um survey englobando as principais soluções para o problema de eleição de líder, analisando suas complexidades de mensagens e tempo e buscando uma classificação de modo a agrupar os algoritmos baseando-se no modelo do sistema e no princípio básico usado no desenvolvimento dos mesmos. Ver menos

Abstract: The main feature of a distributed system is to allow many computers, at different locations, to work together performing a common task, making the sharing of resources and the distribution of services possible. However, due to the difficulty of acquiring a global view of the system, the development of distributed algorithms is very complex. Several distributed applications make use of a distinguished processor to execute some special task. This processor generally is called coordinator or leader; the leader election problem consists of finding a distributed algorithm for a given network such that, at the end of the execution, only one processor has been declared leader. This dissertation presents, a survey of the main algorithms for the leader election problem, analyzing their message and time complexities and attempting to classify the algorithms according to the system model and the basic principle used in their development. Ver menos