Problema De Los Dos Generales

Problema de los dos generales
En computación, el Problema de los dos generales es un experimento mental que ilustra los problemas y retos de diseño involucrados en la coordinación de una acción a través de una comunicación a través de un vínculo poco fiable. Está relacionado con la generalización del Problema de los generales bizantinos (aunque se conoce de mucho antes ) y aparece frecuentementeen clases introductorias sobre redes informáticas (particularmente respecto al protocolo TCP), aunque también puede aplicarse a otros tipos de comunicación (ver; Criptología). También es un concepto importante en lógica epistémica, y la importancia del conocimiento común. Algunos autores hablan de esto como elProblema de las dos armadas o el Problema del Ataque Coordinado.1 2

Índice  [ocultar] 
1 Definición
2 Ilustración del problema
3 Demostración
3.1 Para protocolos deterministas con un número limitado de mensajes
3.2 Para protocolos no deterministas y variables en longitud
4 Enfoque en ingeniería
5 Historia
5.1 Referencias
Definición[editar]
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 generalesse 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 demensaje) 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 permitaa 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 dosgenerales reside en la imposibilidad de diseñar un algoritmo tal que los generales puedan usar para que permita llegar a la conclusión anterior.
Ilustración del problema[editar]
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 puedellevar 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 loacordado". 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-...