Problema dels dos generals

En computació, el Problema dels dos generals, també cridat Problema de les dos armada o Problema de l'Atac Coordinat, és un experiment mental que ilustra els problemes i reptes de disseny involucrats en la coordinació d'una acció a través d'una comunicació a través d'un víncul poc fiable.

Està relacionat en el més general Problema dels generals bizantins (encara que es coneix de molt abans).

S'utilisa freqüentment com a introducció a problemes dels sistemes de comunicació com per eixemple en rets informàtiques (particularment respecte al protocol TCP) i Criptología. També és un concepte important en llògica epistémica, i l'importància del coneiximent comú.

Definició

El problema es presenta com una analogia en un escenari de guerra en el que dos eixèrcits, cada u liderat per un general, es preparen per a atacar una ciutat fortificada. Els eixèrcits estan acampats prop de la ciutat, cada u en un tossal. Una vall separa abdós tossals, i l'únic modo que tenen els generals de comunicar-se és per mig de l'enviament de mensagers per la vall. Desafortunadament, en la vall es troben els defensors de la ciutat i existix certa possibilitat de que capturen a qualsevol d'estos mensagers. (enterant-se i/o alterant el mensage). Tinga's en conte que encara que els dos generals s'han posat d'acort en que atacaran, no han acordat el moment de fer-ho.

Els dos generals deuen atacar la ciutat al mateix temps per a no fracassar. Deuen, per tant, comunicar-se i decidir el moment oportú. Com cada general deu saber que l'atre ha acceptat el pla d'atac, i pels temors a que el mensage original siga perdut o modificat per l'enemic (confirmació de recepció de mensage) la coordinació entre els generals podria ser interminable sense consens.

Este eixercici mental implica tindre en conte cóm s'aplega efectivament a dit consens. En la seua forma més simple, un general (al que cridarem "primer general") serà el líder, el qual decidix el moment d'atac, i li comunica l'informació a l'un atre general. El problema consistix en aplegar a un algoritme que li permeta als generals comunicar-se de manera efectiva para, aixina, predir el moment exacte de l'eixecució de les accions bèliques.

En principi, i segons lo expost, és prou senzill per als generals aplegar a un acort pel que fa al moment d'atacar. És suficient per a això un mensage satisfactori en una resposta igualment satisfactòria . La subtilea del Problema dels dos generals residix en l'impossibilitat de dissenyar un algoritme tal que els generals puguen usar per a que permeta aplegar a la conclusió anterior.

Ilustració del problema

El primer general pot començar dient "Atacarem el 4 d'agost a les 09:00". No obstant, una volta enviat, el primer general no té la certea de si el mensager va aplegar a l'atre costat. Qualsevol tipo d'incertitut pot dur al primer general a dubtar de les accions a prendre, la qual cosa seria desastrós per als seus fins. Si els generals no ataquen coordinats, la guarnició de la ciutat rebujarà la vanguarda, i disminuirà considerablement les seues forces.

Sabent açò, el segon general pot manar una confirmació de nou al primer: "He rebut el mensage i atacarem el 4 d'agost a les 09:00 segons lo acordat". No obstant, ¿qué passaria si el mensager no va aplegar al seu destí?. Alternativament -i com a precaució- es definix llavors que el segon mensage podria dir simplement: "Rebut el mensage". Pero ¿si el mensage va ser capturat? ¿Cóm saber que no va ser alterat?

Es fa evident que no importa quàntes voltes es confirme l'informació, no hi ha forma de garantisar -segons este plantejament- que abdós generals manegen la mateixa informació.