Problem generałów bizantyjskich opisuje serwer, który może okłamywać różnych sąsiadów na różne sposoby
Awaria nie zawsze oznacza, że komputer się wyłączył. W modelu bizantyjskim wadliwy uczestnik może zachowywać się dowolnie: wysyłać sprzeczne wiadomości, udawać poprawne działanie albo przekazywać różne informacje różnym węzłom. Lamport, Shostak i Pease pokazali, jak trudne jest osiągnięcie uzgodnienia w takim świecie. W klasycznym wariancie bez uwierzytelnionych wiadomości, aby tolerować `m` bizantyjskich zdrajców, potrzeba co najmniej `3m+1` uczestników. Nazwa brzmi historycznie, ale problem dotyczy realnego pytania: jak uzgodnić wspólny stan, gdy część maszyn może nie tylko zamilknąć, ale aktywnie wprowadzać pozostałe w błąd.
Crash jest prostszą awarią niż kłamstwo
Gdy serwer przestaje działać, nie wysyła już nowych sprzecznych informacji. Pozostali mogą stracić jego głos, ale przynajmniej nie muszą analizować dwóch różnych historii podpisanych przez tę samą maszynę. Awaria bizantyjska jest znacznie silniejszym modelem: wadliwy proces może wysłać A wiadomość „atak”, a B wiadomość „odwrót”.
Generałowie są metaforą uzgodnienia
W klasycznym artykule kilku dowódców musi uzgodnić wspólne działanie, komunikując się przez posłańców. Część dowódców może być zdrajcami. Warunek nie polega tylko na tym, aby lojalni uczestnicy wybrali sensowną decyzję, lecz aby wszyscy lojalni skończyli z tym samym wynikiem mimo sprzecznych komunikatów wysyłanych przez zdrajców.
Skąd bierze się granica 3m+1
Lamport, Shostak i Pease wykazali, że przy tzw. oral messages — wiadomościach bez podpisów pozwalających niezależnie dowieść ich pochodzenia — rozwiązanie tolerujące `m` zdrajców wymaga co najmniej `3m+1` uczestników. Intuicyjnie problem polega na tym, że poprawni uczestnicy muszą mieć wystarczająco dużą przewagę liczebną, aby sprzeczne relacje wadliwych węzłów nie stworzyły dwóch równie wiarygodnych obrazów sytuacji.
Podpisy cyfrowe zmieniają problem
Ten sam artykuł pokazuje, że dodatkowe założenia o wiadomościach mogą radykalnie zmienić możliwości systemu. Jeżeli uczestnicy mogą posługiwać się niepodrabialnymi podpisami, wadliwy węzeł nie może dowolnie przypisywać innym autorstwa wiadomości. To dobry przykład ogólniejszej zasady: wynik algorytmu rozproszonego zależy od modelu awarii i od tego, jakie właściwości kanału komunikacji uznajemy za pewne.
Dlaczego problem jest aktualny
Modele bizantyjskie pojawiają się w systemach, w których trzeba uwzględniać złośliwych lub całkowicie wadliwych uczestników, np. w części protokołów blockchain i systemach o bardzo wysokich wymaganiach odporności. Nie każdy klaster bazy danych potrzebuje tak silnego modelu. W zwykłym centrum danych często zakłada się prostsze awarie typu crash, bo odporność bizantyjska kosztuje dodatkową komunikację i złożoność.
Model awarii dobiera się do zagrożenia
Odporność bizantyjska jest droga, dlatego nie należy stosować jej automatycznie. W zamkniętym klastrze jednej organizacji często rozsądniejsze jest założenie, że maszyny mogą się zawiesić lub stracić łączność, ale nie będą świadomie fałszować komunikatów. W systemie otwartym, w którym uczestnicy nie ufają sobie nawzajem, model bizantyjski staje się znacznie bardziej adekwatny. Projekt algorytmu zaczyna się więc od threat modelu, a nie od wyboru najbardziej imponującego protokołu.
Nazwa przetrwała, bo dobrze pokazuje problem informacji
Lamport świadomie ubrał problem w historię o generałach, bo metafora ułatwia zrozumienie trudności. Każdy lojalny uczestnik musi podjąć tę samą decyzję na podstawie wiadomości, z których część może być celowo sprzeczna. To nie jest problem „większość wygra głosowanie” w zwykłym sensie, bo zdrajca może przedstawić inny obraz głosowania każdemu odbiorcy. Sednem jest osiągnięcie wspólnej wiedzy mimo niewiarygodnych źródeł.
Współczesne systemy często łączą kryptografię z protokołami BFT, dzięki czemu odbiorca może zweryfikować autorstwo i integralność komunikatu. Podpis nie sprawia jednak, że kłamliwy uczestnik nagle zaczyna mówić prawdę; zmienia tylko to, czego może się wyprzeć i jakie sprzeczności da się udowodnić innym. To dobry przykład różnicy między bezpieczeństwem komunikacji a wiarygodnością uczestnika. Szyfrowanie i podpisy rozwiązują część problemu, ale algorytm nadal musi zdecydować, jak osiągnąć wspólny wynik mimo nieuczciwych głosów.