Wesley Schneider
#distributed systems#theorem#consensus

Teorema da Impossibilidade FLP

Foi proposto por Fischer, Lynch e Paterson em 1985. O acrônimo foi formado pelas iniciais dos autores.

O teorema estabelece que em um modelo assíncrono de sistemas distribuídos, onde pelo menos um processo pode falhar por crash, não há algoritmo de consenso determinístico que pode garantir terminação, acordo e validade ao mesmo tempo em todos cenários possíveis.

Async vs Sync

Em sistemas distribuídos assíncronos não há garantias de tempo, uma mensagem pode atrasar por um tempo indeterminado mas finito. Não é possível diferenciar se um sistema atrasou a mensagem por estar lento ou por estar falho. Um exemplo é a internet.

Já os sistemas distribuídos síncronos, possuem limites conhecidos para atrasos de mensagens. Por exemplo sistemas embarcados críticos.

O coração

As três propriedades do teorema são:

  • Terminação: Todos os processos não falhos eventualmente decidem um valor.
  • Acordo: Todos os processos concordam com um mesmo valor. Não pode haver dois valores possíveis.
  • Validade: O valor decidido deve ter sido proposto por um processo, deve existir e não ser viciado (um valor fixo, por exemplo).

A segurança/safety é formada por Acordo e Validade, que garante que o resultado de um consenso é correto. A vivacidade/liveness é formada pela Terminação, que garante que o consenso eventualmente produzirá um resultado.

Algoritmos

Existem diversos algoritmos de consenso para sistemas distribuídos assíncronos, os mais conhecidos são o Raft, Paxos e Zab. Irei explorar os três em próximo post.

Referências