Algoritmo para resolver el problema de los generales bizantinos
La descripción original del problema bizantino es: n generales están separados en diferentes lugares, y los generales leales esperan llegar a un acuerdo sobre un determinado orden a través de algún acuerdo (como atacar juntos o retirarse juntos). Pero algunos de estos generales traidores impedirán que los generales leales lleguen a un acuerdo sobre las órdenes enviando mensajes equivocados. Lamport demostró que los generales leales pueden lograr un acuerdo de orden cuando el número total de generales es superior a 3 millones y el número de desertores es m o menos.
Para garantizar los requisitos anteriores, se deben cumplir las dos condiciones siguientes:
1. Cada dos generales leales deben recibir el mismo valor v(i) (v(i) es la orden del i-ésimo general)
2. Si el i-ésimo general es leal, entonces la orden que envía es la misma que v(i) recibe cada general leal
.Para simplificar el modelo anterior, utilizamos la forma de un general que envía órdenes a varios ayudantes para probar. El general que envía la orden se llama comandante y el general que recibe la orden es el ayudante. Las dos condiciones anteriores se pueden expresar como:
IC1. Todos los tenientes leales obedecen las mismas órdenes
IC2 Si el general que dio la orden es leal, entonces todos los tenientes leales obedecen las órdenes. del comandante (el general que dio la orden)
Nota especial: solo un general envía órdenes a la vez, y sus órdenes se envían a n-1 ayudantes. m representa el número de traidores. Dado que el número total de generales es n, el número total de ayudantes es n-1. El cumplimiento del ayudante en IC2 en realidad significa que los generales leales pueden recibir correctamente los mensajes de mando de los generales leales. El acuerdo se llega a través de mensajes verbales, y si hay m generales traidores, el número total de generales debe ser 3 millones 1 o más. Las siguientes son algunas condiciones predeterminadas para la mensajería verbal:
A1. Cada mensaje enviado se puede entregar correctamente
A2. El destinatario del mensaje sabe quién lo envió.
A3. Pudiendo conocer el mensaje faltante
A1 y A2 asumen que no hay interferencia en la comunicación entre los dos generales, y tampoco hay un traidor que obstaculice el envío del mensaje (truncamiento). ) ni No habrá casos de traidores que fabriquen información (falsificación). Es decir, cada general puede enviar su mensaje a todos los demás generales sin error. (Esta condición necesaria puede no ser requerida en la siguiente sección)
Definimos el algoritmo de mensaje oral OM(m). Para todos los números enteros no negativos m, cada comandante envía comandos a n-1 tenientes a través del algoritmo OM (M). A continuación se explicará que el algoritmo OM(m) puede resolver el problema de los generales bizantinos cuando hay como máximo m desertores y el número total de generales es 3 m 1 o más. (Teniendo en cuenta el entorno real de las aplicaciones de red, el texto original utiliza el valor recibido en lugar del comando recibido, y este artículo no será modificado)
El algoritmo define una función: mayoría (com1, com2,. .., comn) es igual al comando mayoritario.
Algoritmo OM(0)
(1) El comandante envía su orden a cada ayudante.
(2) Cada teniente adopta la orden que recibió del comandante, o adopta por defecto la orden de retirada si no recibe ninguna orden.
Algoritmo OM(m)
(1) El comandante envía su orden a cada ayudante.
(2) Para cada i, vi es la orden que recibe cada ayudante i del comandante. Si no se recibe ninguna orden, es la orden de retirada. El teniente i actúa como comandante en OM(m-1) y envía vi a otros tenientes n-2.
(3) Para cada i y j\neq i, vj es el comando enviado por el ayudante i desde el ayudante j en el paso (2) (usando el algoritmo OM(m-1)), si la orden del ayudante j en el paso (2) no se recibe, la orden de retirada quedará predeterminada. Finalmente, el ayudante i usa mayoría (v1,...,vn-1) para obtener el comando.
A continuación, consideremos una situación en la que n=4, m=1:
1. Cuando el ayudante D es el traidor
El primer paso es da la orden A ejecuta el algoritmo OM(1) y envía su orden a tres ayudantes B, C y D. Los tres ayudantes recibieron la orden correctamente.
En el segundo paso, cada ayudante que recibe la orden ejecuta el algoritmo OM(0) como comandante y envía la orden que recibió a los demás ayudantes. Debido a que el ayudante D es un traidor, da la orden. al ayudante Las noticias entregadas por B y C pueden ser noticias falsas. Los ayudantes B y C deciden respectivamente el orden basándose en la función mayoritaria.
Tal traición al Ayudante D no puede interferir con la decisión del comandante. Veamos qué sucede si el comandante es un traidor.
2. El comandante es un traidor y los ayudantes restantes son leales
Paso 1: El comandante A envía órdenes diferentes a los ayudantes B, C y D. En la situación real. Un atacante envía valores inconsistentes (por ejemplo, 0 o 1) a diferentes partes en un intento de impedir que el teniente tome una decisión unánime.
Paso 2: Después de que el ayudante recibe la orden, se transforma en el comandante y ejecuta OM(0) para enviar la orden a todos los ayudantes. Cada ayudante aún puede alcanzar una orden unánime a través del algoritmo de votación mayoritaria.
El artículo luego demuestra que el algoritmo OM(m) puede satisfacer cualquier m. Primero, se introduce un lema (prueba por inducción):
Lema 1: Para cualquier m y k. , si hay más de 2k m generales y como máximo k desertores, entonces el algoritmo OM(m) satisface IC2 (recuerde que IC2 significa que si el general es leal, todos los tenientes obedecen las órdenes del general).
Prueba: Cuando m=0, OM(0) satisface IC2 cuando el general es leal. Cuando mgt; 0, primero el general pasa la orden a n-1 ayudantes, y luego cada ayudante ejecuta el algoritmo OM (m-1) para n-1 generales. Porque se supone que ngt; 2k m (el número de generales en el lema es mayor que 2k m), entonces n-1 gt; cada ronda no es menos del doble que la de los traidores), de modo que las órdenes recibidas por el ayudante leal en cada ronda del algoritmo OM(m-k) son mayoritarias(v1, v2,..., v(n-1)) , y las órdenes enviadas por el ayudante leal son mayores o iguales a la mitad.
Luego resuelve el problema de los generales bizantinos.
Teorema 1: Para cualquier m, si hay más de 3m generales y como máximo m desertores, el algoritmo OM(m) satisface la condición IC1 y la condición IC2.
Demostración: mediante prueba inductiva de m, probamos OM(m) mgt;0 suponiendo que OM(m-1) se cumple. El general que primero considera enviar la orden es leal. Entonces, si k en el lema se establece en m, entonces OM(m) satisface IC2, y IC1 también se satisface cuando el general emisor es leal.
A continuación, considere que uno de los m traidores es el comandante, entonces, como máximo, solo los ayudantes m-1 son traidores, y debido a que hay 3 millones de generales, el número total de ayudantes excede los 3 m-1. son 3m-1gt; Por tanto, por inducción se supone que OM(m-1) satisface IC1 e IC2 (como máximo 3(m-1) generales y como máximo m-1 desertores). Entonces, dos tenientes leales j reciben el mismo comando vj en OM(m-1), luego, en el algoritmo OM(m) cada teniente leal recibirá (v1, v2,...,\v(n- 1)), Se puede observar que se cumplen las condiciones IC1 e IC2.
Después de leer esta prueba, estaba bastante confundido ~~~~, así que hice un dibujo para ver cómo lo demostraba Lambor:
Además de los mensajes orales satisfactorios, los mensajes firmados Además de los tres requisitos de A1-A3, también se deben cumplir los siguientes A4:
A4 (a) La firma no puede falsificarse y puede descubrirse una vez que ha sido manipulada
(b) Cualquiera puede verificarlo Fiabilidad de la firma del general
A continuación se define una función Choice() similar a la función mayoritaria() anterior para determinar la elección del ayudante: 1. Cuando el conjunto V solo contiene un elemento v, entonces elección(V)= v; 2. elección(o)=RETIRO.
Basándonos en el A4 anterior y la elección(), damos el método SM(m):
Algoritmo SM(m)
Inicializar Vi=empty set
(1) El general firma la orden y la envía a cada ayudante
(2) Para cada ayudante i:
(A) Si el ayudante Recibo la orden del mensaje del ordenante a v: 0, y no se ha recibido ninguna otra secuencia de comando, entonces:
(i) Hacer Vi {v}
(ii) Enviar v: 0:i A todos los demás tenientes
(B) Si el teniente i recibe el mensaje v:0:j1:...:jk y v no está en el conjunto Vi entonces
(i) Agregar v a Vi
(ii) Si klt;m, entonces envíe v:0:j1:...:jk:i a cada teniente que no esté en j1,..., jk
(3) Para cada teniente i, cuando no se reciban más mensajes, se seguirá el comando elegir(Vi)
Algunas instrucciones sobre el algoritmo:
El tercer paso del algoritmo es No explica cómo el ayudante determina que no hay ningún mensaje nuevo. Hay dos soluciones: una es exigir que cada ayudante firme y reenvíe el mensaje después de recibirlo, o que envíe un mensaje. notificación de que no enviará el mensaje; el otro es establecer un tiempo de espera, si el mensaje no se ha recibido dentro de este período de tiempo, se considera que el mensaje ya no se recibe.
En el algoritmo SM(m), pedirle al ayudante que firme es confirmar que ha recibido el mensaje (un poco como entregar un documento a cada líder para su aprobación). En SM(1), el ayudante no necesita firmar al recibir el mensaje porque no es necesario reenviarlo a otros ayudantes.
Teorema 2: Para cualquier m, hay como máximo m desertores, el algoritmo SM(m) resuelve el problema de los generales bizantinos
Prueba: Primero prueba IC2, si el comandante es leal , entonces todos los tenientes deben haber recibido la misma orden, porque la firma no puede ser alterada y IC1 está satisfecho. Para probar IC1, sólo necesitamos considerar la situación en la que el comandante es un traidor (recuerde que IC1 significa que todos los tenientes leales ejecutan la misma orden). IC1 requiere que dos tenientes leales (i, j) deben recibir el mismo conjunto de órdenes). Vi, Vj, es decir, cada v en Vi está en Vj. Habrá dos situaciones: una es cuando el ayudante i recibe la secuencia del comando v, la agrega a Vi y la envía al ayudante j, y j guarda el comando v; la otra es cuando el ayudante i recibe el comando v; 0:j1: ...:jk:i, donde jr=j, por lo que desde A4 podemos saber que el ayudante j también recibió la orden. Si no, entonces existe:
klt;m. En este caso, i envía el mensaje v:0:j1:...:jk:i al ayudante j, luego j debe recibir v. (Este sentimiento es similar al anterior)
k=m. El comandante es un traidor y, como máximo, los tenientes m-1 son traidores. Por lo tanto, existe al menos una secuencia j1,...,jm que es leal. Entonces j debe recibir el valor v enviado por esta secuencia de ayudante leal, por lo que el ayudante j recibe v.
Prueba cumplimentada.