Coordinated Attack Problem
Stelt u zich twee troepen legers voor die strijden tegen dezelfde vijand. De twee troepen bevinden zich elk op een heuvel met daar tussenin een vallei waarin de vijand zich bevindt. Om de vijand te kunnen verslaan is een gezamenlijke aanval noodzakelijk. Hiervoor moeten de generaals van beide troepen onderling afspreken wanneer de aanval plaats gaat vinden. Om dit voor elkaar te krijgen stuurt de éne generaal, generaal A, een menselijke berichtgever naar de andere generaal, generaal B. Het kan gebeuren dat de berichtgever onderweg gevangen of vermoord wordt door de vijand. Hierdoor is er een kans dat een verstuurd bericht helemaal niet aankomt. Generaal A wil daarom graag een bevestiging van het bericht en dus stuurt generaal B een berichtgever terug dat hij het door generaal A verstuurde bericht ontvangen heeft. Generaal B wil echter graag een bericht terug dat de door hem verstuurde bevestiging wel bij Generaal A is aangekomen zodat generaal B weet dat generaal A weet dat generaal B weet wanneer er aangevallen gaat worden. Generaal A wil echter weer graag een bevestiging dat het door hem verstuurde bericht weer is aangekomen.
Je merkt het al, dit kan oneindig lang doorgaan. Elke generaal wil telkens een bevestiging van zijn verstuurde bericht, zodat het weet dat het bericht is aangekomen en ze gezamenlijk kunnen gaan aanvallen. Het probleem is dat, omdat elke generaal telkens een bevestiging wil, een gezamenlijke aanval nooit kan plaatsvinden! Om dit goed te begrijpen is enige kennis van het begrip common knowlegde noodzakelijk.
Stel dat X een bepaald feit is. Dan kun je je verschillende situaties voorstellen. Iedereen weet X, iedereen weet dat iedereen weet X, iedereen weet dat iedereen weet dat iedereen weet X, …. enz. Met noemt iets common knowlegde als een dergelijke reeks van ‘iedereen weet dat iedereen weet dat…’ oneindig lang doorgaat. Common knowlegde wordt gezien als een verklaring voor gecoördineerd gedrag. Bij het coordinated attack problem kan alleen een gezamenlijke aanval plaatsvinden als er sprake is van common knowlegde. Hiervoor moeten er oneindig lang berichten heen en weer worden verstuurd en dit is niet mogelijk omdat er maar een eindige tijd zit tussen het eerst verzonden bericht en het tijdstip dat de gezamenlijke aanval moet gaan plaatsvinden. Een formeel bewijs dat voor het coordinated attack problem common knowlegde tussen beide generaals nodig is en dat dit niet bereikt kan worden vindt men bijvoorbeeld in Halpern en Moses (1990).
Nu is het coordinated attack problem minder erg dan het lijkt. In het mobiele tijdperk waarin we nu leven moet het natuurlijk mogelijk zijn voor de generaals om een gezamenlijke aanval af te spreken zonder berichtgevers naar elkaar te sturen. Een telefoongesprek tussen de generaals zorgt direct voor de benodigde common knowlegde.