Algoritmo Bully (Valentão)

O algoritmo de eleição de líder mais simples considera uma topologia lógica em anel, onde os processos se comunicam apenas com seus vizinhos no sentido horário. O algoritmo apresentado a seguir considera uma topologia como um grafo completo, onde todos os processos estão conectados e cada processo contem informações sobre os identificadores dos demais processos.

No algoritmo valentão (bully), quando um processo P_i percebe que o processo líder não responde mais à requisições de outros processos, ele inicia uma eleição. Como no algoritmo de eleição em anel, cada processo possui um identificador (ID) único, que funciona como sendo uma espécie de "força" que o processo possui, de modo que, aquele processo com a maior "força" pode ser considerado o líder em uma eleição.

Cada processo P_i contém, além de sua "força", uma lista de processos que possuem "forças" maiores que a dele. A ilustração a seguir demonstra a relação entre os processos considerando suas "forças".

Quando o processo P_i percebe que o atual líder não responde, ele executa o seguinte algoritmo:

• P_i envia uma mensagem para iniciar uma eleição para todos os processos com "forças" maiores que a dele.
• Se nenhum processo responder, P_i vence a eleição e se torna líder.
• Se algum processo P_k, com "força" superior à de P_i responde, P_k se torna líder e P_i termina seu trabalho de eleição.

Quando o processo P_k recebe uma mensagem de eleição de líder de algum processo P_i com menor "força", P_k responde a P_i uma mensagem de confirmação ("OK") para indicar que ele está "vivo" e que será o novo líder. P_k então realiza uma eleição, a menos que já esteja realizando uma. Eventualmente, todos os processos desistem, menos P_k, e esse é o novo líder. Assim, P_k envia uma mensagem ("COORDENADOR") a todos os processos informando que a partir de agora é o novo líder.

Se um processo P_j, que estava inativo, voltar, ele realiza uma nova eleição. Se acontecer de ser o processo de maior "força", P_j se tornará o novo líder. Nesse caso, o cara mais "forte" do bairro vence, daí o nome de algoritmo valentão.