En informática, el Problema de los Dos Generales es un experimento mental que pretende ilustrar los problemas y desafíos de diseño que supone intentar coordinar una acción comunicándose a través de un enlace poco fiable. En el experimento, dos generales sólo pueden comunicarse entre sí enviando un mensajero a través del territorio enemigo. El experimento plantea la cuestión de 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.
El problema de los dos generales aparece a menudo como una introducción al problema más general de los generales bizantinos 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 consistencia 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 son posibles fallas de comunicación. Un concepto clave en la lógica epistémica , este problema resalta 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 de computadora que se demostró que no tenía solución. [3] Una consecuencia importante de esta prueba es que las generalizaciones como el problema de los generales bizantinos también son irresolubles ante fallas de comunicación arbitrarias, lo que proporciona una base de expectativas realistas para cualquier protocolo de consistencia distribuida.
Dos ejércitos , cada uno dirigido por un general diferente , se preparan para atacar una ciudad fortificada. Los ejércitos están acampados 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. [4]
Aunque los dos generales han acordado atacar, no han acordado el momento del ataque. Es necesario que los dos generales hagan que sus ejércitos ataquen la ciudad simultáneamente para tener éxito, para que el ejército atacante solitario no muera en el intento. Por lo tanto, deben comunicarse entre sí para decidir el momento del ataque y acordar atacar en ese momento, y cada general debe saber que el otro general sabe que han acordado el plan de ataque. Debido a que el acuse de recibo del mensaje puede perderse tan fácilmente como el mensaje original, se requiere una serie potencialmente infinita de mensajes para llegar a un consenso . [5]
El experimento mental consiste en 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 comunicarlo al otro general. El problema es idear algoritmos que los generales puedan utilizar, incluido el envío de mensajes y el procesamiento de los mensajes recibidos, que les permitan concluir correctamente:
Si se supone que es bastante sencillo 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 está en la imposibilidad de diseñar algoritmos que los generales puedan usar para acordar de manera segura la declaración anterior. [ cita requerida ]
El primer general puede empezar enviando un mensaje: "Ataque a las 09:00 horas del 4 de agosto". Sin embargo, una vez enviado, el primer general no tiene idea de si el mensajero llegó o no. Esta incertidumbre puede hacer que el primer general dude en atacar debido al riesgo de ser el único atacante.
Sin duda, el segundo general puede enviar una confirmación al primero: "He recibido su mensaje y atacaré a las 09:00 horas del 4 de agosto". Sin embargo, el mensajero que lleva la confirmación podría ser capturado, y el segundo general puede dudar, sabiendo que el primero podría resistirse sin la confirmación.
Puede parecer que una solución sería enviar más confirmaciones: que el primer general envíe una segunda confirmación: "He recibido su confirmación del ataque planeado a las 09:00 horas del 4 de agosto". Sin embargo, este nuevo mensajero del primer general también corre el riesgo de ser capturado. Por lo tanto, rápidamente se hace evidente que, sin importar 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 con la duda de si su último mensajero logró llegar a buen puerto. [6]
Como este protocolo es determinista , supongamos 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 debería haber una certeza compartida de que ambos generales atacarán . Consideremos el último mensaje de este tipo que se entregó con éxito. Si ese último mensaje no se hubiera entregado con éxito, entonces 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 se hubiera entregado. Como 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.
Un protocolo no determinista con un recuento de mensajes potencialmente variable se puede comparar con un árbol finito etiquetado en los bordes , donde cada nodo del árbol representa un ejemplo explorado hasta un punto especificado. Un protocolo que termina antes de enviar mensajes está representado por un árbol que contiene solo un nodo raíz. Los bordes desde un nodo hasta cada hijo están etiquetados con los mensajes enviados para alcanzar el estado hijo. Los nodos de hoja representan puntos en los que termina el protocolo. Supongamos que existe un protocolo no determinista P que resuelve el problema de los dos generales. Entonces, por un argumento similar al utilizado para los protocolos deterministas de longitud fija anteriores, P' también debe resolver el problema de los dos generales, donde el árbol que representa a P' se obtiene a partir de aquel para P eliminando todos los nodos de hoja y los bordes que conducen a ellos. Dado que P es finito, se deduce que el protocolo que termina antes de enviar mensajes resolvería el problema. Pero claramente, no lo hace. Por lo tanto, no puede existir un protocolo no determinista que resuelva el problema.
Un enfoque pragmático para tratar el problema de los dos generales es utilizar esquemas que acepten la incertidumbre del canal de comunicaciones y no intenten eliminarla, sino mitigarla hasta 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 recibe algún mensaje. Alternativamente, el primer general podría enviar una serie de mensajes y el segundo general podría enviar acuses de recibo a cada uno, y cada general se sentiría más cómodo con cada mensaje recibido. Sin embargo, como se ve en la prueba, ninguno puede estar seguro de que el ataque será coordinado. No hay ningún algoritmo que puedan usar (por ejemplo, atacar si se reciben más de cuatro mensajes) que sea seguro para evitar que uno ataque sin el otro. Además, el primer general puede enviar una marca en cada mensaje que diga 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 una cantidad apropiada de mensajes de vuelta 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 ayudan. El último tiene la misma probabilidad de perderse que 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 la cantidad de mensajeros necesarios para lograr la máxima confianza en que el ataque está coordinado. Para evitar que sacrifiquen cientos de vidas para lograr una confianza muy alta en la coordinación, los generales podrían acordar usar 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; permitir que haya 200 minutos de silencio después de que se hayan recibido las confirmaciones nos permitirá lograr una confianza extremadamente alta sin sacrificar vidas de mensajeros. En este caso, los mensajeros se utilizan solo en el caso de que una de las partes 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 bien 200 mensajeros no lograron cruzar la zona de peligro, o significa que el otro general ha confirmado y se ha comprometido con el ataque y confía en que yo también lo haré".
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", [7] donde se describe a partir de la página 73 en el contexto de la comunicación entre dos grupos de gánsteres.
Este problema recibió el nombre de Paradoja de los Dos Generales por parte de Jim Gray [8] en 1978 en "Notas sobre sistemas operativos de bases de datos" [9] a partir de la página 465. Esta referencia se cita ampliamente como fuente para la definición del problema y la prueba de imposibilidad, aunque ambas se publicaron previamente como se mencionó anteriormente.
{{cite book}}: |journal=ignorado ( ayuda ){{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )Versión en línea: Notas sobre sistemas operativos de bases de datos. Portal.acm.org . Consultado el 19 de marzo de 2010 .