(Este é o primeiro de uma série de textos sobre experimentos mentais interessantes - e também uma boa introdução à criptografia.)
Imaginem que exista uma cidade, em um vale, inimiga do Império Bizantino. O Imperador, desejoso de eliminar sua ameaça, destaca dois de seus melhores generais para sitiar e conquistar a cidade.
Os generais e seus respectivos exércitos, partindo de estradas opostas, acabam cada um acampando de um lado da cidade. Observando-a, concluem que, sozinhos, cada um deles não conseguiria vencer as defesas da cidade: seria imediatamente derrotado. Entretanto, em um ataque coordenado, com cada general assediando a cidade por um dos lados, a cidade cairia. Entretanto esse ataque deveria ser perfeitamente coordenado, iniciando simultaneamente.
Os generais, cientes da responsabilidade, então adotam o seguinte protocolo: atacarão, cada um, apenas quando estiver combinada a hora de ataque, e que esta combinação ocorrerá por meio de mensageiros, que, infelizmente, deverão chegar ao general do lado oposto passando por uma área que pode ou não estar sendo patrulhada pelo inimigo. Relembrando, o ataque só acontecerá se 1) os dois generais tiverem combinado a mesma hora e 2) um tiver certeza de que o outro recebeu e confirmou o recebimento do mensageiro.
Para simplificar o problema, vamos supor que a mensagem é cifrada (o inimigo capturar o mensageiro não implica em abandonar o plano) e que um dos generais é hierarquicamente superior, podendo decidir sozinho a hora do ataque.
É possível ocorrer tal combinação e confirmação?
O Problema
O senso comum daria este problema como facilmente contornável: bastaria que o general superior decidisse a hora, enviasse o mensageiro e este fosse recebido pelo segundo general. Simples, não?
Pois o problema é bem mais espinhoso, e ocorre de ser insolúvel: é impossível a combinação, por mais simples que possa parecer o procedimento. Demonstremos, primeiro, de um modo narrativo.
O primeiro general, utilizando sua prerrogativa hierárquica, decide um horário - digamos, 14:00 da terça-feira- e envia um mensageiro, portando um bilhete cifrado. No dia e hora que definiu atacará, mas se e somente se tiver confirmação que ambos estão cientes da data e horário.
O segundo general recebe a mensagem, e lê: 14:00 da terça-feira. Sabendo que o primeiro general precisa receber uma prova de que o segundo está ciente do combinado, despacha o mensageiro de volta com um bilhete onde se lê: "recebi a mensagem e estou ciente". Entretanto, sabendo que o primeiro general só atacará na certeza de que o segundo recebeu e está ciente, ordena ao mensageiro que, assim que entregar a mensagem, retorne com a confirmação de que o primeiro general está ciente da ciência do segundo.
O primeiro general recebe a confirmação, e mobiliza as tropas. Entretanto, sabe que o segundo general não sabe se recebeu confirmação de que recebeu a mensagem, e que suas tropas estarão paralisadas enquanto não receber a confirmação. Assim, paralisa suas próprias tropas e manda o mensageiro voltar, com o recibo.
O segundo general recebe esta notícia, e mobiliza suas tropas. Entretanto, sabendo que as tropas do outro devem estar paralizadas, ordena ao mensageiro que...
... bem, acredito que você já tenha entendido o problema.
Outra demonstração
A demonstração do problema é melhor colocada desta forma: se para a confirmação de uma determinada mensagem n for estritamente necessária a confirmação de uma mensagem n+1, é impossível se confirmar n, pois n+1 exigirá confirmação por n+2, que exigirá confirmação por n+3, e assim infinitamente.
Este foi o primeiro problema de computação a ser provado insolúvel - o que não quer dizer insuperável. O Problema dos Generais Bizantinos e sua prova de impossibilidade foi primeiro publicado por E. A. Akkoyunlu, K. Ekanadham, e R. V. Huber em 1975 em "Some Constraints and Trade-offs in the Design of Network Communications".