The Two Generals Problem on ajatuskokeilu laskennassa , joka on suunniteltu havainnollistamaan kahden järjestelmän tilan synkronoinnin ongelmaa epäluotettavalla viestintäkanavalla. Tämä ongelma on usein katettu tietokoneverkkojen (erityisesti TCP -protokollan ) aikana, vaikka sitä voidaan soveltaa muihin viestintävälineisiin. Kirjallisuudessa sitä kutsutaan joskus myös kahden armeijan tehtäväksi .
Kaksi armeijaa, joista kumpaakin johtaa oma kenraali, valmistautuu ryöstämään kaupunkia. Näiden armeijoiden leirit sijaitsevat kahdella kukkulalla, joita erottaa laakso. Ainoa tapa kommunikoida kenraalien välillä on lähettää sanansaattajia viestejä pitkin laakson poikki. Mutta laakso on vihollisen miehittämä ja kuka tahansa sanansaattaja voidaan siepata. Ongelmana on se, että kenraalit tekivät perustavanlaatuisen päätöksen hyökkäyksestä etukäteen (kun viestintä oli), mutta eivät sopineet hyökkäyksen tarkasta ajasta ( aika H ).
Hyökkäyksen onnistumiseksi kenraalien on hyökättävä kaupunkiin samanaikaisesti. Vain yhden armeijan hyökkäys johtaa tuhoisiin seurauksiin hyökkääjille. On löydettävä viestinvaihtoalgoritmi, jonka jälkeen jokainen kenraali olisi varma, että he molemmat hyökkäävät määrättynä aikana.
Huomaa, että tällaiseen sopimukseen pääseminen (kun kyseessä on luotettava viestintäkanava) on hyvin yksinkertaista - vain yksi viesti, jossa on hyökkäyksen alkamisaika, ja yksi viesti, joka vahvistaa sopimuksen. Tehtävän monimutkaisuus on siinä, ettei näiden viestien taattua vaihtoa varten voida kehittää algoritmia.
Oletetaan, että ensimmäinen kenraali lähettää toiselle viestin "Hyökkäämme huomenna kello yhdeksän aamulla . " Lähetettyään sanansaattajan ensimmäinen kenraali ei tiedä, onko sanansaattaja saavuttanut toisen kenraalin. Koska hän ei tiedä, tukeeko toinen kenraali tekojaan, ensimmäinen saattaa viivyttää hyökkäystä. Tämän tietäen toinen kenraali voi lähettää vahvistusviestin "Sain viestisi ja hyökkää huomenna kello yhdeksän aamulla . " Mutta myös vastustaja voi siepata tämän viestin. Tietäen, että ensimmäinen kenraali ei aloita hyökkäystä ilman vahvistusta, toinen kenraali voi myös viivyttää hyökkäystä. Ensimmäinen kenraali voi lähettää viestin "Olen vastaanottanut vahvistuksen hyökkäyksen alkamisajasta" , mutta tämä voidaan myös siepata. Nopeasti käy ilmi, että riippumatta siitä, kuinka monta sanomanvaihtojaksoa on olemassa, ei ole mitään keinoa olla varma, että molemmille kenraaleille ilmoitetaan heidän viestiensä vastaanottamisesta. Ongelmaan ei siis ole ratkaisua.
Oletetaan, että jokin viestisarja, toimitettu tai siepattu, mahdollistaa sen, että molemmat kenraalit sopivat hyökkäyksen alkamisajasta. Tässä tapauksessa tällaisia viestejä on pieni osajoukko. Harkitse viimeistä viestiä tässä minimaalisessa sarjassa. Kuten mikä tahansa muu viesti, se voidaan siepata. Jos sitä ei toimiteta, johdonmukaisuusehto ei täyty, ja yksi kenraaleista (todennäköisimmin vastaanottaja) viivyttää hyökkäystään. Toisen kenraalin näkökulmasta vaihtoalgoritmia seurataan, ja hän aloittaa hyökkäyksen täysin luottavaisin mielin siitä, että häntä tuetaan. Siten tunnettua oikeaa algoritmia käytettäessä syntyy tilanne, jossa toinen kenraali hyökkää kaupunkiin ja toinen ei. Tämä on ristiriidassa oletuksemme kanssa algoritmin olemassaolosta ongelman ratkaisemiseksi.
Pragmaattinen lähestymistapa ongelman ratkaisemiseen ei sisällä kanavan epäluotettavuuden poistamista kokonaan, vaan sen vähentämistä hyväksyttävälle tasolle. Esimerkiksi ensimmäinen kenraali voi lähettää 100 sanansaattajaa kerralla sanoman kanssa ottaen huomioon, että todennäköisyys siepata kaikki sanansaattajat kerralla on äärimmäisen pieni, ja sitten hyökätä odottamatta vahvistusta määritettynä aikana. Tämä menetelmä ei kuitenkaan tietenkään takaa tiukkaa kenraalien toiminnan koordinointia.
Kahden yleisen ongelman ja ratkaisemattomuuden todisteen julkaisi ensimmäisenä E.A. Akkoyunlu, K. Ekanadham ja R.V. Huber vuonna 1975 teoksessa "Some Constraints and Tradeoffs in Network Communication Design", jossa se on kuvattu sivulta 73 alkaen kahden gangsteriryhmän välisen viestinnän yhteydessä.