Bizancio, la capital del antiguo Imperio Romano de Oriente, fue una de las ciudades más poderosas y ricas del mundo. Sin embargo, debido a su vasto territorio, Bizancio a menudo enfrentaba invasiones externas y rebeliones internas. Para defender sus fronteras, Bizancio enviaba múltiples ejércitos, cada uno comandado por diferentes generales. Lograr consenso entre estos generales se convirtió en un desafío significativo.
El Problema de los Generales Bizantinos tiene una estrecha relación con la cadena de bloques. Una red de cadena de bloques es una red distribuida donde los nodos, al igual que los generales bizantinos, deben lograr consenso sobre transacciones y datos en un entorno de red no confiable.

Problema de los dos generales

El Problema de los Dos Generales es un caso especial del Problema de los generales bizantinos. El problema y su prueba de irresolubilidad fueron propuestos por primera vez por E.A. Akkoyunlu, K.Ekanadham y R.V. Huber en su artículo de 1975 “Some Constraints and Trade-offs In The Design of Network Communications.” En 1978, Jim Gray nombró formalmente este problema como el “Problema de los Dos Generales” en su libro “Notes on Data Base Operating Systems.” Originalmente, se utilizaba para analizar los problemas de lograr consenso a través de la comunicación en un enlace de comunicación no confiable. Ahora se utiliza comúnmente para ilustrar problemas de consistencia y consenso en sistemas distribuidos.

Definición del problema:
Dos ejércitos del país A, cada uno liderado por un general, se preparan para atacar a un ejército del país B. El ejército del país B está rodeado en un valle, con los dos ejércitos de A estacionados en las colinas a cada lado del valle. Sin embargo, el único camino entre los dos ejércitos de A pasa por el valle. El ejército de B es más fuerte que cualquiera de los ejércitos de A individualmente, pero si ambos ejércitos de A atacan juntos, pueden derrotar al ejército de B.
Problema: ¿Se puede diseñar un algoritmo que permita a los dos generales de los ejércitos de A ponerse de acuerdo en un ataque simultáneo? El algoritmo puede incluir el envío y recepción de mensajes.
Solución: El clásico problema de los dos generales es irresoluble. No existe ningún protocolo que pueda garantizar que los dos ejércitos de A coordinen con éxito su ataque. Sin embargo, en los sistemas prácticos, los problemas se pueden abordar de manera relativamente confiable, como con el mecanismo de "protocolo de enlace de tres vías" en el protocolo TCP.

Problema de los generales bizantinos

El Problema de los generales bizantinos fue propuesto por primera vez por Leslie Lamport, un ganador del Premio Turing 2013, en su artículo de 1982 “El Problema de los generales bizantinos”. El problema describe cómo lograr consistencia en sistemas distribuidos en presencia de comportamientos maliciosos, como la manipulación de mensajes.
Varias armadas del Imperio Bizantino rodean una ciudad enemiga, cada una liderada por un general. Las armadas bizantinas solo podían comunicarse a través de mensajeros. Después de observar las fuerzas enemigas, los generales bizantinos deben llegar a la misma conclusión: solo si más de la mitad de las armadas bizantinas atacan juntas pueden capturar la ciudad y lograr la victoria.

Solución: Si el número de generales (nodos) en un sistema bizantino es Z y el número de generales no confiables (traidores) es X, entonces solo cuando Z ≥ 3X + 1 puede un protocolo de tolerancia a fallas bizantinas (BFT) garantizar la consistencia del sistema.
En sistemas prácticos, las fallas que causan que los nodos no respondan se clasifican como 'Fallas por bloqueo', mientras que los nodos que falsifican o manipulan mensajes se clasifican como 'Fallas bizantinas'.

Clasificación del algoritmo de consenso

Los sistemas blockchain son un tipo de sistema distribuido, especialmente cadenas públicas como Bitcoin y Ethereum, que consisten en numerosos nodos de red altamente descentralizados y mutuamente desconfiados. El mecanismo de consenso blockchain garantiza que el sistema blockchain logre consistentemente la consistencia de datos sin bifurcaciones.
Basándose en el tipo de tolerancia a fallas, los algoritmos de consenso se pueden clasificar en algoritmos de Tolerancia a Fallas no Bizantinas (CFT) y algoritmos de Tolerancia a Fallas Bizantinas (BFT).

Algoritmos de Tolerancia a Fallas No Bizantinas

En sistemas distribuidos, los algoritmos de Tolerancia a Fallas no Bizantinas garantizan la confiabilidad de todo el sistema distribuido cuando los nodos experimentan fallas del sistema o interrupciones no planificadas (fallas no bizantinas). Sin embargo, cuando los nodos maliciosos falsifican o manipulan datos, los algoritmos de Tolerancia a Fallas no Bizantinas no pueden garantizar la confiabilidad del sistema. Estos algoritmos se utilizan principalmente en sistemas distribuidos empresariales cerrados y controlados. Los algoritmos de Tolerancia a Fallas no Bizantinas más representativos incluyen el algoritmo Paxos y el algoritmo Raft.

Algoritmos de tolerancia a fallas bizantinas

Los algoritmos de tolerancia a fallas bizantinas permiten que un sistema distribuido garantice la confiabilidad incluso si los nodos experimentan cualquier tipo de falla, siempre y cuando el número de nodos defectuosos no exceda cierta proporción. En pocas palabras, mientras el número de nodos defectuosos (debido a fallas no bizantinas o bizantinas) sea menor que cierta proporción de los nodos totales, los algoritmos de tolerancia a fallas bizantinas pueden garantizar la confiabilidad del sistema. Debido a la presencia de muchos nodos de red no confiables en sistemas blockchain como Bitcoin y Ethereum, los algoritmos de tolerancia a fallas bizantinas se utilizan principalmente en los mecanismos de consenso blockchain. Los algoritmos de tolerancia a fallas bizantinas más representativos incluyen PBFT (Tolerancia Práctica a Fallas Bizantinas), PoW (Prueba de Trabajo) y PoS (Prueba de Participación).