En informática, el problema de los dos generales es un experimento mental destinado a ilustrar las trampas y los desafíos de diseño de intentar coordinar una acción comunicándose a través de un vínculo no confiable. En el experimento, dos generales solo pueden comunicarse entre sí enviando un mensajero a través del territorio enemigo. El experimento pregunta cómo podrían llegar a un acuerdo sobre el momento de lanzar un ataque, sabiendo que cualquier mensajero que envíen podría ser capturado.
Está relacionado con el problema general bizantino más general y aparece a menudo en clases introductorias sobre redes de computadoras (particularmente con respecto al Protocolo de control de transmisión , donde muestra que TCP no puede garantizar la coherencia de estado entre los puntos finales y por qué este es el caso). aunque se aplica a cualquier tipo de comunicación entre dos partes donde es posible que se produzcan fallos en la comunicación. Un concepto clave en la lógica epistémica , este problema destaca la importancia del conocimiento común . Algunos autores también se refieren a esto como la paradoja de los dos generales , el problema de los dos ejércitos o el problema del ataque coordinado . [1][2] El problema de los dos generales fue el primer problema de comunicación informática que se demostró que no tenía solución. Una consecuencia importante de esta prueba es que generalizaciones como el problema de los generales bizantinos también son irresolubles frente a fallas de comunicación arbitrarias, proporcionando así una base de expectativas realistas para cualquier protocolo de consistencia distribuida.
Definición
Dos ejércitos , cada uno liderado por un general diferente , se están preparando para atacar una ciudad fortificada. Los ejércitos acampan cerca de la ciudad, cada uno en su propio valle. Un tercer valle separa las dos colinas, y la única forma de que los dos generales se comuniquen es enviando mensajeros a través del valle. Desafortunadamente, el valle está ocupado por los defensores de la ciudad y existe la posibilidad de que cualquier mensajero enviado a través del valle sea capturado.
Si bien los dos generales han acordado que atacarán, no han acordado un momento para atacar. Se requiere que los dos generales hagan que sus ejércitos ataquen la ciudad al mismo tiempo para tener éxito, no sea que el único ejército atacante muera en el intento. Por lo tanto, deben comunicarse entre sí para decidir el momento de atacar y aceptar atacar en ese momento, y cada general debe saber que el otro general sabe que ha aceptado el plan de ataque. Debido a que el acuse de recibo del mensaje se puede perder tan fácilmente como el mensaje original, se requiere una serie potencialmente infinita de mensajes para llegar a un consenso .
El experimento mental implica considerar cómo podrían llegar a un consenso. En su forma más simple, se sabe que un general es el líder, decide el momento del ataque y debe comunicar este momento al otro general. El problema es idear algoritmos que los generales puedan usar, incluido el envío de mensajes y el procesamiento de los mensajes recibidos, que les permitan concluir correctamente:
- Sí, ambos atacaremos a la hora acordada.
Permitiendo que sea bastante simple para los generales llegar a un acuerdo sobre el momento de atacar (es decir, un mensaje exitoso con un reconocimiento exitoso), la sutileza del problema de los dos generales radica en la imposibilidad de diseñar algoritmos para que los usen los generales. para aceptar con seguridad la declaración anterior.
Ilustrando el problema
El primer general puede comenzar enviando un mensaje "Ataque a las 0900 del 4 de agosto". Sin embargo, una vez despachado, el primer general no tiene idea de si el mensajero logró comunicarse o no. Esta incertidumbre puede llevar al primer general a dudar en atacar por el riesgo de ser el único atacante.
Sin duda, el segundo general puede enviar una confirmación al primero: "Recibí su mensaje y atacaré a las 0900 del 4 de agosto". Sin embargo, el mensajero que lleva la confirmación podría enfrentar la captura y el segundo general puede dudar, sabiendo que el primero podría contenerse sin la confirmación.
Otras confirmaciones pueden parecer una solución; deje que el primer general envíe una segunda confirmación: "Recibí su confirmación del ataque planeado a las 0900 del 4 de agosto". Sin embargo, este nuevo mensajero del primer general también puede ser capturado. Por lo tanto, rápidamente se hace evidente que no importa cuántas rondas de confirmación se realicen, no hay forma de garantizar el segundo requisito de que cada general esté seguro de que el otro ha aceptado el plan de ataque. Ambos generales siempre se quedarán preguntándose si su último mensajero logró comunicarse.
Prueba
Para protocolos deterministas con un número fijo de mensajes
Debido a que este protocolo es determinista , suponga que hay una secuencia de un número fijo de mensajes, uno o más entregados con éxito y uno o más no. La suposición es que debe haber una certeza compartida para que ambos generales ataquen .
Considere el último mensaje de este tipo que se envió con éxito. Si ese último mensaje no se hubiera entregado con éxito, al menos un general (presumiblemente el receptor) decidiría no atacar. Sin embargo, desde el punto de vista del remitente de ese último mensaje, la secuencia de mensajes enviados y entregados es exactamente la misma que habría sido si ese mensaje hubiera sido entregado.
Dado que el protocolo es determinista, el general que envía ese último mensaje aún decidirá atacar. Ahora hemos creado una situación en la que el protocolo sugerido lleva a un general a atacar y al otro a no atacar, lo que contradice la suposición de que el protocolo era una solución al problema.
Para protocolos no deterministas y de longitud variable
Un protocolo no determinista con un recuento de mensajes potencialmente variable se puede comparar con un árbol finito etiquetado como borde , donde cada nodo del árbol representa un ejemplo explorado hasta un punto específico. Un protocolo que termina antes de enviar cualquier mensaje está representado por un árbol que contiene solo un nodo raíz. Los bordes de un nodo a cada hijo se etiquetan con los mensajes enviados para alcanzar el estado hijo. Los nodos hoja representan puntos en los que termina el protocolo.
Suponga que existe un protocolo no determinista P que resuelve el problema de los dos generales. Entonces, por un argumento similar al usado para los protocolos deterministas de longitud fija arriba, P ' también debe resolver el Problema de los Dos Generales, donde el árbol que representa a P' se obtiene a partir del de P eliminando todos los nodos de hojas y los bordes que conducen a ellos.
Dado que P es finito, se deduce que el protocolo que termina antes de enviar cualquier mensaje resolvería el problema. Pero claramente no es así. Por tanto, no puede existir un protocolo no determinista que resuelva el problema.
Enfoques de ingeniería
Un enfoque pragmático para abordar el problema de los dos generales es utilizar esquemas que acepten la incertidumbre del canal de comunicaciones y no intenten eliminarlo, sino mitigarlo en un grado aceptable. Por ejemplo, el primer general podría enviar 100 mensajeros, anticipando que la probabilidad de que todos sean capturados es baja. Con este enfoque, el primer general atacará sin importar qué, y el segundo general atacará si se recibe algún mensaje. Alternativamente, el primer general podría enviar un flujo de mensajes y el segundo general podría enviar acuses de recibo a cada uno, sintiéndose cada general más cómodo con cada mensaje recibido. Sin embargo, como se ve en la prueba, ninguno de los dos puede estar seguro de que el ataque se coordine. No existe un algoritmo que puedan usar (por ejemplo, atacar si se reciben más de cuatro mensajes) que seguramente evitará que uno ataque sin el otro. Además, el primer general puede enviar una marca en cada mensaje diciendo que es el mensaje 1, 2, 3 ... de n. Este método permitirá al segundo general saber qué tan confiable es el canal y enviar un número apropiado de mensajes de regreso para asegurar una alta probabilidad de que se reciba al menos un mensaje. Si se puede hacer que el canal sea confiable, entonces un mensaje será suficiente y los mensajes adicionales no ayudarán. Es tan probable que el último se pierda como el primero.
Suponiendo que los generales deben sacrificar vidas cada vez que se envía e intercepta un mensajero, se puede diseñar un algoritmo para minimizar el número de mensajeros necesarios para lograr la máxima confianza en que se coordina el ataque. Para salvarlos de sacrificar cientos de vidas para lograr una confianza muy alta en la coordinación, los generales podrían acordar utilizar la ausencia de mensajeros como una indicación de que el general que inició la transacción ha recibido al menos una confirmación y ha prometido atacar. Supongamos que un mensajero tarda 1 minuto en cruzar la zona de peligro, y permitir que ocurran 200 minutos de silencio después de que se hayan recibido las confirmaciones nos permitirá alcanzar una confianza extremadamente alta sin sacrificar las vidas de los mensajeros. En este caso, los mensajeros se utilizan solo en el caso de que una parte no haya recibido el tiempo de ataque. Al final de los 200 minutos, cada general puede razonar: "No he recibido un mensaje adicional durante 200 minutos; o 200 mensajeros no pudieron cruzar la zona de peligro, o significa que el otro general ha confirmado y comprometido el ataque y tiene confianza". Yo lo hare tambien".
Historia
El problema de los dos generales y su prueba de imposibilidad fue publicado por primera vez por EA Akkoyunlu, K. Ekanadham y RV Huber en 1975 en "Algunas restricciones y compensaciones en el diseño de comunicaciones de red", [3] donde se describe a partir de página 73 en el contexto de la comunicación entre dos grupos de gánsteres.
Este problema recibió el nombre de la paradoja de los dos generales por Jim Gray [4] en 1978 en "Notas sobre sistemas operativos de bases de datos" [5] a partir de la página 465. Esta referencia se da ampliamente como fuente para la definición del problema y la prueba de imposibilidad, aunque ambas fueron publicadas previamente como se mencionó anteriormente.
Referencias
- ↑ Gmytrasiewicz, Piotr J .; Edmund H. Durfee (1992). "Modelado recursivo de teoría de decisiones y el problema de ataque coordinado" . Actas de la Primera Conferencia Internacional sobre Sistemas de Planificación de Inteligencia Artificial . San Francisco: Morgan Kaufmann Publishers: 88–95. doi : 10.1016 / B978-0-08-049944-4.50016-1 . ISBN 9780080499444. Consultado el 27 de diciembre de 2013 .
- ↑ El ataque coordinado y las amazonas celosas de Alessandro Panconesi. Consultado el 17 de mayo de 2011.
- ^ Akkoyunlu, EA; Ekanadham, K .; Huber, RV (1975). Algunas limitaciones y compensaciones en el diseño de comunicaciones de red (PDF) . Portal.acm.org. págs. 67–74. doi : 10.1145 / 800213.806523 . S2CID 788091 . Consultado el 19 de marzo de 2010 .
- ^ "Página de inicio del resumen de Jim Gray" . Research.microsoft.com. 2004-05-03 . Consultado el 19 de marzo de 2010 .
- ^ "Notas sobre sistemas operativos de bases de datos" . Portal.acm.org . Consultado el 19 de marzo de 2010 .