###### tags: `prir` `studia`

# Problem bizantyjskich generałów

W systemach rozproszonych możliwe są **awarie**
- węzeł przestaje odpowiadać
- węzeł wysyła błędne komunikaty

Możliwe rozwiązania problemów:
- system przechodzi w stan bezpieczny, zapisuje stany i bezpiecznie kończy obliczenia
- system pozwala na dalszą pracę, prawdopodobnie spada wydajność

## Opis problemu
Grupa armii otacza miasto. Wszystkie grupy chcą jednocześnie zaatakować lub jednocześnie się wycofać. Inne akcje to porażka.

Niektórzy generałowie armii mogą być zdrajcami i chcieć doprowadzic do porazki.

### System rozproszony
Generałowie - węzły
Posłańcy - kanały komunikacyjne

### Rodzaje awarii węzłów

**załamanie** - zdrajca w dowolnej chwili przestaje wysyłać komunikaty
**awarie bizantyjskie** - zdrajca wysyła dowolne (w tym fałszywe) komunikaty

## Algorytm jednorundowy
Każdy generał przekazuje reszcie swoją decyzją - atak lub odwrót
Załóżmy generałów **A**, **B**, **C**.
Generałowie **A** oraz **B** są wierni, **C** jest zdrajcą (załamanie, przestanie przesyłać informacje)

**Co otrzyma generał A**
A : atak
B : odwrót
C : atak
_decyzja: atak_

**Co otrzyma generał B**
A : atak
B : odwrót
C ; BRAK
_decyzja: odwrót_

## Algorytm dwurundowy
W pierwszej rundzie generał przesyła innym swoją decyzję, w drugiej z kolei przesyła decyzje, jakie dostał w pierwszej od innych.

Następnie porównuje (np. tablicę decyzji) i większościową wybiera odpowiednią decyzję.

Decyzja ostatecznaDecyzja, decyzje[generalowie], wiekszosc[generalowie], przekazane[generalowie]

decyzja[mojId] = wybierzAtakLubOdwrot()

// runda 1
po wszystkich innych generałach G:
    send(G, decyzje[mojId])
    receive(G, decyzje[G])
    
// runda 2
po wszystkich innych generałach G:
    
    KURWA ILE KODU

Niweluje **załamanie** ale nie powstrzyma **awarii bizantyjskiej**

**W przypadku załamania**
W dwurundowym wymaga się, w przypadku T zdrajców aż 2T+1 generałów

**W przypadku awarii bizantyjskiej**
Algorytm dwurundowy poprawny dla minimum 4 generałów, gdzie tylko 1 jest zdrajcą

Dla T zdrajców potrzeba T+1 rund oraz 3T+1 generałów.

Jeśli założymy że jedyną awarią jest załamanie to stosujemy **algorytm rozpływowy**
- każdy generał kilkukrotnie rozsyła i odbiera zbiór otrzymanych decyzji
- dla T zdrajców wystarczy T+1 rund

## Algorytm króla
Wymaga aby przy T zdrajcach było 4T+1 generałów.

- w każdej rundzie jeden generał zostaje królem i jego głos jest ważniejszy od reszty

Runda pierwsza:
- każdy przesyła każdemu swoją decyzję
- każdy zapamiętuje wynik głosowania większościowego oraz ilość głosów, którą zdobyła opcja większości

Runda druga:
- tylko król przesyła swoją decyzje reszcie
- gdy generał otrzyma decyzję od króla, sprawdza, iloma głosami była wybrana decyzja w pierwszej rundzie. Jeśli większość była znacząca (większa niż [n/2] + t) to ignoruje decyzję króla. W przeciwnym wypadku generałowie zapominają o pierwszej rundzie i podporządkowują się królowi
- następnie algorytm powtarzany jest drugi raz