Problema de los dos generales

El problema se presenta como una analogía con un escenario de guerra en el que dos ejércitos, cada uno liderado por un general, se preparan para atacar una ciudad fortificada. Los ejércitos están acampados cerca de la ciudad, cada uno en una colina. Un valle separa ambas colinas, y el único modo que tienen los generales de comunicarse es mediante el envío de mensajeros por el valle. Desafortunadamente, en el valle se encuentran los defensores de la ciudad y existe cierta posibilidad de que capturen a cualquiera de estos mensajeros. (enterándose y/o alterando el mensaje). Téngase en cuenta que aunque los dos generales se han puesto de acuerdo en que atacarán, no han acordado el momento de hacerlo.

Los dos generales deben atacar la ciudad a la vez para no fracasar. Deben, por tanto, comunicarse y decidir el momento oportuno. Como cada general debe saber que el otro ha aceptado el plan de ataque, y por los temores a que el mensaje original sea perdido o modificado por el enemigo (confirmación de recepción de mensaje) la coordinación entre los generales podría ser interminable sin consenso.

Este ejercicio mental implica tener en cuenta cómo se llega efectivamente a dicho consenso. En su forma más simple, un general (al que llamaremos "primer general") será el líder, el cual decide el momento de ataque, y le comunica la información al otro general. El problema consiste en llegar a un algoritmo que le permita a los generales comunicarse de manera efectiva para, así, predecir el momento exacto de la ejecución de las acciones bélicas.

En principio, y según lo expuesto, es bastante sencillo para los generales llegar a un acuerdo en lo que se refiere al momento de atacar. Es suficiente para ello un mensaje satisfactorio con una respuesta igualmente satisfactoria . La sutileza del Problema de los dos generales reside en la imposibilidad de diseñar un algoritmo tal que los generales puedan usar para que permita llegar a la conclusión anterior.

El primer general puede comenzar diciendo "Atacaremos el 4 de agosto a las 09:00". Sin embargo, una vez enviado, el primer general no tiene la certeza de si el mensajero llegó al otro lado. Cualquier tipo de incertidumbre puede llevar al primer general a dudar de las acciones a tomar, lo cual sería desastroso para sus fines. Si los generales no atacan coordinados, la guarnición de la ciudad rechazará la vanguardia, y disminuirá considerablemente sus fuerzas.

Sabiendo esto, el segundo general puede mandar una confirmación de nuevo al primero: "He recibido el mensaje y atacaremos el 4 de agosto a las 09:00 según lo acordado". Sin embargo, ¿qué pasaría si el mensajero no llegó a su destino?. Alternativamente -y como precaución- se define entonces que el segundo mensaje podría decir simplemente: "Recibido el mensaje". Pero ¿si el mensaje fue capturado? ¿Cómo saber que no fue alterado?

Se hace evidente que no importa cuántas veces se confirme la información, no hay forma de garantizar -según este planteamiento- que ambos generales manejan la misma información.

Supóngase que exista una secuencia de longitud fija de mensajes, algunos entregados con éxito y otros no, que satisfaga cumplir el requisito de la certeza compartida de ambos generales para atacar. En este caso debe haber algún subconjunto mínimo no vacío de mensajes satisfactoriamente entregados que satisfaga (al menos un mensaje con el instante/plan debe ser entregado). Considérese el último de estos mensajes entregados con éxito en dicha secuencia mínima. Si este último mensaje no se hubiese entregado con éxito entonces el requisito no se habría cumplido, y un general al menos (presumiblemente el receptor) habría decidido no atacar. Desde el punto de vista del último remitente, sin embargo, la secuencia de mensajes enviada y recibida es exactamente la misma que habría sido antes, cuando el mensaje se hubiese recibido. Por tanto el general que manda el último mensaje habría aun así decidido atacar (ya que el protocolo es determinista). Hemos construido una circunstancia en la que el protocolo supuesto lleva a un general a atacar sin compañía, contradiciendo la presunción de que el protocolo era solución al problema.

Tal protocolo puede ser modelado como un bosque finito etiquetado, en el que cada nodo representa un recorrido del protocolo hasta el punto especificado. Las raíces se etiquetan con los posibles mensajes de inicio, y los hijos de un nodo N se etiqueta con los posibles mensajes siguientes después de N. Los nodos hoja representan recorridos en los que el protocolo termina después de haber enviado un mensaje con el nodo etiquetado. El bosque vacío representa el protocolo que termina antes de enviar ningún mensaje.

Sea P un protocolo que resuelve el Problema de los dos generales. Entonces, por un argumento similar al utilizado en el caso de arriba, ‘P’ debe también resolver el Problema de los dos generales, donde P’ se obtiene de P quitando todos los nodos hoja. Ya que P es finito, sigue que el protocolo representado por el bosque vacío resuelve el Problema de los dos generales. Pero claramente no lo hace, contradiciendo la existencia de P.

Un enfoque pragmático para hacer frente al problema de los dos generales es utilizar esquemas que acepten la incertidumbre del canal de comunicaciones y no intente eliminarla, sino mitigarla hasta un grado aceptable. Por ejemplo, el primer general podría enviar 100 mensajeros, anticipando que la probabilidad de que capturarlos a todos sea baja. Con este enfoque el primer general atacará sin importar lo que pase, y el segundo atacará si recibe cualquier mensaje. Alternativamente, el primer general podría mandar una caravana de mensajeros y el segundo podría mandar confirmación de cada uno, aumentando así la confianza de cada general con cada mensaje recibido. Tal y como se ve en la demostración, sin embargo, ninguno de los dos puede estar completamente seguro de que el ataque será coordinado. No hay ningún algoritmo que puedan usar (e.g. atacar si se reciben más de cuatro mensajeros) que asegure que uno no ataque sin el otro. Además, el primer general puede enviar una marca en cada mensaje diciendo que es el mensaje número 1, 2, 3...o n. Este método permitiría al segundo general saber cuán seguro es el canal y enviar un número apropiado de mensajes de vuelta para asegurar una alta probabilidad de que al menos uno sea recibido. Si el canal puede ser convertido en uno seguro, entonces un mensaje será suficiente y no serán de ayuda mensajes adicionales. El último mensaje tiene tanta posibilidad de perderse como el primero.

El problema de los dos generales y la demostración de su imposibilidad fue publicado por primera vez por E. A. Akkoyounlu, K. Ekanadham, y R. V. Huber en 1975 en "Some Constraints and Trade-offs in the Design of Network Communications",^[3]​ donde se describe desde la página 73 en el contexto de comunicación entre dos grupos de gangsters.

Jim Gray dio a este problema el nombre «La paradoja de los dos generales»^[4]​ en 1978 en Notes on Data Base Operating Systems^[5]​ desde la página 465. Esta referencia suele darse como fuente para la definición del problema y su demostración, aunque ambos fueron publicados como se dice arriba.