Problem dwóch generałów - Two Generals' Problem
W informatyce Problem Dwóch Generałów jest eksperymentem myślowym mającym na celu zilustrowanie pułapek i wyzwań projektowych związanych z próbą skoordynowania działania poprzez komunikowanie się przez niepewne łącze. W eksperymencie dwóch generałów jest w stanie komunikować się ze sobą jedynie poprzez wysłanie posłańca przez terytorium wroga. Eksperyment pyta, w jaki sposób mogą dojść do porozumienia w sprawie czasu rozpoczęcia ataku, wiedząc, że każdy wysłany przez nich posłaniec może zostać schwytany.
Jest to związane z bardziej ogólnym problemem generałów bizantyjskich i pojawia się często we wstępnych zajęciach dotyczących sieci komputerowych (szczególnie w odniesieniu do protokołu kontroli transmisji , gdzie pokazuje, że TCP nie może zagwarantować spójności stanu między punktami końcowymi i dlaczego tak jest), chociaż ma to zastosowanie do każdego rodzaju komunikacji dwustronnej, w której możliwe są awarie komunikacji. Problem ten, kluczowy w logice epistemicznej , podkreśla znaczenie wiedzy powszechnej . Niektórzy autorzy nazywają to również paradoksem dwóch generałów , problemem dwóch armii lub problemem skoordynowanego ataku . Problem dwóch generałów był pierwszym problemem komunikacji komputerowej, którego nie można było rozwiązać. Ważną konsekwencją tego dowodu jest to, że uogólnienia, takie jak problem generałów bizantyjskich, są również nierozwiązywalne w obliczu arbitralnych awarii komunikacji, zapewniając w ten sposób podstawę realistycznych oczekiwań dla dowolnych rozproszonych protokołów spójności.
Definicja
Dwie armie , każda dowodzona przez innego generała , przygotowują się do ataku na ufortyfikowane miasto. Armie są obozowane w pobliżu miasta, każda w swojej własnej dolinie. Trzecia dolina oddziela dwa wzgórza, a jedynym sposobem komunikacji między dwoma generałami jest wysłanie posłańców przez dolinę. Niestety dolina jest okupowana przez obrońców miasta i istnieje szansa, że każdy wysłany przez nią posłaniec zostanie schwytany.
Chociaż obaj generałowie uzgodnili, że zaatakują, nie uzgodnili czasu ataku. Aby odnieść sukces, obaj generałowie muszą jednocześnie atakować miasto, w przeciwnym razie armia samotnych napastników zginie podczas próby. Muszą więc komunikować się ze sobą, aby zdecydować o czasie ataku i zgodzić się na atak w tym czasie, a każdy generał musi wiedzieć, że drugi generał wie, że zgodził się na plan ataku. Ponieważ potwierdzenie otrzymania wiadomości może zostać utracone równie łatwo, jak oryginalna wiadomość, do osiągnięcia konsensusu wymagana jest potencjalnie nieskończona seria wiadomości .
Eksperyment myślowy polega na rozważeniu, w jaki sposób mogą dojść do porozumienia. W najprostszej formie jeden generał jest przywódcą, decyduje o czasie ataku i musi tym razem przekazać drugiemu generałowi. Problemem jest wymyślenie algorytmów, z których mogą korzystać generałowie, w tym wysyłania wiadomości i przetwarzania otrzymanych wiadomości, które pozwolą im poprawnie wnioskować:
- Tak, oboje zaatakujemy w uzgodnionym czasie.
Pozwalając generałom dość łatwo dojść do porozumienia co do czasu ataku (tj. Jednej udanej wiadomości z pomyślnym potwierdzeniem), subtelność problemu dwóch generałów polega na niemożności zaprojektowania algorytmów, z których mogliby korzystać generałowie. bezpiecznie zaakceptować powyższe oświadczenie.
Zilustrowanie problemu
Pierwszy generał może zacząć od wysłania wiadomości „Atak 4 sierpnia o godz. 9:00”. Jednak po wysłaniu pierwszy generał nie ma pojęcia, czy posłaniec się przedostał. Ta niepewność może doprowadzić do tego, że pierwszy generał zawaha się przed atakiem ze względu na ryzyko bycia jedynym napastnikiem.
Dla pewności drugi generał może wysłać potwierdzenie z powrotem do pierwszego: „Otrzymałem twoją wiadomość i zaatakuję o 9:00 4 sierpnia”. Jednak posłaniec niosący bierzmowanie może stanąć w obliczu schwytania, a drugi generał może się wahać, wiedząc, że pierwszy może się powstrzymać bez potwierdzenia.
Dalsze potwierdzenia mogą wydawać się rozwiązaniem - niech pierwszy generał wyśle drugie potwierdzenie: „Otrzymałem Twoje potwierdzenie planowanego ataku 4 sierpnia o godz. 9:00”. Jednak ten nowy posłaniec od pierwszego generała również może zostać schwytany. W ten sposób szybko staje się oczywiste, że bez względu na to, ile rund potwierdzeń zostanie przeprowadzonych, nie ma możliwości zagwarantowania drugiego wymogu, aby każdy generał miał pewność, że drugi zgodził się na plan ataku. Obaj generałowie zawsze będą się zastanawiać, czy ich ostatni posłaniec się przedostał.
Dowód
Dla deterministycznych protokołów ze stałą liczbą komunikatów
Ponieważ ten protokół jest deterministyczny , załóżmy, że istnieje sekwencja ustalonej liczby komunikatów, jeden lub więcej pomyślnie dostarczonych i jeden lub więcej nie. Założenie jest takie, że obaj generałowie powinni mieć wspólną pewność ataku .
Weź pod uwagę ostatnią taką wiadomość, która została pomyślnie dostarczona. Gdyby ta ostatnia wiadomość nie została pomyślnie dostarczona, przynajmniej jeden generał (prawdopodobnie odbiorca) zdecydowałby nie atakować. Jednak z punktu widzenia nadawcy ostatniej wiadomości sekwencja wysłanych i dostarczonych wiadomości jest dokładnie taka sama, jak byłaby, gdyby ta wiadomość została dostarczona.
Ponieważ protokół jest deterministyczny, ogólne wysłanie ostatniej wiadomości nadal będzie decydowało o ataku. Stworzyliśmy teraz sytuację, w której sugerowany protokół prowadzi jednego generała do ataku, a drugiego do nie ataku, co jest sprzeczne z założeniem, że protokół był rozwiązaniem problemu.
Dla protokołów niedeterministycznych io zmiennej długości
Niedeterministyczny protokół z potencjalnie zmienną liczbą komunikatów można porównać do drzewa skończonego ze znakami krawędzi , w którym każdy węzeł w drzewie reprezentuje zbadany przykład aż do określonego punktu. Protokół, który kończy się przed wysłaniem jakichkolwiek wiadomości, jest reprezentowany przez drzewo zawierające tylko węzeł główny. Krawędzie od węzła do każdego dziecka są oznaczone wiadomościami wysłanymi w celu osiągnięcia stanu potomnego. Węzły liści reprezentują punkty, w których protokół się kończy.
Załóżmy, że istnieje niedeterministyczny protokół P, który rozwiązuje problem dwóch generałów. Następnie, za pomocą argumentu podobnego do argumentu używanego w powyższych protokołach deterministycznych o stałej długości, P ' musi również rozwiązać problem dwóch generałów, w którym drzewo reprezentujące P' jest uzyskiwane z drzewa P przez usunięcie wszystkich węzłów liści i krawędzi prowadzących do nich.
Ponieważ P jest skończone, wynika z tego, że protokół kończący się przed wysłaniem jakichkolwiek wiadomości rozwiązałby problem. Ale najwyraźniej tak nie jest. Dlatego niedeterministyczny protokół, który rozwiązuje ten problem, nie może istnieć.
Podejścia inżynieryjne
Pragmatyczne podejście do czynienia z dwoma generałami problemem jest schematów korzystania przyjmujących niepewność w komunikacyjnym kanale i nie próbuje go wyeliminować, ale raczej łagodzenia go do akceptowalnego poziomu. Na przykład pierwszy generał mógłby wysłać 100 posłańców, spodziewając się, że prawdopodobieństwo schwytania wszystkich jest niskie. Przy takim podejściu pierwszy generał zaatakuje bez względu na wszystko, a drugi generał zaatakuje, jeśli otrzyma jakąkolwiek wiadomość. Alternatywnie, pierwszy generał mógłby wysłać strumień wiadomości, a drugi generał mógłby wysłać każdemu z nich potwierdzenia, przy czym każdy generał czułby się bardziej komfortowo z każdą otrzymaną wiadomością. Jednak jak widać na dowodzie, żadne z nich nie może być pewne, że atak będzie skoordynowany. Nie ma algorytmu, którego mogliby użyć (np. Ataku, jeśli otrzymano więcej niż cztery wiadomości), który z pewnością zapobiegnie zaatakowaniu jednego bez drugiego. Ponadto pierwszy generał może wysłać oznaczenie na każdej wiadomości, mówiąc, że jest to wiadomość 1, 2, 3 ... z n. Ta metoda pozwoli drugiemu generałowi dowiedzieć się, jak niezawodny jest kanał i wysłać odpowiednią liczbę komunikatów z powrotem, aby zapewnić wysokie prawdopodobieństwo odebrania co najmniej jednej wiadomości. Jeśli kanał może być niezawodny, wystarczy jedna wiadomość, a dodatkowe wiadomości nie pomogą. Ten ostatni może się zgubić tak samo, jak pierwszy.
Zakładając, że generałowie muszą poświęcić życie za każdym razem, gdy posłaniec jest wysyłany i przechwytywany, można zaprojektować algorytm w celu zminimalizowania liczby posłańców potrzebnych do osiągnięcia maksymalnej pewności, że atak jest koordynowany. Aby uchronić ich przed poświęceniem setek istnień w celu uzyskania bardzo wysokiego zaufania do koordynacji, generałowie mogliby zgodzić się na wykorzystanie braku posłańców jako wskazówki, że generał, który rozpoczął transakcję, otrzymał przynajmniej jedno potwierdzenie i obiecał zaatakować. Załóżmy, że przekroczenie niebezpiecznej strefy zajmie posłaniecowi 1 minutę, a 200 minut ciszy po otrzymaniu potwierdzeń pozwoli nam osiągnąć niezwykle wysokie zaufanie, nie poświęcając życia posłańców. W tym przypadku komunikatory są używane tylko w przypadku, gdy strona nie otrzymała czasu ataku. Pod koniec 200 minut każdy generał może stwierdzić: „Nie otrzymałem dodatkowej wiadomości przez 200 minut; albo 200 posłańców nie przekroczyło strefy niebezpiecznej, albo oznacza to, że drugi generał potwierdził i zobowiązał się do ataku i ma zaufanie Też będę".
Historia
Problem dwóch generałów i jego niemożliwy dowód został po raz pierwszy opublikowany przez EA Akkoyunlu, K. Ekanadhama i RV Hubera w 1975 roku w „Some Constraints and Trade-offs in the Design of Network Communications”, gdzie jest opisany od strony 73 w kontekst komunikacji między dwiema grupami gangsterów.
Ten problem został nazwany Paradoksem Dwóch Generałów przez Jima Graya w 1978 r. W „Uwagach na temat systemów operacyjnych baz danych” zaczynającym się na stronie 465. Odniesienie to jest powszechnie podawane jako źródło definicji problemu i dowodu niemożliwości, chociaż oba zostały opublikowane wcześniej, jak wspomniano powyżej.