Eleição de líder

Eleição de líder é um problema da área de sistemas distribuídos que busca selecionar de forma consensual um processo num conjunto de processos tendo como objetivo selecionar um líder para uma determinada tarefa. A eleição torna-se necessária quando o sistema distribuído está sendo iniciado pela primeira vez ou o líder anterior não consegue se comunicar com os demais processos pela ocorrência de alguma falha. Há vários algoritmos que realizam a eleição do líder, cada um específico a alguma situação.

Algoritmo em anel

O algoritmo em anel ou LCR, iniciais de Le Lann, Chang e Roberts, serve para eleger um líder se os processos estiverem dispostos em um anel. Cada processo deve conhecer seu vizinho à direita e à esquerda e deve ter um identificador numérico, único, fixo e atribuído antes do início da eleição. Originalmente este algoritmo visava a recuperação de um token perdido em uma rede com topologia em forma de anel, elegendo um nó da rede que servisse como ponto de partida para o novo token.

A execução do algoritmo busca eleger o processo de maior identificador e fazer com que todos os membros do anel reconheçam o novo líder. Este é o seu pseudocódigo:

• Se um dos nós identifica a perda do token, inicia a eleição enviando uma mensagem de eleição com o seu número de nó ao vizinho da direita.
• Se o nó que recebe a mensagem de eleição tem um identificador maior que o informado na mensagem que recebeu, passa uma mensagem de eleição para seu vizinho da direita com seu próprio identificador. Caso contrário aceita que o nó que tem o identificador contido na mensagem será o líder e repassa ao seu vizinho da direita.
• Se o nó recebe uma mensagem com o identificador idêntico ao seu, ele se declara líder. Este evento só ocorre quando a mensagem contendo o maior identificador circulou por todo o anel tornando todos os seus membros cientes do resultado.

Algoritmo de bully

O algoritmo de bully serve para eleger um líder entre processos identificados por um identificador numérico, único, fixo e atribuído antes do início da eleição. Entretanto neste caso a topologia não é limitada a um anel e cada um dos processos pode se comunicar com qualquer outro no sistema. Novamente a execução do algoritmo busca eleger o processo de maior identificador e fazer com que todos reconheçam o novo líder. Este é o seu pseudocódigo:

• Se um dos processos identifica a perda de contato com o líder, inicia uma nova eleição enviando a todos os outros uma mensagem contendo seu identificador.
• Todos os nós respondem ao processo que iniciou a eleição com os seus próprios identificadores.
• Se o processo que iniciou a eleição verifica possuir o maior identificador entre todos os outros, proclama-se líder e avisa todos os outros. Senão aguarda que o processo de maior identificador inicie uma eleição e se torne líder.

Este algoritmo possui este nome justamente por seu comportamento de bully. O processo de maior identificador predomina sobre os de menor número e mesmo que um destes ganhe uma eleição, rapidamente toma o posto do eleito propondo uma nova eleição.

Ver também

• Sistemas distribuídos