Volver a contar los clásicos: comprender el problema de los generales bizantinos en un artículo

El problema de los generales bizantinos (The Byzantine Generals Problem) proporciona una descripción situacional del problema del consenso distribuido, publicado por primera vez por Leslie Lamport y otros en 1982. El documento "El problema de los generales bizantinos" también proporciona dos algoritmos para resolver el problema de los generales bizantinos:

Solución de mensaje oral (Una solución con mensaje oral);

Una solución con mensaje firmado.

Tesis:

https://www-inst.eecs.berkeley.edu/~cs162/sp16/static/readings/Original_Byzantine.pdf

Ambos algoritmos se describirán en detalle más adelante en este artículo. De hecho, el problema de los generales bizantinos es el modelo tolerante a fallas más complejo en el campo de los sistemas distribuidos, que describe cómo hacer que un sistema distribuido llegue a un consenso en presencia de un comportamiento malicioso, como la manipulación o falsificación de mensajes. Es una base importante para nosotros comprender los protocolos y algoritmos de consenso distribuidos.

Descripción del problema de los generales bizantinos

El problema de los generales bizantinos describe tal escenario:

Figura 1. Problema de los generales bizantinos

Varias divisiones del ejército del Imperio Bizantino estaban estacionadas fuera de la ciudad enemiga, cada división estaba comandada por su propio general. Los generales solo pueden comunicarse entre sí a través de mensajeros. Después de observar la situación del enemigo, debe formular un plan de acción común, como ataque (Attack) o retirada (Retreat), y solo cuando más de la mitad de los generales lanzan un ataque en conjunto pueden ganar. Sin embargo, algunos de estos generales pueden ser traidores que intentan evitar que los generales leales acuerden un plan de acción. Para empeorar las cosas, el mensajero responsable de entregar el mensaje también puede ser un traidor, que puede alterar o falsificar el mensaje, o hacer que se pierda.

Para tener una comprensión más profunda del problema de los generales bizantinos, tomamos como ejemplo el problema de los tres generales. Cuando los tres generales son leales, pueden votar para determinar un plan de acción coherente. La figura 2 muestra un escenario, es decir, el general A y B pueden lanzar un ataque al observar la situación militar del enemigo y combinar su propia situación, y el general C puede lanza un ataque a través de Observa la situación militar del enemigo y juzga en base a tu propia situación que debes retirarte. Al final, los tres generales votaron y el resultado fue ofensivo: retirada = 2:1, por lo que lanzarán una ofensiva juntos para ganar. Para tres generales, cuando cada general puede ejecutar dos decisiones (atacar o retirarse), hay 6 escenarios diferentes, y la Figura 2 es uno de ellos, y los otros 5 escenarios se pueden deducir simplemente por Un voto de los tres generales estaría de acuerdo un plan de acción.

Figura 2. Un escenario donde los tres generales son leales

Cuando hay un traidor entre los tres generales, puede interrumpir el plan de batalla normal. La Figura 3 muestra un escenario en el que el General C es un traidor. Envió diferentes mensajes al General A y al General B. En este escenario, el General A obtiene el ataque votando: retirada = 1: 2, y eventualmente hará un Plan de retirada; General B vota para atacar: retirada = 2:1, y finalmente hará un plan de acción ofensivo. Como resultado, solo el General B atacó y fue derrotado.

Figura 3. El escenario de dos lealtades y una traición

De hecho, para el escenario donde hay un traidor entre los tres generales, es imposible llegar siempre a un curso de acción consistente. Se puede encontrar una prueba detallada en el artículo de Leslie Lamport. Además, el documento da una conclusión más general: si hay m traidores, entonces se necesitan al menos 3m+1 generales para finalmente llegar a un plan de acción consistente.

Solución

Leslie Lamport dio dos soluciones al problema de los generales bizantinos en el artículo, a saber, una solución con mensaje oral y una solución con mensaje firmado.

1. Solución basada en mensajes

En primer lugar, la definición de mensaje oral es la siguiente:

A1 Cualquier mensaje ya enviado se comunicará correctamente;

A2 El receptor del mensaje sabe quién envió el mensaje;

A3 Se puede detectar la ausencia de mensajes.

Basándonos en la definición de mensaje oral, podemos saber que   el mensaje oral no se puede manipular, pero se puede falsificar. Con base en la derivación de la escena en la Figura 3, sabemos que cuando hay un general traidor, se deben agregar tres generales más leales para lograr el consenso final de acción. Para profundizar la comprensión, utilizaremos el escenario de 3 generales leales y 1 general traidor para derivar la solución del mensaje oral. En una solución de boca en boca, el general que envía el mensaje primero se llama comandante y los generales restantes se llaman tenientes. Para el escenario de 3 leales y 1 traidor, se requieren dos rondas de negociación de información de combate y, si no se recibe información de combate, retirarse por defecto. La figura 4 muestra la escena en la que el comandante es un general leal. En la primera ronda de negociación de información de combate, el comandante envió un mensaje ofensivo a los tres tenientes; en la segunda ronda, los tres tenientes negociaron nuevamente información de combate. , B es un general leal, por lo que enviaron un mensaje de ataque a los otros dos tenientes de acuerdo con el mensaje del comandante, y el General C era un traidor, para desbaratar el plan de batalla, envió un mensaje de retirada a los otros dos tenientes. Eventualmente, el Comandante General, el General A y B acordaron un plan de ataque que podría conducir a la victoria.

Figura 4. La escena donde el comandante es un general leal

La Figura 5 muestra el escenario donde el comandante es un traidor En la primera ronda de negociación de información de combate, el comandante envió un mensaje de retirada al General A y B, pero envió un mensaje de ataque al General C para interrumpir la decisión. En la segunda ronda, dado que todos los tenientes son generales leales, los mensajes del comandante se envían correctamente a los dos tenientes restantes. Al final, todos los generales leales pudieron ponerse de acuerdo sobre un plan de retirada.

Figura 5. La escena donde el comandante es un traidor

Como se mencionó anteriormente, para el problema general bizantino de boca en boca, si el número de traidores es m y el número de generales no es inferior a 3m+1, al final se puede llegar a un plan de acción consensuado. Vale la pena señalar que en este algoritmo se conoce el número de traidores m, y el número de traidores m determina el número de recursiones, es decir, el número de traidores m determina el número de rondas de negociación de información de combate, si hay m Para traidores, se requieren m+1 rondas de negociación de información de combate. Esta es también la razón por la cual se requieren dos rondas de negociación de información de combate cuando hay un general traidor mencionado anteriormente.

2. Solución de mensaje de firma

De manera similar, la definición de mensaje de firma consiste en agregar los siguientes dos elementos sobre la base de la definición de mensaje oral:

A4 La firma de un general leal no se puede falsificar y se descubrirá cualquier cambio en el contenido de su mensaje firmado;

A5 Cualquiera puede verificar la autenticidad de la firma del general.

Según la definición de mensajes firmados, podemos saber que los mensajes firmados no se pueden falsificar ni manipular. Para comprender profundamente la solución del mensaje de firma, también tomamos el problema de 3-3-generales como ejemplo para derivarlo.  La figura 6 muestra la escena en la que el general leal inicia por primera vez la negociación de la batalla. El general A envía primero el mensaje de ataque al general B y C. C manipula y el general B ejecutará el mensaje enviado por el general A.

Figura 6. Los generales leales toman la iniciativa en el inicio de negociaciones de combate

La figura 7 muestra la escena en la que el general traidor inicia primero la negociación del combate. El general traidor C envía primero información de combate engañosa, luego los generales A y B encontrarán que la información de combate enviada por el general C es inconsistente, por lo que determinan que son traidores. . Puede ser procesado y luego negociado para información de combate.

Figura 7. Los generales rebeldes toman la iniciativa en el inicio de negociaciones operativas

Las soluciones de mensajes firmados pueden manejar cualquier número de traidores.

Resumen

En el campo de los sistemas distribuidos, los roles en el Problema de los Generales Bizantinos corresponden al mundo de la informática de la siguiente manera:

General, correspondiente al nodo informático;

Generales leales, correspondientes a nodos informáticos bien administrados;

Un general traidor, un nodo informático controlado ilegalmente;

El mensajero murió, la falla de comunicación hizo que se perdiera el mensaje;

Messenger es reemplazado por espía, la comunicación es atacada, el atacante manipula o falsifica información.

Como se mencionó anteriormente, el problema de los generales bizantinos proporciona una descripción situacional del problema del consenso distribuido y es el modelo más complejo en el campo de los sistemas distribuidos. Además, también proporciona un marco para que comprendamos y clasifiquemos los numerosos protocolos y algoritmos de consenso distribuido existentes. Los protocolos y algoritmos de consenso distribuido existentes se pueden dividir principalmente en dos categorías:

Uno es el algoritmo Crash Fault Tolerance (Crash Fault Tolerance, CFT), que es un algoritmo tolerante a fallas no bizantino, que resuelve el problema de consenso en el escenario donde hay fallas en el sistema distribuido pero no ataques maliciosos. Es decir, en este escenario, los mensajes pueden perderse y los mensajes pueden repetirse, pero no hay un escenario donde los mensajes sean manipulados o falsificados. Generalmente se usa en sistemas distribuidos en escenarios LAN, como bases de datos distribuidas. Los algoritmos comunes que pertenecen a esta categoría incluyen el algoritmo Paxos, el algoritmo Raft, el protocolo ZAB, etc.

Uno es el algoritmo tolerante a fallas bizantinas, que puede resolver el problema de consenso en sistemas distribuidos donde hay fallas y ataques maliciosos. Generalmente se usa en sistemas distribuidos en escenarios de Internet, como en la tecnología blockchain de moneda digital. Los algoritmos comunes que pertenecen a esta categoría incluyen el algoritmo PBFT y el algoritmo PoW.

Después de leer este artículo, ¿qué opinas de estas dos soluciones? ¡Bienvenido a discutir con nosotros en el área de comentarios!

Tags：

Huobi App