Por que é determinado um limite para tolerância a falhas bizantinas de uma rede “assíncrona”?(onde não pode tolerar nem mesmo um nó defeituoso)

Question

Na resposta a seguir (LINK: https://bitcoin.stackexchange.com/a/58908/41513), foi demonstrado que para Acordo Bizantino Assíncrono:

"Não podemos tolerar 1/3 ou mais dos nós sendo desonestos ou perdemos a segurança ou a vensagem".

Para esta comprovação foram consideradas as seguintes condições/requisitos:

1. Nosso sistema é assíncrono.
2. Alguns participantes podem ser maliciosos.
3. Queremos segurança.
4. Queremos vivacidade.

Uma questão fundamental é que:

Considerando o conhecido artigo intitulado: "Impossibilidade de consenso distribuído com um processo defeituoso" (LINK: https://apps.dtic.mil/dtic/tr/fulltext/u2/a132503.pdf)

mostrando que:

nenhum protocolo de consenso completamente assíncrono pode tolerar até mesmo a morte não anunciada de um único processo,

Ainda podemos assumir que a rede é assíncrona?Como nesse caso, a rede não pode tolerar nem mesmo um nó com defeito.

Answer 1

A resposta tem a ver com rastrear as suposições precisas feitas nesses diferentes resultados.Em suma, embora ambos os resultados assumam assincronia, a “impossibilidade de consenso distribuído com um processo defeituoso” requer uma forma mais forte de vivacidade e determinismo, e isso torna o consenso impossível.

1.Impossibilidade de consenso distribuído com um processo defeituoso

Este resultado seminal (de Michael Fischer, Nancy Lynch e Michael Paterson) trata do consenso distribuído onde o sistema não é apenas assíncrono, mas também satisfaz:

• Determinismo. O algoritmo de consenso não usa nenhuma aleatoriedade.

• Atividade sob atrasos de mensagens. Não só as mensagens podem ser atrasadas arbitrariamente, mas também devemos garantir a vivacidade mesmo na presença de tais atrasos contínuos.

Vejamos por que essas propriedades são fortes demais e tornam impossível o consenso distribuído.

Considere um exemplo:Alice, Bob e Charlie são amigos e querem decidir onde jantar.É possível que um deles saia sem permissão inesperadamente (ou decida que não tem mais interesse em ser amigos) e pare de responder às mensagens.Nesse caso, os outros dois ainda podem decidir o local do encontro.Agora, o que eles deveriam fazer?

A abordagem óbvia seria esta:

Alice apenas decide para onde ir e conta a Bob e Charlie.

Mas isso não funciona porque Alice pode ser quem desaparece.Então, para corrigir isso, a próxima abordagem mais óbvia pode ser:

Alice e Bob dizem a todos para onde ir.Se todos tiverem notícias de Alice, então irão para onde Alice disser;caso contrário, eles irão para onde Bob diz.

Mas isso tem um novo problema.Suponha que você seja Charlie.Se você tiver notícias de Alice, você sabe para onde ir.Se você não tiver notícias de nenhum deles, espere para ouvir.O problema é quando você ouviu falar de Bob, mas não de Alice.Como existem atrasos arbitrários nas mensagens, você não pode se comprometer a ir aonde Bob disse:Alice pode ter dito para onde ir e você ainda não recebeu!Então você está completamente preso, e se acontecer de Alice desaparecer, você continuará esperando para sempre.

O problema aqui é que não temos como abortar a transação;Não há como dizer: "OK, isso não está funcionando, já faz muito tempo e eu não recebi um atraso - vamos tentar novamente". Os algoritmos de consenso do mundo real (os mais conhecidos são paxos) têm a possibilidade de que as rodadas falhem devido a atrasos na rede e, nesse caso, eles apenas tentam novamente, esperando atrasos mais curtos na rede.Além disso, é possível contornar o problema utilizando protocolos randomizados que geralmente funcionam e só duram para sempre com probabilidade pequena (ou até zero).

2.Acordo Bizantino Assíncrono onde menos de $1/3$ dos nós falham

A postagem do bitcoinSE que você vincula encobre a questão da vivacidade, dizendo apenas que é “a capacidade de continuar a progredir”.Na verdade, o resultado acima mostra que a forma mais forte disso é impossível, então temos que relaxar nossos requisitos/suposições.

Vamos considerar dois exemplos.Em "Practical Byzantine Fault Tolerance" de Miguel Castro e Barbara Liskov, eles alcançam vivacidade prática com menos de um terço dos nós sendo defeituosos por assumindo que os atrasos nas mensagens não continuam a crescer indefinidamente.Como afirmam os autores:

Garantimos que os clientes, ou seja, os clientes eventualmente recebem respostas aos seus pedidos, desde que o máximo $\frac{n-1}{3}$ réplicas estão com defeito e $atraso(t)$ não cresce mais rápido do que $t$ indefinidamente ... Esta é uma suposição de sincronia bastante fraca que provavelmente será verdadeira em qualquer sistema real, desde que as falhas de rede sejam reparadas, mas nos permite contornar o resultado da impossibilidade em [9].

Aqui [9] está o resultado de impossibilidade discutido acima.Em termos simples, para o nosso exemplo, eles evitam o problema acima com Charlie, exigindo uma forma fraca de sincronia:Charlie não precisa simplesmente ficar esperando para sempre, pois sabemos que os atrasos nas mensagens só podem aumentar temporariamente, e não indefinidamente.(É claro que o algoritmo real fica muito mais complexo, mas essa é, em parte, a ideia conceitual de por que a vivacidade é possível.)

Em "Acordo Bizantino Assíncrono Rápido com Resiliência Ideal" de Ran Canetti e Tal Rabin, eles usam a aleatoriedade para obter vivacidade com menos de $n/3$ Falhas no nó bizantino.Do artigo deles:

Neste cenário, descrevemos um $(\lceil\frac{n}{3} ceil- 1)$- protocolo resiliente do Acordo Bizantino.Com probabilidade esmagadora, todos os jogadores não atacados completam a execução do protocolo.Condicionado ao evento em que todos os players não atacados concluíram a execução do protocolo, eles o fazem em constante tempo esperado.

Aqui $(\lceil\frac{n}{3} ceil- 1)$-resiliente significa apenas que menos de um terço dos nós são bizantinos.Observe as palavras-chave com uma probabilidade esmagadora. Portanto, eles têm um algoritmo probabilístico que possui muitas "execuções" possíveis, e a esmagadora maioria delas funciona.Observe que o resultado de impossibilidade acima implica que sempre deve haver alguns é executado onde a vivacidade não ocorre, ou seja,não há consenso:

O resultado seminal de impossibilidade de Fischer, Lynch e Paterson [FLP] para protocolos determinísticos implica que qualquer protocolo (randomizado) que chegue a BA deve ter execuções não-terminais.