Problema dos generais bizantinos

A alegoria apresenta vários generais do exército bizantino, separados geograficamente, que precisam decidir em conjunto se atacam ou recuam ao mesmo tempo. Eles só se comunicam por mensageiros, e alguns generais ou mensageiros podem ser traidores que espalham informações contraditórias. A pergunta é se os generais leais conseguem chegar a um acordo comum apesar dos traidores. O resultado teórico central: o consenso é alcançável se mais de dois terços dos participantes forem honestos, ou seja, o sistema tolera até f falhas bizantinas com n igual ou maior que 3f mais 1 nós.

O problema foi formalizado por Leslie Lamport, Robert Shostak e Marshall Pease no paper The Byzantine Generals Problem, publicado na ACM Transactions on Programming Languages and Systems (TOPLAS), volume 4, número 3, julho de 1982, páginas 382 a 401. Daí nasce o termo tolerância a falhas bizantinas (BFT). Com n igual a 3 e 1 traidor, o acordo é impossível usando apenas mensagens orais não assinadas; com mensagens assinadas, não falsificáveis, a tolerância melhora.

É o marco do qual deriva todo o campo BFT, já definido no glossário. O problema é a formulação, a tolerância a falhas bizantinas é a propriedade que o resolve, e pBFT, Tendermint ou HotStuff são implementações concretas. O PBFT (Castro e Liskov, 1999) foi a primeira solução prática eficiente; Tendermint e CometBFT, base do Cosmos, oferecem finalidade instantânea tolerando menos de um terço de validadores bizantinos. Satoshi Nakamoto resolveu uma variante sem permissão via prova de trabalho (Proof of Work) em 2008.