Impossibilidade para o problema dos generais bizantinos onde

7

Wiki: https://en.wikipedia.org/wiki/Byzantine_fault_tolerance


No artigo "Chegar a um acordo na presença de falhas", M. Pease et al. provou que não existe um protocolo (de algum tipo) para resolver o probleman3m, Onde n significa o número de generais e msignifica o número de traidores. A chave da prova disso é a impossibilidade do cason=3,m=1. No entanto, o método que eles usaram não parece uma prova teórica da informação. Assim, parece que o resultado deles não é "impossibilidade de protocolo arbitrário".


Minha pergunta: Existe uma prova baseada em teoria da informação para o cason=3,m=1? Mais formalmente, existe uma prova ou contra-exemplo para a proposição "não existe nenhum tipo de protocolo que resolva o problema dos generais bizantinos em quen=3,m=1"?


Nota: O protocolo típico SM(m) (funciona para arbitrário n,m) sugerido por L. Lamport et al. NÃO é um contra-exemplo adequado, porque precisa de um mecanismo de assinatura, que NÃO é perfeitamente confiável no sentido da teoria da informação, se assumirmos que os traidores têm recursos de computação infinito.

Lwins
fonte
11
O que é uma "prova baseada na teoria da informação"? Por que você espera que essa prova exista neste caso?
Yuval Filmus
Para @YuvalFilmus: Eu acho que (talvez seja uma crença falsa) a prova original da impossibilidade afirma que "não existe um protocolo em um determinado formulário para n3m", que é diferente de" não há protocolo para n3m". Portanto, estou buscando uma prova (ou contra-exemplo) para este último. Observe que o protocolo típico SM(m) (funciona para arbitrário n,m) sugerido por L. Lamport et al. NÃO é um contra-exemplo adequado, porque precisa de um mecanismo de assinatura, que NÃO é perfeitamente confiável no sentido da teoria da informação, se assumirmos que os traidores têm recursos de computação infinito.
Lwins
Então, o que você realmente está perguntando é: qual resultado é exatamente comprovado no artigo "Chegar a um acordo na presença de falhas". Presumivelmente, isso é explicado no artigo.
Yuval Filmus
Para @YuvalFilmus: Provavelmente não. Como mencionei acima, estou buscando uma prova (ou contra-exemplo) para a proposição "não há protocolo paran3m".
Lwins

Respostas:

3

No modelo síncrono de comunicação, existem nagentes que compartilham um relógio. Em cada rodada de comunicação, cada agente envia uma mensagem arbitrária para o outro agente e, em seguida, recebe a mensagem enviada por todos os outros agentes.

Um protocolo para acordo bizantino sobre n agentes de apoio m agentes bizantinos é um protocolo de comunicação para os agentes que satisfazem as seguintes propriedades:

  • Cada agente recebe um bit de entrada.
  • Todos os agentes começam a falar no horário 0.
  • Existem no máximo m agentes bizantinos, cujo comportamento é arbitrário.
  • Os outros agentes seguem o protocolo.
  • O protocolo sempre termina (isso significa que os agentes não bizantinos sempre atingem um estado "final" especial do protocolo e param de falar para sempre), com um valor de retorno que também é um pouco.
  • Todos os valores de retorno devem concordar (observe que isso se aplica apenas aos agentes não bizantinos).
  • Se todos os bits de entrada forem iguais, os valores de retorno deverão ser o mesmo bit.

O resultado da impossibilidade afirma que esse protocolo existe se e somente se n>3m.

Há um modelo diferente no qual um agente pode assinar uma mensagem e essa assinatura não pode ser violada. Neste modelo (que não especificarei formalmente), o problema pode ser resolvido para qualquern,m.

Uma das dificuldades na área de sistemas distribuídos é a natureza complicada do modelo de computação. Se você deseja entender o significado dos resultados da impossibilidade, deve familiarizar-se com esses modelos em todos os detalhes (ainda mais detalhes do que o tratamento informal nesta resposta).

Yuval Filmus
fonte
Obrigado pela explicação do paciente :) E tenho a última pergunta: como encontrar a prova da impossibilidade no modelo de comunicação síncrona? A prova em papel "Chegar a um acordo na presença de falhas" parece não ser a única. Você poderia sugerir alguma literatura (digamos, papel ou livro) altamente relacionada ao modelo de comunicação com os nós bizantinos?
Lwins
Estou ciente de apenas uma prova, e é a única no papel. Para a mesma prova em um modelo um pouco diferente, consulte as notas da aula de Chiu Yuen Koo .
Yuval Filmus
Aqui é um livro: Attiya e Welch, computação distribuída: Fundamentos, Tópicos Simulações, e avançado, segunda edição, Wiley, 2004.
Yuval Filmus