Problema de los generales bizantinos

La alegoría plantea a varios generales del ejército bizantino, separados geográficamente, que deben acordar atacar o retirarse a la vez. Solo se comunican por mensajeros y algunos generales o mensajeros pueden ser traidores que difunden información contradictoria. La pregunta es si los generales leales pueden llegar a un acuerdo común pese a los traidores. El resultado teórico clave: el consenso es alcanzable si más de dos tercios de los participantes son honestos, es decir, el sistema tolera hasta f fallos bizantinos con n igual o mayor que 3f más 1 nodos.

El problema lo formalizaron Leslie Lamport, Robert Shostak y Marshall Pease en el paper The Byzantine Generals Problem, publicado en ACM Transactions on Programming Languages and Systems (TOPLAS), volumen 4, número 3, julio de 1982, páginas 382 a 401. De ahí nace el término tolerancia a fallos bizantinos (BFT). Con n igual a 3 y 1 traidor, el acuerdo es imposible usando solo mensajes orales no firmados; con mensajes firmados, no falsificables, la tolerancia mejora.

Es el marco del que deriva todo el campo BFT, ya definido en el glosario. El problema es el planteamiento, la tolerancia a fallos bizantinos es la propiedad que lo resuelve y pBFT, Tendermint o HotStuff son implementaciones concretas. PBFT (Castro y Liskov, 1999) fue la primera solución práctica eficiente; Tendermint y CometBFT, base de Cosmos, ofrecen finalidad instantánea tolerando menos de un tercio de validadores bizantinos. Satoshi Nakamoto resolvió una variante sin permiso vía proof of work en 2008.