Jeżeli za podstawimy liczbę zdrajców, potrzebujemy par rund. Rząd złożoności pod względem wysyłanych komunikatów wynosi
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 (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. Plik:3generałowie-rysunek1.svg
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ą: Plik:3generałowie-rysunek2.svg
Modyfikacje problemu Modyfikacje problemu bizantyjskich generałów obejmują m.in.: komunikację po krawędziach grafu – np.