Coordenação e Consenso

Exclusão mútua distribuída

Já fomos introduzido ao problema da exclusão mútua em Sistemas Operativos (SO), que tem como objetivo garantir que dois processos/threads não acedem concorrentemente ao mesmo recurso (ex: ficheiro, bloco de memória, ...), uma vez que tal pode causar incoerências (ao tentarmos ler e escrever no mesmo espaço por ex.).

Em Sistemas Distríbuidos existe o mesmo problema: é necessário coordenar os processos de forma a garantir que não acedem simultaneamente ao mesmo recurso, mas com a diferença de que agora a exclusão mútua é distribuída, baseando-se na troca de mensagens.

Algoritmos de exclusão mútua

Consideramos um sistema de $N$ processos $p_i, i = 1, 2, ..., N$, que não partilham variáveis. Os processos acedem a recursos comuns, mas fazem-no numa secção crítica.

Os requisitos essenciais para exclusão mútua são:

• ME1 (safety): apenas um processo pode estar na secção crítica
• ME2 (liveness): os pedidos para entrar e sair da secção crítica eventualmente são bem sucedidos (esta condição previne deadlocks e starvation)
• ME3 (happened-before ordering): se um pedido para entrar na secção crítica ocorreu antes de outro, então a entrada é concedida nessa ordem.

Algoritmo do servidor central

Esta é a forma mais simples de alcançar a exclusão mútua, utilizando um servidor que concede permissão para entrar na secção crítica.

Para entrar na secção crítica, um processo envia um pedido ao servidor e aguarda uma resposta deste. Conceptualmente, a resposta é uma chave que significa permissão para entrar na secção crítica. Se nenhum outro processo tiver a chave, então o servidor responde imediatamente, concedendo a chave. Se a chave estiver detida por outro processo, então o servidor não responde, mas coloca o pedido numa fila de espera. Quando um processo sai da secção crítica, envia uma mensagem ao servidor, devolvendo-lhe a chave.

Desvantagens:

• Pode existir sobrecarga do servidor.
• Se o servidor falhar, o sistema fica bloqueado.
• É necessário entregar a "chave" ao servidor para que este depois a passe a outro cliente (entregar diretamente ao próximo cliente seria muito mais eficiente)

Devemos assim tentar implementar uma solução descentralizada!

Algoritmo baseado em anel

Uma das formas mais simples de estabelecer exclusão mútua entre $N$ processos sem utilizar um processo adicional é organizá-los num anel lógico. Isto apenas requer que cada processo $p_i$ tenha um canal de comunicação com o próximo processo no anel, $p_{(i+1) \op{mod} N}$.

A ideia é que a exclusão mútua é concebida passando a chave de processo para processo numa única direção (por exemplo, no sentido horário) ao redor do anel. Se um processo não precisa de entrar na secção crítica quando recebe a chave, encaminha-a para o seu vizinho. Um processo que precise da chave espera até recebê-la (e retém-a após receber). Para sair da secção crítica, o processo encaminha a chave para o seu vizinho.

Algoritmo de Ricart and Agrawala

Este algoritmo utiliza 3 estados:

• HELD: significa que temos acesso exclusivo à região crítica
• WANTED: não temos acesso mas queremos obtê-lo
• RELEASED: não precisamos de aceder à região crítica

Se um processo deseja aceder à região, deve enviar requests a todos os outros clientes e esperar obter "OK" de todos estes. Se todos responderem afirmativamente, o processo recebe acesso exclusivo à região.

On initialization
  state := RELEASED;

To enter the section
  state := WANTED;
  Multicast request to all processes; // É omitido o processamento dos requests
  T := request’s timestamp;
  Wait until (number of replies received = (N – 1)); // Espera receber N-1 OK's
  state := HELD; // Temos acesso

On receipt of a request <T_i, p_i> at p_j (i != j)
  // Se (já temos acesso) ou (queremos ter e enviámos o pedido há mais tempo),
  // colocamos os pedidos em espera
  if (state = HELD or (state = WANTED and (T, p_j) < (T_i, p_i)))
  then
      queue request from p_i without replying;
  else
      reply immediately to p_i;
  end if

To exit the critical section
  state := RELEASED;
  reply to any queued requests;

Este algoritmo já permite que a "chave" seja passada diretamente para outro cliente, mas tem 2 problemas:

• Não é tolerante a faltas
• Em vez de sobrecarregar o servidor, sobrecarrega todos os processos!

Algoritmo de Maekawa

Maekawa observou que, para um processo entrar numa secção crítica, não é necessário que todos os seus peers concedam o acesso (só precisa de obter permissão de um subconjunto destes).

Este algoritmo associa um voting set $V_i$ (também chamados quóruns) a cada processo $p_i$ $(i = 1,2,...,N)$, onde $V_i \subseteq \{p_1, p_2, ..., p_N\}$. Os sets $V_i$ são escolhidos de forma a que, para todo $i,j = 1,2,...,N$:

• $p_i \in V_i$ (atenção que um processo pode pertencer a mais que um voting set)
• $V_i \cap V_j \neq \varnothing$ – há pelo menos um membro comum entre quaisquer dois voting sets
• $|V_i| = K$ – de forma a ser justo, todos os voting sets têm o mesmo tamanho
• Cada processo $p_j$ está contido em $M$ dos voting sets $V_i$

Cada processo pode votar num pedido de acesso à região crítica, mas não pode votar em mais que um em simultâneo, o que origina a seguinte propriedade:

K = |V_i| ~ sqrt(N)
On initialization
  state := RELEASED;
  voted := FALSE;

For p_i to enter the critical section
  state := WANTED;
  Multicast request to all processes in V_i;
  Wait until (number of replies received = K);
  state := HELD;

On receipt of a request from p_i at p_j
  if (state = HELD or voted = TRUE)
  then
    queue request from p_i without replying;
  else
    send reply to p_i;
    voted := TRUE;
  end if

For p_i to exit the critical section
  state := RELEASED;
  Multicast release to all processes in V_i;

On receipt of a release from p_i at p_j
  if (queue of requests is non-empty)
  then
    remove head of queue – from p_k, say;
    send reply to p_k;
    voted := TRUE;
  else
    voted := FALSE;
  end if

Este algoritmo consegue distribuir a carga, ou seja, não existe um processo que recebe todos os pedidos, mas tem um grande problema: sofre de interbloqueio (deadlock-prone).

Comparação dos algoritmos

Terminologia:

• Bandwith usage : total de mensagens trocadas entre enter /exit por um mesmo cliente
• Client delay : tempo para um processo entrar numa secção crítica livre
• Synchronization delay : tempo entre exit por um processo e enter por outro que estava à espera

* assumindo que os 2 quóruns se intercetam em apenas 1 processo

Distribuição de carga:

• Centralizado: tudo passa pelo servidor, possível sobrecarga
• Ricart and Agrawala: todos os processos são sobrecarregados
• Maekawa: cada pedido apenas afeta um subconjunto de processos (quórum)

Tolerância a falhas:

• Todos assumem rede fiável! Nenhum tolera perdas de mensagens
• Centralizado: não tolera falha do servidor, mas tolera falha de cliente em estado RELEASED
• Ricart and Agrawala: nenhum processo pode falhar
• Maekawa: cada pedido tolera falhas dos processo que não estejam no quórum

Eleição de líder

Tal como vimos anteriormente, muitos algoritmos distribuídos precisam de atribuir cargos especiais a certos processos. Por exemplo, na variante "servidor central" dos algoritmos para exclusão mútua, o servidor é escolhido entre os processos que precisam de utilizar a secção crítica. É necessário um algoritmo de eleição para esta escolha, sendo essencial que todos os processos concordem com a mesma.

É necessário assegurar principalmente 2 propriedades:

• E1 (safety): todos os processos escolhem o mesmo líder (tipicamente o processo com id maior)
• E2 (liveness): a execução do algoritmo é finita

Ao longo deste capítulo, iremos assumir que:

• O detetor de falhas é perfeito, ou seja, nunca diagnostica erradamente um processo como morto
• Os processos não recuperam, ou seja, não voltam ao ativo depois de morrerem

Eleição em anel

Este algoritmo é adequado para um conjunto de processos organizados num anel lógico. Cada processo $p_i$ tem um canal de comunicação com o próximo processo no anel, $p_{(i + 1) \op{mod} N}$, e todas as mensagens são enviadas no sentido horário ao redor do anel.

Funcionamento do algoritmo

Quando um processo p decide iniciar uma eleição:

• Marca-se como participante
• Prepara uma mensagem election(id(p)) e envia-a para o próximo anel

Quando um processo p recebe uma mensagem election(id):

• Se o id na mensagem é superior ao identificador local: p reencaminha-a ao próximo e marca-se como participante.
• Se o id na mensagem é inferior e p ainda não participava: substitui o id na mensagem pelo de p, reencaminha-a ao próximo e marca-se como participante.
• Se o id na mensagem é o de p, então p torna-se o novo líder! Marca-se como não participante e envia mensagem elected(id(p)) ao próximo no anel.

Quando um processo p recebe uma mensagem elected(id):

• Aprende que o novo líder é aquele indicado na mensagem, reencaminha a mensagem e marca-se como não participante.
• Se o id na mensagem for p, não faz nada (o algoritmo terminou).

No caso em que apenas um processo dá início ao processo de eleição, podem ser geradas até $\bold{3N - 1}$ mensagens.

Eleição em anel por torneio

• Os processos procuram um líder num horizonte que duplica em cada turno
• Em cada turno o número de competidores vai sendo reduzido para metade
• Isto resulta na execução de $\log(n)$ turnos para uma complexidade total de $n\log(n)$

Algoritmo "Bully"

O objetivo deste algoritmo é, tal como anteriormente, eleger o processo com maior identificador.

Tem alguns pressupostos:

• existem tempos máximos conhecidos para a comunicação (sistema síncrono; canais fiáveis)
• os processos podem falhar
• todos os processos conhecem os identificadores dos restantes

Existem 3 tipos de mensagens trocadas neste algoritmo:

• election: que assinala o início de uma eleição
• answer: serve de resposta a uma mensagem election
• coordinator: assinala o id do processo elegido (o novo coordenador)

Funcionamento do algoritmo

Um processo inicia uma eleição quando se apercebe, através de timeouts, que o coordenador falhou (vários processos podem descobrir isto simultaneamente):

• se for o processo com id mais alto:
  • elege-se a si próprio e envia uma coordinator message para todos os processos com id mais baixo
• se não:
  • envia a todos os processos com ids mais altos uma election message:
    • se não receber nenhuma answer message, considera-se o coordenador e envia uma coordinator message a todos os processos com id mais baixo
    • se receber, espera durante um período de tempo por uma mensagem coordinator e caso não receba nenhuma, começa uma nova eleição

Quando um processo $p_i$ receber uma coordinator message:

• regista o id recebido na mensagem e passa a tratar esse processo como coordenador

Quando um processo recebe uma election message:

• envia de volta uma answer message
• começa uma nova eleição (a não ser que já tenha começado uma)

Quando um novo processo vem substituir um outro crashed:

• começa uma nova eleição:
  • se tiver o id mais alto: decide que é o líder e anuncia-o (mesmo que o atual líder esteja a funcionar, daí ser chamado bully)

No melhor caso, o processo com o segundo maior identificador percebe a falha do coordenador e elege-se imediatamente, e envia $N - 2$ mensagens coordinator.

No pior caso, o processo com o identificador mais baixo é o primeiro a detetar a falha do coordenador. Assim, $N - 1$ processos iniciam eleições simultaneamente, cada um enviando mensagens para os processos com identificadores mais altos. Desta forma, o algoritmo requer $O(N^{2})$ mensagens.

Algoritmo do "Luís"

O professor desenhou um algoritmo bastante simples, que consiste em ter um detetor de falhas que notifica todos os processos sempre que algum falha:

• Inicialização:

  • $ativos = {p_0, p_1, p_2, ..., p_n}$
  • $líder = max_{id}(ativos)$
  • $output(líder)$

• Quando um processo ($p_i$) falha:

  • $ativos = ativos \setminus \{~p_i~\}$
  • $líder = max_{id}(ativos)$
  • $output(líder)$

Bully vs "Luís":

Algoritmo do Luís:

• simples
• modular
• menos eficiente pois obriga a detetar falhas em processos que não são candidatos a líder

Algoritmo Bully:

• Mistura deteção de falhas com eleição de líder
• Cada processo apenas precisa de detetar falhas de outros com id maior

Deteção de falhas

Todos estes algoritmos têm um grande problema: assumem que a deteção de falhas é perfeita. Só assim conseguem garantir que todos os nós funcionais elegem o mesmo líder (ou seja, garantir a safety do algoritmo).

Uma deteção de falhas perfeita implica que:

• um processo funcional nunca é diagnosticado como falhado
• a falha é sempre detetada

Mas para se fornecer tais garantias é preciso que:

• o sistema seja síncrono, para que se possa detetar as falhas com exatidão com recurso a temporizadores
• não hajam falhas na rede

Por outro lado, se a deteção de falhas não for perfeita:

• os processos podem discordar sobre a identidade do líder
• podem existir vários líderes ao mesmo tempo

O ideal seria construirmos algoritmos que são tolerantes a falhas, de forma a não dependerem de uma deteção perfeita.

Referências

• Coulouris et al - Distributed Systems: Concepts and Design (5th Edition)
  • Secções 15.1, 15.2 e 15.3
• Departamento de Engenharia Informática - Slides de Sistemas Distribuídos (2023/2024)
  • SlidesTagus-Aula03a
  • SlidesTagus-Aula04