Odporność na błędy (fault tolerance)¶

Są 2 rodzaje błędów sieci: złośliwe i łagodne (ang. benign)

1. łagodne – wierz lub kraw przestaje działać „na zawsze” (np. "crash" procesorów)
2. złośliwe - wierz lub kraw(?) zachowuje się w sposób nieprzewidywalny

Problemy które rozważymy:

1. problem 2 generałów (atakujących miasto z przeciwnych stron)
2. consensus (wszyscy muszą się zgodzić na tą samą liczbę)

problem 2 generałów (coordinated attack problem) - form. def.¶

chodzi o podjęcię wspólnej decyzji o ataku...
psują się połączenia (komunikaty nie są dostarczane)
$x_i$ – chęć $P_i$, $y_i$ – ostateczna decyzja $P_i$
formalnie: mamy 2 procesory $P_1$ i $P_2$; mają być spełnione warunki:

1. „agreement”, $y_1=y_2$, czyli wspólna decyzja...
2. „validity”, if $x_1=x_2=0$, żaden kom. nie został dost., to $y_1=y_2=0$
3. „nontriviality”, istnieje egzekucja, w której $y_1=y_2=1$

consensus - form. def.¶

każdy procesor $P_i$ ma liczbę $x_i$ na wejściu,
chodzi o wybranie wspólnej liczby $y_i$ spośród $x_i$,
przez te proc które się nie popsuły („crash” procesorów)
formalnie: mamy procesory P1, .., Pn; mają być spełnione warunki:

1. „agreement”, $y_i=y_j$ dla wsz niepopsutych Pi, Pj
2. „validity”, $y_i$ in {$x_1$, ..., $x_n$}, dla wsz niepopsutych Pi

problem 2 generałów¶

przypomnieć pojęcie egzekucji asynch (konfiguracja początkowa i ciag zdarzeń) ...

Tw: nie istnieje alg rozwiązujący problem 2 generałów
Dowód:
def: a|P = egzekucja „a” z pkt widzenia procesora P
def: $a_1$/P/$a_2$ = egz $a_1$ i $a_2$ są nierozróżnialne z pkt widzenia P
Zakładamy, że alg istnieje, czyli istnieje egz $b_1$, w której
dostarcza się „k” komunikatów oraz $y_1=y_2=1$ (z nontriviality).
Konstruujemy egzekucje $a_k$, która wygląda tak:

Zauważmy, że:
$b_1$/P1/$a_k$ oraz w $a_k$ dostarcza się $k-1$ kom, $y_1=y_2=1$ (?)
Następnie tworzymy egz $a_{k-1}$ z $a_k$ analogicznie (jak $a_k$ z $b_1$)
czyli w $a_{k-1}$ dostarcza się $k-2$ kom, $y_1=y_2=1$
…
w $a_1$ dostarcza się 0 kom, $y_1=y_2=1$,
czy to już sprzeczność z validity ?
NIE, no nie wiemy czy w 1 konfiguracji było $x_1=x_2=0$ ?!?!
Konstruujemy egz $b'_0$ = "$a_1$ z tą zmianą, że $x_1=0$"
$a_1$/P2/$b'_0$ => w egz $b'_0$: $y_1=y_2=1$ (P2 nie widzi innej wart $x_1$)
Konstruujemy egz $b_0$ = "$b'_0$ z tą zmianą, że $x_2=0$"
$b'_0$/P1/$b_0$ => w egz $b_0$: $y_1=y_2=1$ (P1 nie widzi innej wart $x_2$)
tzn. $b_0$ jest egz w której $x_1=x_2=0$, $y_1=y_2=1$, dostarcza się 0 kom...
SPRZECZNOŚĆ z validity !!!

consensus¶

algorytm "obliczający" consensus:

oraz główne Twierdzenie:

pierwszy proces ma x na WE...
„iteracje”: w której dany proces dostaje x, oraz go wysyła w następnej iteracji (ew. crash) !
Są 2 możliwości:

1. przedostatni proces się psuje – sprzeczność (co do f) !!!
2. -''- się NIE psuje – wysyła x do Pj

Intuicja algorytmu consensus: wysyłam cenna informację gdzie się da, może przetrwa...

...

Zadania¶

ZADANIE 50 impl algorytmu consensus
Zaprojektuj eksperyment pokazujący nietrywialne działanie algorytmu Consensus...
Nasz symulator nie jest przystosowany do algorytmow synch "psujących się w połowie rundy",
dlatego najlepiej użyc proc blad {iter1 iter2} generującej błąd fibera przy pomocy error "crash",
w odpowiednio dobranej chwili (patrz tutaj),
Uwaga: przez "nietrywialne działanie" rozumiemy takie, w którym coś się zmienia
także w ostatnich iteracjach pętli for...