Si le envías a un amigo el mensaje «Nos vemos mañana a las 3 de la tarde frente a la estación» y no te responde, es fácil inquietarse sin saber si lo ha leído. Aunque te responda «De acuerdo», ahora puedes preguntarte si sabe que has recibido su respuesta. En informática hay un problema famoso que explica esta cadena interminable de confirmaciones mediante la historia de dos generales. Es el «problema de los dos generales (Two Generals' Problem)».
En pocas palabras, el problema de los dos generales es un experimento mental que muestra que, si se utiliza un canal de comunicación en el que los mensajes pueden perderse por el camino, dos partes jamás pueden tener plena certeza de haber acordado realizar la misma acción. Es un tema habitual al empezar a estudiar redes y sistemas distribuidos y se considera el primer problema de comunicación entre computadoras cuya imposibilidad de resolución se demostró.
En este artículo veremos qué situación plantea el problema de los dos generales, por qué no se puede resolver, dónde surgió y cómo se aborda esta limitación en la práctica.
El problema de los dos generales y la cadena interminable de confirmaciones
¿Qué situación plantea el problema de los dos generales?
El problema comienza con la historia de dos ejércitos separados por un castillo.
(1) Dos ejércitos acampados por separado
Los ejércitos al mando de dos generales acampan en colinas distintas para atacar un castillo. Si atacan al mismo tiempo, pueden tomarlo, pero si ataca uno solo, ese ejército sufrirá una gran derrota.
(2) Un mensajero cruza un valle peligroso
La única forma de comunicarse que tienen los dos generales es enviar un mensajero a través del valle que vigilan las tropas del castillo. El mensajero puede ser capturado en cualquier momento, y quien lo envía no tiene forma de saber si ha llegado.
(3) La certeza que buscan los generales
Además de fijar la hora del ataque, cada general quiere tener la certeza de que ambos atacarán a esa hora. Necesitan esa certeza para poder movilizar a sus tropas con tranquilidad.
Así, el problema de los dos generales ilustra con una escena sencilla la dificultad de coordinar las acciones de dos partes mediante un canal de comunicación poco fiable.
¿Por qué nunca se alcanza la certeza?
Podría parecer que enviar mensajeros de ida y vuelta varias veces resolvería el problema, pero con cada confirmación vuelve a surgir la misma duda.
(1) La incertidumbre del primer mensaje
Aunque el primer general envíe a un mensajero con el aviso «Atacaremos a las 6 de la mañana», dudará por temor a atacar solo, ya que desconoce si el mensajero ha llegado.
(2) Una cadena interminable de respuestas
Si el segundo general responde «Recibido, atacaré a las 6», ahora es él quien se preocupa por si su respuesta habrá llegado. Aunque el primer general envíe otra confirmación para avisar de que recibió la respuesta, ese último mensajero también puede ser capturado.
(3) La paradoja del último mensajero
Por muchos mensajes que se intercambien, quien envió al último mensajero no puede saber si ha llegado. Si lo capturan, la situación se ve igual desde la perspectiva de quien lo envió. Por tanto, si el ataque depende de ese único mensajero, puede ocurrir que solo ataque uno de los ejércitos. De ahí se concluye que ningún método que intercambie un número fijo de confirmaciones puede coordinar a la perfección a los dos generales.
El mensaje de confirmación puede perderse con la misma facilidad que el mensaje original. Por muchas confirmaciones que se acumulen, la incertidumbre sobre la última permanece intacta.
¿Dónde surgió el problema de los dos generales?
El problema se formuló en la década de 1970, cuando las redes informáticas apenas empezaban a desarrollarse.
- Primera publicación (First Publication). En 1975, E. A. Akkoyunlu, K. Ekanadham y R. V. Huber publicaron por primera vez el problema y la demostración de que era irresoluble en un artículo sobre las limitaciones del diseño de las comunicaciones en red. En ese artículo, la situación se ilustraba con dos bandas que se comunicaban entre sí y que desempeñaban el papel de los generales.
- Autor del nombre (Naming). En 1978, el investigador de bases de datos Jim Gray llamó a este problema «paradoja de los dos generales (Two Generals Paradox)» en un texto sobre sistemas operativos para bases de datos. A partir de entonces se difundió la versión actual de la historia de los generales.
- Ampliación a un problema más general (Byzantine Generals Problem). En 1982, Leslie Lamport, Robert Shostak y Marshall Pease publicaron el «problema de los generales bizantinos», que plantea una situación en la que hay traidores entre varios generales. El problema de los dos generales suele presentarse como introducción al estudio de este problema.
¿Cómo se aborda esta limitación en la práctica?
Dado que la certeza absoluta es imposible, en la práctica se opta por reducir la incertidumbre a un nivel manejable.
(1) Enviar el mensaje varias veces
Si el primer general envía a varios mensajeros, la probabilidad de que todos sean capturados disminuye considerablemente. La probabilidad de éxito puede aumentar lo suficiente, aunque siga habiendo incertidumbre.
(2) Confirmación y retransmisión
TCP (Transmission Control Protocol), un protocolo básico de comunicación de Internet, intercambia tres mensajes al establecer una conexión. Después de enviar datos, los retransmite si no recibe una confirmación dentro del plazo establecido. Con este método se logra una fiabilidad suficiente para el uso práctico, aunque no se puede garantizar que ambos extremos estén siempre en el mismo estado.
(3) Usar también el silencio como señal
También se puede acordar de antemano que, si no se recibe ninguna comunicación durante un tiempo determinado, se dará por hecho que la otra parte ha aceptado el plan. Así se puede alcanzar un alto grado de certeza con menos mensajeros.
Todos estos métodos comparten el objetivo de alcanzar un nivel de fiabilidad suficiente, aun sin llegar a la perfección.
El problema de los dos generales nos recuerda que incluso la tecnología más sofisticada es incapaz de superar por completo las limitaciones de un canal de comunicación incierto. Las aplicaciones de mensajería, los sistemas de pago y los servicios en la nube que usamos hoy también se diseñan teniendo en cuenta esta limitación.
El primer paso para diseñar sistemas fiables es aceptar que la certeza absoluta es imposible e incorporar mecanismos de protección a partir de esa premisa.
