Problem bizantyjskich generałów

Problem (paradoks) bizantyjskich generałów - zagadnienie rozważane w teorii gier, kryptografii oraz teorii systemów rozproszonych (w tym systemów wieloagentowych).

Problem dwóch generałów

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ą n + 1-go rzędu będą informacje na temat wiedzy 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 .

Rozwiązanie

W oryginalnej wersji problemu rozwiązanie nie istnieje. Problem bizantyjskich 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).

Uogólnienia problemu

Uogólnienia problemu obejmują m.in.

• ograniczenie rzędu wiedzy
• komunikację między większą liczbą stron,
• komunikację po krawędziach grafu - np. A może się komunikować z B, a B z C, ale A z C - nie.
• wprowadzenie zdrajców - stron, które starają się nie dopuścić do porozumienia.

Takie uogólnione problemy znajdują już często rozwiązanie, o ile wymagany rząd uzgodnionej wiedzy jest skończony.

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

Linki zewnętrzne

• (en) The Byzantine Generals Problem