Consenso e Coordenação
Consenso e coordenação abordam como processos independentes que se comunicam apenas por mensagens podem concordar em um valor ou ação comum, apesar de atrasos e falhas.
Definition
Consenso é o problema de um conjunto de processos, cada um propondo um valor, todos decidirem sobre um único valor comum, de modo que a decisão seja válida, todos os processos corretos concordem e todo processo correto eventualmente decida, mesmo quando alguns processos falham.
Scope
Esta área abrange o problema do consenso e suas variantes (acordo, transmissão atômica, validade, terminação), o resultado fundamental da impossibilidade FLP para consenso assíncrono determinístico, protocolos de consenso práticos como Paxos e Raft, acordo tolerante a falhas bizantinas e os problemas clássicos de coordenação de exclusão mútua e eleição de líder. É o núcleo teórico e prático da computação distribuída tolerante a falhas.
Sub-topics
Core questions
- Sob quais modelos de tempo e falha o consenso é solucionável e quando é comprovadamente impossível?
- Como os protocolos práticos contornam a impossibilidade FLP, preservando a segurança?
- Quanta replicação é necessária para tolerar falhas de travamento versus falhas bizantinas?
- Como os processos podem coordenar o acesso a recursos compartilhados ou eleger um líder de forma confiável?
Key theories
- Impossibilidade FLP
- Em um sistema totalmente assíncrono, nenhum protocolo determinístico pode garantir consenso se mesmo um único processo puder falhar, porque um processo lento não pode ser distinguido de um processo falho; este resultado motiva a sincronicidade parcial, a randomização e os detectores de falhas.
- Consenso baseado em quórum
- Protocolos como o Paxos alcançam o acordo exigindo que maiorias sobrepostas (quóruns) aceitem propostas, garantindo que quaisquer duas decisões se cruzem em um processo correto e, assim, permaneçam consistentes entre rodadas e mudanças de líder.
- Limites do acordo bizantino
- Para chegar a um acordo quando até f processos podem se comportar arbitrariamente, são necessários pelo menos 3f+1 processos no cenário síncrono clássico, um limite rigoroso que molda o design de todos os sistemas tolerantes a falhas bizantinas.
Clinical relevance
O consenso é a espinha dorsal da infraestrutura confiável: serviços de coordenação, bancos de dados replicados, bloqueios distribuídos e blockchains executam um protocolo de consenso para manter as réplicas consistentes, tornando esta área diretamente responsável pelas garantias de durabilidade e disponibilidade dos sistemas de nuvem modernos.
History
O artigo de 1982 sobre os generais bizantinos e o resultado da impossibilidade FLP de 1985 enquadraram os limites do acordo; o Paxos de Lamport (circulado em 1989, publicado em 1998) forneceu um protocolo prático assíncrono-seguro, e trabalhos posteriores sobre tolerância a falhas bizantinas e Raft tornaram o consenso robusto contra falhas maliciosas e acessível aos implementadores.
Debates
- A impossibilidade FLP torna o consenso inatingível na prática?
- A FLP exclui um protocolo determinístico que seja sempre seguro e ativo em um modelo totalmente assíncrono, mas sistemas práticos o contornam assumindo sincronicidade eventual ou usando randomização, mantendo a segurança incondicional e alcançando a vivacidade sempre que a rede se comporta.
Key figures
- Leslie Lamport
- Nancy Lynch
- Michael Fischer
- Michael Paterson
- Barbara Liskov
Related topics
Seminal works
- fischer1985
- lamport1998
- lamport1982byz
Frequently asked questions
- Por que o consenso é considerado o problema mais difícil em sistemas distribuídos?
- Porque muitas outras tarefas de coordenação — transmissão atômica, máquinas de estado replicadas, bloqueio distribuído — se reduzem ao consenso, e o próprio consenso é comprovadamente impossível de resolver deterministicamente no modelo de falha por travamento assíncrono, então qualquer solução deve fazer suposições cuidadosas de tempo ou aleatoriedade.
- Como o consenso se relaciona com bancos de dados replicados?
- Um banco de dados replicado mantém suas réplicas consistentes concordando com a ordem das operações, que é exatamente uma sequência de decisões de consenso; é por isso que sistemas como armazenamentos de chave-valor distribuídos incorporam um protocolo de consenso em seu núcleo.