Coordenação e Consenso

Exclusão mútua distribuída

Já fomos introduzidos 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$
• $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.

Problema do Consenso

O consenso é um dos problemas mais difíceis e estudados de Sistemas Distribuídos. Foi provado que, num sistema assíncrono em que podem ocorrer falhas, este problema não tem solução (resultado conhecido como FLP).

Podemos concluir assim três propriedades do Consenso:

1. Terminação: todos os processos correctos decidem ("alguma-vez")
2. Acordo uniforme: se dois processos decidem, decidem o mesmo valor
3. Integridade: o valor decidido (output) foi proposto por um processo

Quanto a soluções para este problema em sistemas:

• síncronos: ou seja, onde é possível concretizar um detetor de falhas perfeito, iremos abordar o algoritmo FloodSet
• assíncronos: ou seja, onde é possível concretizar um detetor de falhas "alguma-vez" perfeito, não iremos abordar nenhum algoritmo, mas podem consultar o algoritmo "Paxos" do Lamport

Floodset Consensus

A ideia essencial deste algoritmo é cada processo enviar para todos os outros o seu valor (input), de forma a que no fim todos conheçam todos os valores possíveis e possam tomar a mesma decisão de forma determinística.

O funcionamento do algoritmo é baseado em rondas:

• em cada ronda, cada processo faz broadcast do seu valor
• ao receber um valor de outro processo, adiciona-o ao seu conjunto
• ao fim de $f \op{+} 1$ rondas, é escolhido o output com base num critério determinístico utilizado por todos os processos
  • em que $f$ é o número de processos que pode falhar

Algumas notas acerca do algoritmo:

• Pressupõe um sistema síncrono
  • se um processo $p_i$ não recebe o valor de outro processo $p_j$ no turno $n$ então o processo $p_j$ falhou de certeza (e não participa nos próximos turnos)
• É possível adaptar o algoritmo de forma a utilizar um detetor de falhas perfeito:
  • Caso um processo $p_i$ não tenha recebido o valor de um processo $p_j$ num turno $n$, apenas avança para o turno $n \op{+} 1$ caso o detetor de falhas declare $p_j$ como falhado
• Em alguns casos, caso não ocorram falhas, é possível terminar em menos turnos

Problemas relacionados

Iremos agora abordar dois exemplos de problemas que são semelhantes ao problema do Consenso e que podem ser utilizados para o resolver ou utilizá-lo na construção da sua solução.

Coerência Interativa

O problema da coerência interativa é outra variante de consenso, na qual cada processo propõe um único valor. O objetivo do algoritmo é fazer com que os processos corretos concordem com um vetor de valores, um para cada processo. Por exemplo, o objetivo poderia ser para cada processo de um grupo obter a mesma informação sobre os estados respectivos (de cada processo).

• Conjunto de $N$ processos
• Cada processo $p_i$ propõe um valor ($\text{input}_i$)
• Todos os processo decidem o mesmo vetor $V$ ($\text{output}$)
• O vetor $V$ decidido tem uma entrada por cada processo em que:
  • ou $V[i] = \text{input}_i$
  • ou $V[i] = null$

Propriedades:

1. Terminação: todos os processos correctos decidem ("alguma-vez")
2. Acordo uniforme: se dois processos decidem, decidem o mesmo vetor $V$
3. Integridade: se o processo $p_i$ não falhar, $V[i] = \text{input}_i$

Quando Consenso.propoe(valor):
  CoerenciaInteractiva.propoe(valor)

Quando CoerenciaInteractiva.decide(vector):
  valor = primeiraEntradaDiferenteDeNull(vector);
  Consenso.decide(valor)

// este codigo é executado por todos os processos

fun PRONTO(vector):
  se para todo o p_x: p_x não pertence a falhados e tivermos vector_proposta[x] != null
    retorna VERDADEIRO
  caso contrário
    retorna FALSO

Init:
  falhados = {}
  para cada valor de i < N
    vector_proposta[i] = null;

Quando falha(p_x):
  falhados = falhados U {p_x}

Quando IC.propoe(valor_i)
  DifusaoFiavel.envia(p_i, valor_i)

Quando DifusaoFiavel.entrega(p_j, valor_j)
  vector_proposta[j] = valor_j;

Quando PRONTO(vector_proposta)
  Consenso.propoe(vector_proposta) // só propõe uma vez

Quando Consenso.decide(vector)
  IC.decide(vector)

Derivar Consenso a partir de Coerência Interativa

Por vezes é possível derivar uma solução para um problema utilizando uma solução para outro. Esta propriedade é muito útil porque aumenta a nossa compreensão dos problemas e economiza esforço de implementação.

Suponha que existem as seguintes soluções para o consenso (C) e para a consistência interativa (IC):

• $C_i(v_1, v_2, ..., v_N)$ retorna o valor de decisão do processo $p_i$ numa execução da solução para o problema do consenso, onde $v_1, v_2, ..., v_N$ são os valores propostos pelos processos
• ${IC}_i(v_1, v_2, ..., v_N)[j]$ retorna o j-ésimo valor no vetor de decisão do processo $p_i$ numa execução da solução para o problema da consistência interativa, onde $v_1, v_2, ..., v_N$ são os valores propostos pelos processos

Caso a maioria dos processos estejam corretos, construímos uma solução executando IC para produzir um vetor de valores em cada processo, e depois aplicando uma certa função sobre os valores do vetor para derivar um único valor:

Difusão com terminação

• Conjunto de $N$ processos
• Um processo pré-definido $s$ envia uma mensagem $m$
• Se o processo $s$ é correto, todos os processos corretos entregam $m$
• Se o processo $s$ falha, os processos entregam $m$ ou $null$
• Todos os processos corretos entregam o mesmo valor (ou $m$ ou $null$)

Propriedades:

1. Terminação: todos os processos correctos decidem ("alguma-vez")
2. Acordo uniforme: se dois processos decidem, decidem o mesmo valor $v$
3. Integridade: se o processo $s$ não falhar, $v = m$

Quando ConsensoPropoe(v) no processo i
  i.DifusaoComTerminacaoEnvia(v)

Para todo o i
  i.DifusaoComTerminacaoEntrega(v_i)

Escolhe v_final como sendo o menor v_i: v_i != null
  ConsensoDecide(v_final)

No emissor:
  Quando DifusaoComTerminacao(m)
    DifusaoFiavelEnvia(m)
    ConsensoPropoe(m)


No restantes processos, executa um e apenas um destes passos:
  Quando DifusaoFiavelEntrega(m)
    ConsensoPropoe(m)
  Quando suspeita a falha do processo "s"
    ConsensoPropoe(null)

Em todos os processos:
  Quando ConsensoDecide(v)
    DifusaoComTerminacaoEntrega(m)

Impossibilidade em sistemas assíncronos

As soluções para o consenso que abordámos assumem que o sistema é síncrono, ou seja, assumem que um processo falhou se não lhes enviou uma certa mensagem dentro da ronda desejada (atraso máximo excedido).

Fischer et al. [1985] provaram que nenhum algoritmo pode garantir alcançar o consenso num sistema assíncrono, visto que os processos podem responder a mensagens com latências arbitrárias, fazendo com que um processo que realmente falhou seja indistinguível de um lento.

Note que este resultado não significa que os processos não podem alcançar o consenso distribuído num sistema assíncrono. Este permite que o consenso possa ser alcançado com alguma probabilidade maior que zero, confirmando o que sabemos na prática (por exemplo, existem sistemas de transações assíncronos que têm alcançado o consenso regularmente há anos).

Ainda assim, existem diversas técnicas (não abordadas em aula) para contornar o resultado da impossibilidade. Por exemplo:

• Mascarar falhas: envolve técnicas como o uso de armazenamento persistente e replicação de componentes para ocultar falhas, permitindo que os processos continuem a funcionar corretamente
• Consenso usando detetores de falhas: envolve o uso de detetores de falhas (não perfeitos) em sistemas assíncronos para alcançar o consenso, seja considerando processos não responsivos como falhados ou permitindo que processos suspeitos continuem a participar no consenso
• Consenso usando randomização: envolve introduzir aleatoriedade no comportamento dos processos para neutralizar os efeitos negativos dos sistemas assíncronos, permitindo que o consenso seja alcançado em tempo (esperado) finito

Referências

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