La tarea de los generales bizantinos

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 23 de julio de 2020; las comprobaciones requieren 13 ediciones .

La tarea de los generales bizantinos es, en criptología , la tarea de la interacción de varios suscriptores remotos que recibían órdenes de un centro. Algunos de los suscriptores, incluido el centro, pueden ser intrusos (o los intrusos cambiaron los mensajes durante la transmisión). Es necesario desarrollar una estrategia unificada de acciones que sea ventajosa para los suscriptores.

Redacción original

Bizancio . La noche antes de la gran batalla con el enemigo. El ejército bizantino consta de legiones, cada una de las cuales está comandada por su propio general. El ejército también tiene un comandante en jefe, a quien están subordinados los generales. $norte$

Al mismo tiempo, el imperio está en declive, y cualquiera de los generales e incluso el comandante en jefe pueden ser traidores a Bizancio, interesados en su derrota.

Por la noche, cada uno de los generales recibe una orden del comandante en jefe, lo que debe hacerse a las 10 de la mañana (la hora es la misma para todos y se sabe de antemano). Opciones de orden: “atacar al enemigo” o “retirada”.

Posibles resultados de la batalla:

Si todos los generales leales atacan, Bizancio destruirá al enemigo (resultado favorable).
Si todos los generales leales se retiran, Bizancio mantendrá su ejército (resultado intermedio).
Si algunos generales leales atacan y algunos se retiran, el enemigo eventualmente destruirá todo el ejército de Bizancio en partes (resultado desfavorable).

También debe tenerse en cuenta que si el comandante en jefe es un traidor, puede dar órdenes opuestas a diferentes generales para asegurar la destrucción del ejército. Por lo tanto, los generales deben tener en cuenta esta posibilidad y evitar acciones descoordinadas.

Si cada general actúa con total independencia de los demás (por ejemplo, hace una elección aleatoria), la probabilidad de un resultado favorable es muy baja.

Por lo tanto, los generales necesitan intercambiar información entre ellos para llegar a una decisión unificada.

Definición refinada

Que los generales "amarillos" lideren los ejércitos en las montañas y se preparen para atacar a los "azules" en el valle. Para la comunicación, los atacantes utilizan un canal confiable que excluye la sustitución de lo dicho, por ejemplo, un acuerdo memorizado desarrollado antes de la ocurrencia de una situación de incertidumbre. Sin embargo, algunos de los generales están visiblemente del lado del enemigo y están tratando activamente de evitar la unanimidad de los generales del acuerdo. El acuerdo es que todos los generales tienen información verdadera sobre el tamaño de todos los ejércitos participantes y llegan a las mismas conclusiones (aunque falsas) sobre el estado de los ejércitos enemigos. Según la redacción original, la última condición es especialmente importante si los generales planean desarrollar una estrategia de "exclusión del tercero" basada en los datos recibidos . $norte$ $norte$ $metro$

Formalización

Como resultado del intercambio, cada uno de los generales debe recibir un vector de números enteros de longitud n, en el que el i-ésimo elemento es igual al tamaño real del i-ésimo ejército (si su general cumple con el acuerdo) , o contiene desinformación sobre el tamaño del i-ésimo ejército (si su general no observa el acuerdo respecto a n de i cero, asignado al comandante en jefe). Al mismo tiempo, los vectores recibidos por todos los comandantes leales deben ser exactamente iguales.

Algoritmos de solución

Caso especial

Leslie Lamport propuso en 1982 un algoritmo de solución recursivo para el caso particular donde el número de generales es limitado y no puede cambiar dinámicamente . El algoritmo reduce el problema para el caso de traidores entre generales al caso de un traidor. $metro$ $norte$ $m-1$

Para el caso, el algoritmo es trivial, así que vamos a ilustrarlo para el caso y . En este caso, el algoritmo se lleva a cabo en 4 pasos. $metro=0$ $n=4$ $metro=1$

1er paso Cada general envía un mensaje a todos los demás, en el que indica el tamaño de su ejército. Los generales leales informan el número real, mientras que los traidores pueden informar diferentes números en diferentes mensajes. El general 1 indicaba el número 1 (mil soldados), el general 2 indicaba el número 2, el general 3 (traidor) indicaba los otros tres generales, respectivamente , , , (el verdadero valor es 3), y el general 4 indicaba 4. $X$ $y$ $z$

2do paso Cada uno forma su propio vector a partir de la información disponible:

Vector #1 general: (1,2,x,4);
Vector general #2: (1,2,y,4);
Vector general #3: (1,2,3,4);
Vector general #4: (1,2,z,4).

3er paso . Todos envían su vector a todos los demás (el general 3 vuelve a enviar valores arbitrarios).

Después de eso, cada general tiene cuatro vectores:

g1	g2	g3	g4
(1,2,x,4)	(1,2,x,4)	(1,2,x,4)	(1,2,x,4)
(1,2,y,4)	(1,2,y,4)	(1,2,y,4)	(1,2,y,4)
(a B C D)	(e F G H)	(1,2,3,4)	(yo, j, k, l)
(1,2,z,4)	(1,2,z,4)	(1,2,z,4)	(1,2,z,4)

4to paso . Cada general determina por sí mismo el tamaño de cada ejército. Para determinar el tamaño del -ésimo ejército, cada general toma números: el tamaño de este ejército, que proviene de todos los comandantes, excepto el comandante del -ésimo ejército. Si algún valor se repite entre estos números al menos una vez, entonces se coloca en el vector resultante; de lo contrario, el elemento correspondiente del vector resultante se marca como desconocido (o cero, etc.). $i$ $(n-1)$ $i$ $(n-1)$ ${\ estilo de visualización (nm-1)}$

Todos los generales leales reciben un vector , donde hay un número que ocurre al menos dos veces entre los valores de , o "desconocido" si los tres números son diferentes. Dado que los valores y la función de todos los generales leales son los mismos, se ha llegado a un acuerdo. $(1,2,f(x,y,z),4)$ $f(x,y,z)$ $(x, y, z)$ $(x, y, z)$ $x, y, z$ $F$

Caso general

La construcción de cadenas de bloques secuenciales conectados , combinada con la prueba de trabajo -utilizada por primera vez en la criptomoneda " Bitcoin "- permitió, con un nivel de riesgo aceptable, obtener un mecanismo para la toma de decisiones dinámicas en un caso más general de este problema, cuando el número de generales ( nodos de red ) no se conoce exactamente y puede cambiar dinámicamente de manera arbitraria.

Resultados de la investigación de problemas

Lamport demostró que en un sistema con procesadores que funcionan incorrectamente (“generales desleales”), solo se puede llegar a un acuerdo si hay procesadores que funcionan correctamente (“generales leales”), es decir, cuando hay estrictamente más “correctos” que el total . número. $metro$ $2m+1$ $2/3$

Aplicación

Bitcoin y otras criptomonedas [1] .
Sincronización de reloj

Véase también

Notas

↑ Marc Andressen . Por qué importa Bitcoin . The New York Times (21 de enero de 2014). Consultado el 2 de octubre de 2015. Archivado desde el original el 31 de enero de 2014. ( Marc Andressen . ¿Por qué es tan importante Bitcoin?. Habrahabr.ru. Fecha de acceso: 2 de octubre de 2015. Archivado el 28 de enero de 2014. (Ruso) - opción de traducción).