Två generalers problem
Inom datoranvändning är Two Generals' Problem ett tankeexperiment avsett att illustrera fallgroparna och designutmaningarna med att försöka samordna en handling genom att kommunicera via en opålitlig länk. I experimentet kan två generaler bara kommunicera med varandra genom att skicka en budbärare genom fiendens territorium. Experimentet frågar hur de kan komma överens om tidpunkten för att starta en attack, samtidigt som de vet att alla budbärare de skickar kan fångas.
The Two Generals' Problem framstår ofta som en introduktion till det mer allmänna bysantinska generalsproblemet i inledande klasser om datornätverk (särskilt med avseende på Transmission Control Protocol , där det visar att TCP inte kan garantera statens överensstämmelse mellan ändpunkter och varför detta är fallet), även om det gäller alla typer av tvåpartskommunikation där kommunikationsfel är möjliga. Detta problem är ett nyckelbegrepp inom epistemisk logik och belyser vikten av allmän kunskap . Vissa författare hänvisar också till detta som Two Generals' Paradox , Two Armies Problem , eller the Coordinated Attack Problem . The Two Generals' Problem var det första datorkommunikationsproblemet som visade sig vara olösligt. En viktig konsekvens av detta bevis är att generaliseringar som problemet med bysantinska generaler också är olösliga inför godtyckliga kommunikationsfel, vilket ger en bas av realistiska förväntningar på alla distribuerade konsistensprotokoll.
Definition
Två arméer , var och en ledd av en annan general , förbereder sig för att anfalla en befäst stad. Arméerna ligger i läger nära staden, var och en i sin egen dal. En tredje dal skiljer de två kullarna åt, och det enda sättet för de två generalerna att kommunicera är genom att skicka budbärare genom dalen. Tyvärr är dalen ockuperad av stadens försvarare och det finns en chans att en given budbärare som skickas genom dalen kommer att fångas.
Medan de två generalerna har kommit överens om att de ska attackera, har de inte kommit överens om en tidpunkt för en attack. Det krävs att de två generalerna låter sina arméer attackera staden samtidigt för att lyckas, så att den ensamma angripararmén inte dör i försök. De måste alltså kommunicera med varandra för att besluta om en tidpunkt för attack och för att gå med på att attackera vid den tidpunkten, och varje general måste veta att den andra generalen vet att de har gått med på attackplanen. Eftersom bekräftelse av meddelandemottagning kan förloras lika lätt som det ursprungliga meddelandet, krävs en potentiellt oändlig rad meddelanden för att komma till konsensus .
Tankeexperimentet går ut på att överväga hur de kan gå tillväga för att komma till enighet. I sin enklaste form är en general känd för att vara ledaren, bestämmer tiden för attacken och måste kommunicera denna tid till den andra generalen. Problemet är att komma på algoritmer som generalerna kan använda, inklusive att skicka meddelanden och bearbeta mottagna meddelanden, som kan tillåta dem att korrekt dra slutsatser:
- Ja, vi kommer båda att attackera vid den överenskomna tiden.
Med tanke på att det är ganska enkelt för generalerna att komma överens om tidpunkten för attack (dvs. ett framgångsrikt meddelande med ett framgångsrikt bekräftelse), ligger subtiliteten i Two Generals' Problem i omöjligheten att utforma algoritmer för generalerna att använda för att säkert gå med på ovanstående uttalande.
Illustrerar problemet
Den första generalen kan börja med att skicka ett meddelande "Attack kl 0900 den 4 augusti." Men när den väl skickats ut har den första generalen ingen aning om huruvida budbäraren kom igenom eller inte. Denna osäkerhet kan leda till att den första generalen tvekar att attackera på grund av risken att vara den enda angriparen.
För att vara säker kan den andra generalen skicka en bekräftelse tillbaka till den första: "Jag fick ditt meddelande och kommer att attackera kl 0900 den 4 augusti." Budbäraren som bär bekräftelsen kan dock bli tillfångatagen och den andre generalen kan tveka, i vetskap om att den första kan hålla tillbaka utan bekräftelsen.
Ytterligare bekräftelser kan tyckas vara en lösning – låt den första generalen skicka en andra bekräftelse: "Jag fick din bekräftelse på den planerade attacken klockan 0900 den 4 augusti." Men denna nya budbärare från den första generalen kommer också att bli tillfångatagen. Således blir det snabbt uppenbart att oavsett hur många omgångar av bekräftelse som görs så finns det inget sätt att garantera det andra kravet att varje general är säker på att den andra har gått med på attackplanen. Båda generalerna kommer alltid att undra om deras sista budbärare kom igenom.
Bevis
För deterministiska protokoll med ett fast antal meddelanden
Eftersom detta protokoll är deterministiskt , anta att det finns en sekvens av ett fast antal meddelanden, ett eller flera levererade framgångsrikt och ett eller flera inte. Antagandet är att det bör finnas en delad säkerhet för båda generalerna att angripa .
Tänk på det senaste meddelandet som levererades. Om det sista meddelandet inte hade levererats, skulle åtminstone en general (förmodligen mottagaren) besluta att inte attackera. Från avsändarens synvinkel av det sista meddelandet är emellertid sekvensen av meddelanden som skickats och levereras exakt densamma som den skulle ha varit om meddelandet hade levererats.
Eftersom protokollet är deterministiskt kommer den allmänna som skickar det sista meddelandet fortfarande att besluta sig för att attackera. Vi har nu skapat en situation där det föreslagna protokollet leder en general till attack och den andra inte till attack – vilket motsäger antagandet att protokollet var en lösning på problemet.
För icke-deterministiska protokoll och protokoll med variabel längd
Ett icke-deterministiskt protokoll med ett potentiellt variabelt meddelandeantal kan jämföras med ett kantmärkt ändligt träd , där varje nod i trädet representerar ett utforskat exempel upp till en specificerad punkt. Ett protokoll som avslutas innan några meddelanden skickas representeras av ett träd som endast innehåller en rotnod. Kanterna från en nod till varje barn är märkta med de meddelanden som skickas för att nå barntillståndet. Bladnoder representerar punkter där protokollet avslutas.
Antag att det finns ett icke-deterministiskt protokoll P som löser de två generalernas problem. Sedan, med ett liknande argument som det som används för deterministiska protokoll med fast längd ovan, P' också lösa Two Generals' Problem, där trädet som representerar P' erhålls från det för P genom att ta bort alla bladnoder och kanterna som leder till dem.
Eftersom P är ändligt, följer det att protokollet som avslutas innan några meddelanden skickas skulle lösa problemet. Men det är klart att det inte gör det. Därför kan ett icke-deterministiskt protokoll som löser problemet inte existera.
Tekniska tillvägagångssätt
Ett pragmatiskt tillvägagångssätt för att hantera de två generalernas problem är att använda system som accepterar osäkerheten i kommunikationskanalen och inte försöker eliminera den, utan snarare mildra den i en acceptabel grad. Till exempel kunde den första generalen skicka 100 budbärare och förutse att sannolikheten för att alla blir tillfångatagna är låg. Med detta tillvägagångssätt kommer den första generalen att attackera oavsett vad, och den andra generalen kommer att attackera om något meddelande tas emot. Alternativt kan den första generalen skicka en ström av meddelanden och den andra generalen kan skicka bekräftelser till var och en, där varje general känner sig mer bekväm med varje mottagen meddelande. Som framgår av beviset kan dock ingen av dem vara säker på att attacken kommer att koordineras. Det finns ingen algoritm som de kan använda (t.ex. attackera om fler än fyra meddelanden tas emot) som säkert kommer att förhindra en från att attackera utan den andra. Den första generalen kan också skicka en markering på varje meddelande som säger att det är meddelande 1, 2, 3 ... av n. Denna metod kommer att tillåta den andra generalen att veta hur tillförlitlig kanalen är och skicka ett lämpligt antal meddelanden tillbaka för att säkerställa en hög sannolikhet för att åtminstone ett meddelande tas emot. Om kanalen kan göras tillförlitlig räcker det med ett meddelande och ytterligare meddelanden hjälper inte. Den sista är lika sannolikt att gå vilse som den första.
Om man antar att generalerna måste offra liv varje gång en budbärare skickas och avlyssnas, kan en algoritm utformas för att minimera antalet budbärare som krävs för att uppnå det maximala förtroendet som attacken koordineras. För att rädda dem från att offra hundratals liv för att uppnå mycket högt förtroende för samordning, kunde generalerna komma överens om att använda frånvaron av budbärare som en indikation på att generalen som påbörjade transaktionen har fått minst en bekräftelse och har lovat att attackera. Anta att det tar en budbärare 1 minut att korsa farozonen, att tillåta 200 minuters tystnad att inträffa efter att bekräftelser har tagits emot kommer att tillåta oss att uppnå extremt högt förtroende utan att offra budbärarliv. I detta fall används budbärare endast i de fall där en part inte har fått attacktiden. I slutet av 200 minuter kan varje general resonera: "Jag har inte fått ett extra meddelande på 200 minuter; antingen misslyckades 200 budbärare att korsa farozonen, eller så betyder det att den andra generalen har bekräftat och förbundit sig till attacken och har förtroende Jag kommer också".
Historia
De två generalernas problem och dess omöjlighetsbevis publicerades först av EA Akkoyunlu, K. Ekanadham och RV Huber 1975 i "Some Constraints and Trade-offs in the Design of Network Communications", där det beskrivs med början på sidan 73 i sammanhanget för kommunikation mellan två grupper av gangsters.
Detta problem fick namnet Two Generals Paradox av Jim Gray 1978 i "Notes on Data Base Operating Systems" som börjar på sidan 465. Denna referens ges allmänt som en källa för definitionen av problemet och omöjlighetsbeviset, även om båda publicerades tidigare som nämnts ovan.