Impossibilidade para o problema dos generais bizantinos onde

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 problema$n \leq 3m$, Onde $n$ significa o número de generais e $m$significa o número de traidores. A chave da prova disso é a impossibilidade do caso$n=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 caso$n=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 que$n=3,m=1$"?

Nota: O protocolo típico $\mathrm{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.

No modelo síncrono de comunicação, existem $n$agentes 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 qualquer$n,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).