Home Anel Bully

Algoritmo em Anel

Na computação distribuída, muitas vezes é necessária a escolha de um processo específico para coordenar tarefas ou desempenhar alguma função em particular. Os algoritmos usados para escolher um coordenador são conhecidos como algoritmos de eleição de líder. Nesses algoritmos, muitas vezes não importa qual o processo é escolhido como líder, desde que alguém seja eleito. Contudo, todos os processos participantes devem concordar com a escolha do novo líder.

Exemplos de aplicações distribuídas que usam eleição de líder:

Servidores que usam replicação passiva (Harp);
Processo sequenciador em algoritmos de comunicação multicast (Amoeba).

Algoritmos típicos para eleição de líder consideram uma . Seja P, o conjunto de processos P_i, com 0 ≤ i < n, onde n é o número de processos participantes da computação, até n eleições podem ser realizadas de forma concorrente, desde que somente um líder seja eleito e cada processo inicie somente uma eleição por vez. A qualquer momento, um determinado processo pode ser considerado um ou um , indicando se o processo está participando, ou não, de uma execução do algoritmo de eleição. Na imagem abaixo, inicialmente todos os processos são não-participantes. Ao clicar em um processo, ele passa a ser participante. Para visualizar, passe o mouse em cima das caixas de texto.

O Algortimo em Anel é um dos algoritmos clássicos para eleição de líder em sistemas distribuídos. Esse algoritmo realiza a eleição considerando uma rede de sobreposição em anel, o que significa que os processos se comunicam ao redor de um anel no sentido horário. Para esse algoritmo, é considerado que cada processo tenha uma espécie de "força", ou seja, um identificador (ID), onde o processo que possui a maior "força" (identificador) dentre todos os processos que não estejam em estado de falha pode ser eleito o líder. Para esses casos, será considerado que os processos tenham "forças" distintas.

No algoritmo de eleição de líder em anel, cada processo mantém comunicação somente com seus vizinhos à esquerda e à direita, sendo que os vizinhos de P_k são, respectivamente, P_k-1 e P_k+1. Como a comunicação se dá no sentido horário, P_k recebe mensagens de P_k-1 e envia mensagens para P_k+1 anexando seu ID ("força") à cada mensagem enviada. P_k anexa à mensagem seu ID_k e envia a mensagem para P_k+1.

Durante a execução do algoritmo baseado em anel, os nós podem estar em uma de três possibilidades (um, entre três estados possíveis):

Não-decidido: ainda não se decidiu;
Líder: ele é o líder;
Não-líder: entende que não é o líder. Nesse caso, algum outro processo é o líder.

Inicialmente, todo nó está no estado não-decidido (indeciso). Quando ele decide, seu estado final será líder ou não-líder, sujeito a restrição que só pode existir exatamente um líder. Assumimos que cada nó tem uma "força" única. Isso torna o algoritmo trivial, já que é possível eleger um líder, por exemplo, com a maior "força".

Algoritmo de eleição de líder usando uma topologia lógica em anel, com a comunicação no sentido horário:

Apresentamos um algoritmo em anel simples, que é correto, pois elege um líder, com tempo O(n) e complexidade de mensagens de O(n²).

Cada nó executa:

Um processo P_i qualquer inicia o algoritmo enviando uma mensagem send (eleição, P_i. força_i) para o próximo processo P_j, onde P_j é P_{(i+1)mod n}. Nesse momento, ele entende que é líder, pois até o momento só conhece sua "força";
Ao receber uma mensagem (eleição, força_i), o processo P_j calcula o valor máximo entre o força_i e força_j, ou seja max(força_i, força_j);
- Se força_i > força_j, então P_j encaminha para seu vizinho força_i e decide que força_i é a "força" do processo líder e entende que ele é Não-Líder;
- Se força_i < força_j, então P_j encaminha para seu vizinho força_j e decide que ele é líder;
- Se P_j recebe sua própria "força", ele decider por ser o Líder.
O líder coloca em circulação uma mensagem send (eleito, ID), para que todos fiquem sabendo quem é o novo líder e o algoritmo termina quando esta mensagem retorna a ele.

A animação a seguir possui um conjunto de processos com valores de suas forças gerados aleatoriamente. Ao iniciar a animação o usuário pode acompanhar, passo a passo, o comportamento da escolha de um líder usando este algoritmo. Por conveniência escolheu-se iniciar a simulação do algoritmo sempre a partir de P₀. A cada passo, o processo P_i envia o valor de sua "força" para o vizinho P_{(i+1)mod n}.

Força

O usuário pode também interagir com o algoritmo aumentando ou diminuindo o número de processos ou a "força" de cada processo. Igualmente a simulação do algoritmo sempre se inicia a partir de P₀. A cada passo, o processo P_i envia o valor de sua "força" para o vizinho P_{(i+1)mod n}.

Força