Problem bizantyjskich generałów

Problem bizantyjskich generałów – zagadnienie dotyczące uzgadniania rozważane w teorii gier, kryptografii oraz teorii systemów rozproszonych (w tym systemów wieloagentowych).

Wprowadzenie

Projektanci statków kosmicznych natrafili na problem zawodności systemów komputerowych. Aby zminimalizować ryzyko przekłamania, postanowiono zwielokrotnić wszystkie krytyczne elementy systemu. Jeżeli jakiś element przestaje pracować (nastąpi załamanie), to wykrycie takiej awarii jest proste – a istnienie nadmiarowych elementów pozwala na nieprzerwaną pracę. Trudności pojawiają się, jeśli wystąpi awaria bizantyjska: dany element nie przestanie pracować, a zacznie wysyłać błędne komunikaty. Jeśli założymy jeszcze, że np. różne procesory wykonują to samo zadanie za pomocą różnych programów (aby uodpornić się na błędy w oprogramowaniu) i może zajść sytuacja, że prawidłowo działające procesory podejmą różne decyzje, natrafiamy na poważny problem: jak uzgodnić ostateczną decyzję.

Sformułowanie problemu

Problem uzgadniania został bardzo obrazowo sformułowany jako problem bizantyjskich generałów w 1980 roku przez Marshalla Pease’a, Leslie Lamporta i Roberta Shostaka:

Grupa armii bizantyjskich otacza miasto nieprzyjaciela. Rozkład sił jest taki, że jeśli wszystkie armie zaatakują razem, to będą w stanie zdobyć miasto. Innym sposobem uniknięcia porażki jest odwrót wszystkich armii. Generałowie poszczególnych armii mają zaufanych posłańców, którzy z powodzeniem dostarczą każdy komunikat od jednego generała do innego. Jednak niektórzy generałowie mogą być zdrajcami usiłującymi doprowadzić do porażki armii bizantyjskich. Należy opracować algorytm, który umożliwi wszystkim wiernym generałom uzgodnienie pewnego planu działania. Ostateczna decyzja powinna być z grubsza taka, jaka zostałaby podjęta w drodze głosowania większościowego nad decyzjami poszczególnych generałów. W przypadku nierozstrzygnięcia głosowania końcową decyzją ma być odwrót^[1].

Generałowie oznaczają tu węzły systemu rozproszonego, posłańcy – kanały komunikacyjne. Zdrajca to węzeł, który nie pracuje prawidłowo. Algorytm uzgadniania musi spełniać dwa warunki^[2]:

1. Wszyscy wierni generałowie podejmują tę samą ostateczną decyzję
2. Niewielka liczba zdrajców nie może spowodować przyjęcia złej ostatecznej decyzji

Zła ostateczna decyzja to decyzja niezgodna z zamiarami większości wiernych generałów. Jeżeli wierni generałowie są podzieleni co do ataku lub odwrotu mniej więcej po połowie, żadnej z możliwych decyzji nie można nazwać złą. Możemy założyć, że wiemy, kiedy dojdzie do załamania – można to łatwo wykryć ustalając np. limit czasowy, po przekroczeniu którego, jeśli nie uzyskano komunikatu od któregoś generała, uznajemy, że doszło do załamania.

Problem dwóch generałów

Problem bizantyjskich generałów jest uogólnieniem problemu dwóch armii^[3] albo problemu dwóch generałów. Problem dwóch generałów dotyczy raczej zawodności kanałów komunikacyjnych, a nie uszkodzenia węzłów – odwrotnie niż problem bizantyjskich generałów, gdzie zakładamy, że kanały komunikacyjne są niezawodne – a problemem są węzły.

Sformułowanie oryginalne

Dwie bizantyjskie dywizje, dowodzone przez dwóch generałów, stoją po przeciwnych stronach wąwozu. W wąwozie znajdują się wrogowie, którzy nie wiedzą o okrążeniu. Generałowie wiedzą o sobie nawzajem, wiedzą też, że jeśli tylko jedna armia zaatakuje, silniejszy wróg wygra – muszą więc zaatakować jednocześnie.

1. Generał A wysyła posłańca do generała B z wiadomością: „Atakujemy o trzeciej w nocy”.
2. Generał B odsyła posłańca z potwierdzeniem „W porządku”.
3. Generał B myśli – „jeśli posłaniec nie dotarł do A, generał A nie zaatakuje. Muszę mieć potwierdzenie.” Wysyła posłańca do A z prośbą o potwierdzenie ataku.
4. Generał A przyjmuje posłańca i potwierdza atak.
5. Generał A boi się, że jeśli potwierdzenie nie dotrze do B, ten nie zaatakuje. Prosi więc o potwierdzenie dotarcia swojego posłańca.

I tak dalej.

Sformułowanie ścisłe

Rozważamy dwie komunikujące się strony – A i B.

Niech wiedzą pierwszego rzędu będzie wiedza na swój własny temat (lokalna wiedza danego agenta, w tym jego przekonania i intencje). Niech wiedzą ${\displaystyle n+1}$-go rzędu będą informacje na temat wiedzy ${\displaystyle n}$-tego rzędu u drugiej strony.

Problem bizantyjskich generałów można sformułować następująco:

Znaleźć metodę komunikacji pomiędzy A i B, która w warunkach niepewnego kanału komunikacyjnego zapewniłaby obydwu stronom uzgodnienie w skończonym czasie wspólnej wiedzy każdego rzędu ${\displaystyle n\in \mathbb {N} _{+}.}$

Rozwiązanie

W oryginalnej wersji problemu rozwiązanie nie istnieje. Problem dwóch generałów pokazuje, że konieczne jest albo ograniczenie wiedzy do pewnego rzędu, albo przeformułowanie problemu, np. przypisanie do informacji prawdopodobieństwa ich prawdziwości i tolerowanie pewnej niepewności (ustalenie minimalnego prawdopodobieństwa, powyżej którego wiedza nie wymaga weryfikacji).

Rozwiązania

Istnieje wiele algorytmów rozwiązujących problem bizantyjskich generałów. Jedynymi z bardziej istotnych są algorytm bizantyjskich generałów wymyślony przez twórców problemu oraz algorytm króla opracowany przez Piotra Bermana i Juana Garaya.

Algorytm bizantyjskich generałów

Algorytm ten, aby zmniejszyć wagę głosów zdrajców, przewiduje dodatkowe rundy wysyłania komunikatów. W pierwszej rundzie każdy generał przekazuje pozostałym własną decyzję, w następnych – informuje, czego dowiedział się od pozostałych.

W pierwszej rundzie każdy generał informuje każdego innego, jaką decyzję podjął. Otrzymane informacje (i swój głos) każdy z generałów przechowuje w tablicy, nazwijmy ją decyzja. W następnych rundach każdy z generałów przekazuje innym zawartość swojej tablicy decyzja. Generał nie musi przekazywać tablicy decyzja samemu sobie; nie musi też odsyłać innemu generałowi jego własnej decyzji. Jeżeli za ${\displaystyle t}$ weźmiemy liczbę zdrajców, do prawidłowego uzgodnienia potrzeba ${\displaystyle t+1}$ rund. Jednocześnie sumaryczna liczba wszystkich generałów (wiernych i zdrajców) musi wynieść co najmniej ${\displaystyle 3t+1.}$

Głosowanie także dokonuje się wieloetapowo. Najpierw dokonuje się wyboru większości spośród decyzji przekazanej bezpośrednio przez danego generała i uzyskanych od innych informacji o decyzji tego generała. Wynik głosowania uznaje się za prawdziwy głos danego generała i zapamiętuje w tablicy wybor_wiekszosciowy. Następnie podejmuje się ostateczną decyzję przez wybór większości z tablicy wybor_wiekszosciowy.

Wadą algorytmu bizantyjskich generałów jest bardzo duża liczba komunikatów potrzebnych, aby uzgodnić wspólną decyzję. Algorytm ma złożoność pod względem liczby komunikatów rzędu ${\displaystyle O(t^{4}),}$ co sprawia, że w przypadku większej liczby zdrajców przestaje się nadawać do praktycznego użytku.

Algorytm króla

Algorytm wymaga znacznie mniejszej liczby komunikatów niż algorytm bizantyjskich generałów. Jego wadą jest jednak konieczność istnienia większej liczby wiernych generałów. Jeżeli za ${\displaystyle t}$ przyjmiemy liczbę zdrajców, to musimy mieć co najmniej ${\displaystyle 4t+1}$ wszystkich generałów..

Algorytm bazuje na tym, że niewielka liczba zdrajców nie jest w stanie wpłynąć na ostateczne głosowanie, jeżeli na którąś z decyzji padła zdecydowana większość głosów. Algorytm nosi nazwę algorytmu króla, ponieważ w każdej rundzie jeden z generałów staje się królem i jego decyzja staje się ważniejsza niż reszty.

Rozważmy sytuację z jednym zdrajcą. Jeżeli dwaj kolejni generałowie grają rolę króla, to mamy pewność, że przynajmniej jeden z nich jest wierny. Jeżeli pierwszy wybrany król jest wierny, spowoduje on, że pozostali generałowie dojdą do porozumienia i nawet jeśli drugi król będzie zdrajcą, nie będzie mógł spowodować zmiany decyzji. Jeżeli pierwszy król jest zdrajcą, a wierny jest drugi król – to drugi król spowoduje dojście do porozumienia, a jako że nie będzie innych królów po nim – nikt nie zmieni już aktualnej decyzji.

W pierwszej rundzie algorytmu każdy generał podejmuje decyzję i rozsyła ją pozostałym. Dysponując pięcioma głosami każdy generał zapamiętuje wynik głosowania większościowego w zmiennej moja_wiekszosc. Dodatkowo zapisuje, ile głosów było za podjętą decyzję w zmiennej wiekszosc_glosow.

W drugiej rundzie król (i tylko on) przesyła swoją decyzję pozostałym generałom. Wybór króla odbywa się za pomocą dowolnego znanego wszystkim generałom algorytmu. Gdy generał otrzyma decyzję króla, sprawdza, iloma głosami została podjęta decyzja w poprzedniej rundzie, odczytując zmienną wiekszosc_glosow. Jeżeli większość była przeważająca (wiekszosc_glosow ma wartość większą od ${\displaystyle \lfloor n/2\rfloor +t}$), to decyzja króla jest ignorowana. W przeciwnym wypadku generałowie powinni zapomnieć o swoich poprzednich decyzjach i podporządkować się królowi. Następnie algorytm jest powtarzany drugi raz.

Algorytm można rozszerzyć na dowolną liczbę zdrajców. Jeżeli za ${\displaystyle t}$ podstawimy liczbę zdrajców, potrzebujemy ${\displaystyle t+1}$ par rund. Rząd złożoności pod względem wysyłanych komunikatów wynosi ${\displaystyle O(t^{3})}$

Brak rozwiązania dla 3 generałów

Niezależnie od wybranego algorytmu problem bizantyjskich generałów jest nierozwiązywalny dla sumarycznej liczby trzech generałów^[4][2] (z wyjątkiem modyfikacji problemu o możliwość podpisywania decyzji). Załóżmy następującą sytuację: Komunikat o decyzji przekazuje wierny generał Adam. Informuje on dwóch innych generałów, wiernego Bartosza i zdrajcę Celinę, że chce atakować. Jednakże zdrajca Celina przekazuje Bartoszowi, że Adam zarządził odwrót.

Bartosz dostaje dwa sprzeczne sygnały dotyczące decyzji Adama. Nie może rozstrzygnąć, który z generałów jest zdrajcą. Nie pomogą tu żadne dodatkowe komunikaty, ani rundy głosowań. Jeżeli zdrajca będzie konsekwentny, to z punktu widzenia Bartosza równie prawdopodobna jest sytuacja, kiedy to Adam jest zdrajcą:

Modyfikacje problemu

Modyfikacje problemu bizantyjskich generałów obejmują m.in.:

• komunikację po krawędziach grafu – np. A może się komunikować z B, a B z C, ale A z C – nie
• pisemne wiadomości – przekazywanie między generałami wiadomości podpisywanych niepodrabialnym podpisem (w tym wariancie możliwe jest rozwiązanie problemu dla 3 generałów)

Zastosowania

Zagadnienia podobne lub identyczne do problemu bizantyjskich generałów występują m.in. w:

• internecie – błędy przekazywania pakietów w sieci wymusiły powstanie protokołu TCP, który zapewnia uzgodnienie wiedzy drugiego rzędu,
• kryptografii – zagadnienia zbliżone do autoryzacji stron,
• elektronice – zagadnienia przekazywania danych w warunkach wysokich zakłóceń (fault tolerance), uzgadnianie wspólnych parametrów transmisji (handshake),
• systemach wieloagentowych – uzgadnianie wiedzy agentów,
• teorii gier – zagadnienia współpracy między kilkoma graczami.

Przypisy

1. Mordechai Ben-Ari: Podstawy programowania współbieżnego i rozproszonego. Warszawa: Wydawnictwa Naukowo-Techniczne, 2009, s. 238. ISBN 978-83-204-3441-5.
2. Leslie Lamport, Robert Shostak, Marshall Pease. The Byzantine Generals Problem. „ACM Transactions Programming Languages and System”. 4, 1982. (ang.). brak numeru strony
3. Zdzisław Płoski: Komputer, Internet: encyklopedyczny słownik szkolny. Wrocław: Europa, 2002, s. 355–356. ISBN 83-88962-10-8.
4. Mordechai Ben-Ari: Podstawy programowania współbieżnego i rozproszonego. Warszawa: Wydawnictwa Naukowo-Techniczne, 2009, s. 258–259. ISBN 978-83-204-3441-5.

Linki zewnętrzne

• The Byzantine Generals Problem (ang.)