Problém dvou armád

Ilustrace problému: A1 a A2 jsou vojska obou generálů, B jsou ozbrojenci ve městě. Každý bod odpovídá stejnému počtu mužů. Problém dvou armád (též problém dvou generálů nebo problém koordinovaného útoku) je v informatice teoretický myšlenkový experiment, který dokazuje nedosažitelnou jistotu dvou subjektů domluvit se na společné akci přes nespolehlivý komunikační kanál.

Definice

V malém údolí, obklopeném horami, leží opevněné město, ke kterému vedou dvě přístupové cesty. Z obou stran vyčkávají dvě armády, jejichž generálové plánují na toto město zaútočit. +more Síla ozbrojenců ve městě je dost velká na to, aby odvrátila útok jedné armády (a tu zničila), ale nejsou tak silní, aby se ubránili, pokud zaútočí obě armády najednou. Generálové toto vědí a proto hodlají zaútočit koordinovaně. Potřebují se tedy dohodnout na čase útoku. Generálové však spolu nemohou komunikovat jinak, než že přes město tajně posílají posly. Vždy je ale nějaká pravděpodobnost, že posel bude odhalen a zadržen.

Ilustrace problému

První generál navrhne čas koordinovaného útoku a ten se ve zprávě pokusí poslat druhému generálovi. (Dejme tomu, že doba potřebná k přenášení zpráv je k době do plánovaného útoku zanedbatelná, stejně jako počet případných zadržených poslů k počtu mužů kterékoli z armád. +more) Protože ale každá zpráva může nebo nemusí projít, druhý generál se její obsah může nebo nemusí dozvědět. První generál uvažuje, že pokud druhý generál zprávu nedostal, pak by on ve stanovený čas buď útočil na město sám (a byl zničen), nebo by právě z tohoto důvodu útok neprovedl. Druhý generál toto chování předpokládá a proto - pokud zprávu dostane - posílá zpět potvrzení, říkající: „budu tam“. Tato zpráva prvnímu generálovi potvrdí, že druhý generál zná čas útoku a v ten zaútočí. Avšak pouze tehdy, pokud zpráva projde. Druhý generál uvažuje, že pokud jeho potvrzení neprojde, první generál si může myslet, že jeho původní zpráva s časem útoku neprošla, takže ve stanovený čas nebude mít podporu druhé armády a bez ní tedy nemá vůbec smysl útočit - a pokud u bran města nebude první generál, pak tam nebude ani on. První generál to předpokládá, a tak - pokud vyrozumění dostane - pošle zprávu říkající „tak domluveno“. Pokud dorazí, rozptýlí jakékoli obavy druhého generála, že by se v den a hodinu útoku se svou armádou ocitl před branami města sám. Problém je, že ani tato zpráva se nemusí přes město k němu dostat, a ať už bude vyslaných zpráv mezi oběma armádami kolik chce, vždy bude panovat v obou armádách nejistota, že jejich plán na společný útok na město bude zhacen.

Důkaz

Praktická řešení

První generál vyšle větší množství zpráv oznamující čas útoku a zaútočí tak jako tak. Předpokládá se, že při vysokém počtu poslaných zpráv alespoň jedna projde. +more Druhý generál zde ani nemusí odpovídat. * První generál vyšle větší množství (N0) zpráv, ve kterých krom času útoku přidá i to, kolik jich poslal. Druhý generál odpoví na každou, kterou obdržel (N1). Počet odpovědí vrácených prvnímu generálovi budiž N2. V tomto bodě navíc oba generálové znají přibližnou míru úspěšnosti, že bude posel zprávu přes město pronese: \frac{N_1}{N_0} resp. \sqrt{\frac{N_2}{N_0}}.

Historie

Problém byl poprvé nastíněn v roce 1975 E. A. +more Akkoyunluem, K. Ekanadhamem a R. V. Huberem v jejich práci Some Constraints and Trade-offs in the Design of Network Communications na straně 73 a to v kontextu vzájemné komunikace nikoli dvou armád ale dvou gangů. V roce 1978 se problém objevil v příkladu práce Notes on Data Base Operating Systems Jima Graye, který jej nastínil v kontextu dvou generálů - nazval jej Two Generals Paradox. Grayův kontext byl používán častěji a tak problém získal i své současné jméno.

Reference

Kategorie:Algoritmy