El problema de los dos generales: una paradoja sin solución que ilustra los retos del diseño de redes de comunicación
¿Estás listo para quemar neuronas? Espero que sí, porque eso es exactamente lo que hace este problema. Se trata de un experimento mental, pero uno sin solución.
Puede que te estés preguntando cuál es el punto de intentar resolver algo si ya sabes que tal cosa es imposible, pero justamente, el punto es hacer el ejercicio y entender por qué es que no se puede resolver. Veamos de qué se trata.
El problema
Dos generales se disponen a atacar una ciudad. Para que el ataque sea exitoso, deben atacar a la vez, pero se encuentran en lados opuestos y la única forma que tienen de comunicarse para coordinar el ataque es mediante un mensajero.
Cuando el primero de los generales decide que está listo para atacar, le envía un mensaje al otro diciendo «Atacaremos mañana, 26 de febrero, a las 10:00 AM». El otro lo recibe, pero... ¿cómo puede el primer general saber que el segundo recibió el mensaje? ¿Y si el mensajero hubiese sido capturado en el camino? Seguro el segundo general no puede atacar sin saber que el primero sabe que ha recibido el mensaje, así que envía a un segundo mensajero.
Cuando el primer general recibe el mensaje del segundo diciendo «mensaje recibido» debería atacar en la fecha y hora acordadas, ¿no? Hay un problema: ¿cómo sabe el segundo que el primero recibió su confirmación? Ahora es su mensajero el que podría haber sido capturado. Hay una sola opción: mandar un segundo mensaje de confirmación.
Quizás ya veas hacia dónde va esto. Incluso cuando el segundo general reciba el segundo mensaje de confirmación, no tendrá manera de saber si su contraparte está al tanto de que el mensaje fue recibido. Los dos generales podrían seguir enviando mensajes, pero el problema persistiría. Ninguno podrá estar seguro de que su mensaje llegó a destino y el ataque se pospondría indefinidamente.
- Por suerte, no todas las guerras se prolongan tanto: «¡Eso sí que fue rápido! Estas fueron 5 de las guerras más cortas de la historia»
¿Entonces?
Entonces... Nada. No habrá manera de que ambos generales estén 100 % seguros de que el otro sabe que ambos acuerdan realizar el ataque. A esta altura, puede que te estés preguntando cuál es el punto de todo esto...
Bien, el problema suele ser presentado en clases de introducción a la computación y busca demostrar los problemas de diseñar una red que intente enviar un mensaje a través de un vínculo poco fiable. No está diseñado como un problema a resolver, sino más bien como un ejemplo educativo.
En los hechos, sí hay algo así como « soluciones». Una de ellas, implica el uso de la probabilidad. Los generales pueden enviarse miles de mensajes de confirmación, pero ¿cuáles son las probabilidades de que todos esos mensajeros sean capturados? Podrían determinar que, luego de cierto número de comunicaciones, la probabilidad de que el otro general no haya recibido el mensaje es tan baja que podría considerarse que el intercambio se ha confirmado.
¿Qué te pareció esta paradoja? ¿Conoces otros problemas similares? Si buscas problemas que sí tengan solución, puedes probar algunos de nuestros acertijos: