Eleição de líder

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Este artigo não cita fontes confiáveis e independentes (desde julho de 2013). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)

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 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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

Ícone de esboço Este artigo sobre Informática é um esboço. Você pode ajudar a Wikipédia expandindo-o.