dr inż. Arkadiusz Danilecki
W oparciu o wykłady prof. J. Brzezińskiego
Nieformalnie, konsensusem nazywa się problem uzgadniania przez zbiór procesów jednej wartości spośród zbioru wartości zaproponowanych wstępnie przez te procesy.
Nieformalnie (ale już nieco mniej nieformalnie), w konsensusie wszystkie poprawne procesy (albo wszystkie w wersji silniejszej, uściślimy później) wybierają tę samą wartość, nawet jeżeli niektóre procesy ulegają awariom.
WAŻNE - zakładamy, że zawsze chociaż jeden proces jest poprawny
Konsensus jest przykładem klasy problemów nazywanych zbiorczo problemami uzgadniania.
Przykładem takich problemów są:
Wszystkie problemy uzgadniania są rozwiązywalne w trywialny sposób, gdy wszystkie procesy są poprawne.
Wszystkie problemy uzgadniania są rozwiązywalne w trywialny sposób, gdy wiadomo z góry, które procesy są błędne.
Wiele innych problemów (uzgadnianie i nie tylko) jest w trywialny sposób rozwiązywalna, jeżeli możemy użyć działającego mechanizmu rozwiązującego konsensus.
Problem konsensusu można także rozwiązać, mając do dyspozycji mechanizmy rozwiązujące inne problemy (uzgadniania i nie tylko).
Czy można rozwiązać problem konsensusu, mając do dyspozycji mechanizm zapewniający wzajemne wykluczania, na przykład...
WAŻNOŚĆ - jeżeli proces $\displaystyle P_{i}$ decyduje się na wartość $v_i$, to wartość tę zaproponował jakiś inny proces.
ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość
INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz
ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości
Które z tych własności są własnościami postępu, a które bezpieczeństwa?
Twierdzenie (Fisher, Lynch, Patterson)
Problem konsensusu nie ma rozwiązania w systemie w pełni asynchronicznym, jeżeli chociaż jeden proces może ulec awarii.
Twierdzenie
Problem konsensusu nie ma rozwiązania w systemie z synchronicznymi kanałami i asynchronicznymi procesami, jeżeli chociaż jeden proces może ulec awarii.
Twierdzenie
Problem konsensusu nie ma rozwiązania w systemie z asynchronicznymi kanałami i synchronicznymi procesami, jeżeli chociaż jeden proces może ulec awarii.
W praktyce istniejące systemy rozproszone nie są w pełni asynchroniczne. Można więc rozwiązać w nich problem konsensusu, o ile nie będziemy się za bardzo upierali przy zapewnianiu własności postępu (żywotności).
Przykład praktyczny: algorytmy Paxos oraz Raft.
Skoro problem rozwiązywalności wynika z niemożliwości rozróżnienia procesów wolnych od tych, które uległy awarii, to czy detektory pomogą?
TAK!
Problem konsensusu ma rozwiązanie w systemie asynchronicznym o ile jest dostępny detektor awarii klasy P (doskonały detektor awarii)
Problem konsensusu ma rozwiązania w systemie asynchronicznym o ile jest dostępny detektor awarii klasy $\Diamond W$ (ostatecznie słaby detektor awarii) i jeżeli nie więcej niż jedna trzecia procesów ulega awarii ($n > \mbox{2}f$)
KONCEPCJA
Algorytm działa w rundach. Decyzja podejmowana jest, gdy proces otrzyma wiadomości od wszystkich poprawnych procesów i nie wykrył żadnej nowej awarii.
Jeżeli wykryta została awaria, proces nie ma pewności, czy posiadany przez niego zbiór wartości propozycji jest taki sam, jak widziany przez wszystkie pozostałe procesy.
KONCEPCJA
Algorytm działa w rundach. Decyzja podejmowana jest, gdy proces otrzyma wiadomości od wszystkich poprawnych procesów i nie wykrył żadnej nowej awarii.
Jeżeli wykryta została awaria, proces nie ma pewności, czy posiadany przez niego zbiór wartości propozycji jest taki sam, jak widziany przez wszystkie pozostałe procesy.
Różnica może mieć na przykład miejsce, jeżeli jakiś błędny proces zdążył przesłać wiadomość tylko do części pozostałych procesów. W takim wypadku rozpoczynana jest kolejna runda.
Do podjęcia decyzji używana jest dowolna deterministyczna funkcja, znana wszystkim procesom.
message ~~proposal~~ is a struct of ~~\langle~~set of int ~~values~~, int ~~roundNo \rangle~~
message ~~decision~~ is a struct of ~~\langle~~int ~~value~~, int ~~roundNo \rangle~~
local int $roundNo_i$ := 1
local int $decided_i$ := $nil$
local set of int $proposalSet_i$ := $\emptyset$
local set of processes $correct_i$ := $\mathcal{P}$
local set of processes $correctLastRound_i$ := $\mathcal{P}$
local set of processes $correctThisRound_i$ := $\emptyset$
ZAŁOŻENIE: używamy podstawowego rozgłaszania niezawodnego (ang. best-effort bcast)
when process ~~P_i~~ proposes a value ~~v_i~~ do
~~proposalSet_i~~ := ~~\{ v_i \}~~
broadcast ~~proposal\langle values :\{ v_i \}, roundNo_i \rangle~~ to ~~\mathcal{P}~~
end when
when a message ~~proposal~~ arrives at ~~{P}_{i}~~ from ~~{P}_{j}~~ do
~~proposalSet_i \xleftarrow{append} proposal.values~~
~~correctThisRound_i \xleftarrow{append} \{ P_j \}~~
end when
ZAŁOŻENIE: używamy podstawowego rozgłaszania niezawodnego (ang. best-effort bcast)
when ~~correct_i \subseteq correctThisRound_i \land decided_i = nil~~ at ~~P_i~~ do
if ~~correctThisRound_i = correctLastRound_i~~ then
~~decided_i~~ := MIN( $proposalSet_i$)
decide ~~decided_i~~
broadcast ~~decision\langle decided_i, roundNo_i\rangle~~ to ~~\mathcal{P}~~
else
~~roundNo_i~~ := ~~roundNo_i~~ + 1
~~correctLastRound_i~~ := ~~correctThisRound_i~~
~~correctThisRound_i~~ := ~~\emptyset~~
broadcast ~~proposal\langle proposalSet_i, roundNo_i\rangle~~ to ~~\mathcal{P}~~
end if
end when
ZAŁOŻENIE: dostępny jest doskonały detektor awarii $FD_i$
when a message ~~decision~~ arrives at ~~{P}_{i}~~ from ~~{P}_{j}~~ do
if ~~decided_i = nil~~ then
~~decided_i~~ := ~~decision.value~~
decide ~~decided_i~~
broadcast ~~decision\langle decided_i, roundNo_i + 1\rangle~~ to ~~\mathcal{P}~~
end if
end when
when $FD_i$ starts suspecting $P_j$ do
$correct_i$ := $correct_i \setminus P_j$
end when
ZŁOŻONOŚĆ KOMUNIKACYJNA CZASOWA
Przypadek optymistyczny pesymistyczny
Brak awarii : wszyscy wysyłają $n$ propozycji i tyle samo decyzji, a więc $2 * n^2$.
ZŁOŻONOŚĆ KOMUNIKACYJNA CZASOWA
Przypadek optymistyczny pesymistyczny
Brak awarii : wszyscy decydują po pierwszej rundzie (decyzje innych są potem ignorowane, bo już sami podjęliśmy decyzję)
ZŁOŻONOŚĆ KOMUNIKACYJNA CZASOWA
Przypadek optymistyczny pesymistyczny
Najwięcej awarii jak się da : $n$ - 1 awarii, za każdym razem ktoś otrzymuje, rozgłasza i ulega awarii, inni to wykrywają i przechodzą do nowej rundy pakiet dociera do jednego procesu czyli $n$ rund
ZŁOŻONOŚĆ KOMUNIKACYJNA CZASOWA
Przypadek optymistyczny pesymistyczny
Najwięcej awarii jak się da : $n$ - 1 awarii, za każdym razem ktoś otrzymuje, rozgłasza i ulega awarii, inni to wykrywają i przechodzą do nowej rundy pakiet dociera do jednego procesu czyli $n$ rund, w każdej $n^2$ propozycji (plus decyzja na końcu), a więc $O(n^3)$
DOWÓD POPRAWNOŚCI
WAŻNOŚĆ - jeżeli proces $\displaystyle P_{i}$ decyduje się na wartość $v_i$, to wartość tę zaproponował jakiś inny proces.
ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość
INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz
ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości
WAŻNOŚĆ - jeżeli proces $\displaystyle P_{i}$ decyduje się na wartość $v_i$, to wartość tę zaproponował jakiś inny proces.
DOWÓD
Wartość decyzji $P_i$ jest wybierana ze zbioru $proposalSet_i$. Do tego zbioru są dodawane jedynie wartości zaproponowane przez $P_i$ lub jakieś inne procesy.
ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość
INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz
ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości
INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz
DOWÓD
$P_i$ podejmuje decyzję tylko i wyłącznie, jeżeli $decided_i = nil$ i nigdy już tej decyzji nie zmienia (linijki 12 oraz 29)
WAŻNOŚĆ - jeżeli proces $\displaystyle P_{i}$ decyduje się na wartość $v_i$, to wartość tę zaproponował jakiś inny proces.
ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość
ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości
ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość
DOWÓD
$P_i$ czeka w linijce 12, de facto do czasu aż dla każdego procesu - albo otrzyma od niego wiadomość (a więc proces ten będzie dopisany do $correctThisRound_i$, linijka 10), albo proces ten zostanie uznany za niepoprawny (proces zostanie usunięty ze zbioru $correct_i$)
INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz
WAŻNOŚĆ - jeżeli proces $\displaystyle P_{i}$ decyduje się na wartość $v_i$, to wartość tę zaproponował jakiś inny proces.
ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości
ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość
DOWÓD
Wszystkie procesy wysyłają swoje propozycje na początku każdej rundy, a z własności podstawowego rozgłaszania niezawodnego, jeżeli te procesy będą poprawne, wiadomości od nich ostatecznie dotrą do $P_i$.
Jeżeli w danej rundzie nie będzie awarii, proces $P_i$ otrzyma więc wszystkie propozycje ze zbioru $correct_i$ (a więc $correct_i \subseteq correctThisRound_i$ oraz $correctThisRound_i = correctLastRound_i$) i podejmie decyzję (I).
INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz
WAŻNOŚĆ - jeżeli proces $\displaystyle P_{i}$ decyduje się na wartość $v_i$, to wartość tę zaproponował jakiś inny proces.
ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości
ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość
DOWÓD
Jeżeli jakiś proces $P_j$ ulegnie awarii, z własności doskonałego detektora awarii $P_i$ ostatecznie to wykryje i usunie $P_j$ ze zbioru $correct_i$, a więc przestanie czekać na wiadomość od niego i przejdzie do nowej rundy.
Jeżeli proces $P_i$ wykryje awarię, wszystkie inne działające procesy też ostatecznie wykryją tę awarię i przejdą do nowej rundy, rozsyłając propozycje. Analizę powtarzamy rekurencyjnie.
INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz
WAŻNOŚĆ - jeżeli proces $\displaystyle P_{i}$ decyduje się na wartość $v_i$, to wartość tę zaproponował jakiś inny proces.
ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości
ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość
DOWÓD
Sytuacja ta nie może się powtarzać w nieskończoność, bo procesy usunięte z $correct_i$ nigdy nie mogą być do niego dodane, skoro mamy doskonały detektor awarii, który nigdy się nie myli. Ostatecznie więc nie będzie nowych awarii; zakładając, że istnieje co najmniej jeden poprawny proces, w najgorszym razie on sam do siebie wyśle propozycje, a skoro pozostanie jedynym w zbiorze $correct_i$, nie będzie nowych awarii, to ostatecznie podejmie decyzję (II)
INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz
WAŻNOŚĆ - jeżeli proces $\displaystyle P_{i}$ decyduje się na wartość $v_i$, to wartość tę zaproponował jakiś inny proces.
ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości
ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość
DOWÓD
Widzimy więc, że ostatecznie każdy poprawny proces zdecyduje się na jakąś wartość albo w punkcie (I) albo (II) - czyli albo gdy w rundzie nie było nowej awarii, albo najpóźniej gdy wszystkie inne procesy ulegną awarii i nie będzie już nowych rund.
INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz
WAŻNOŚĆ - jeżeli proces $\displaystyle P_{i}$ decyduje się na wartość $v_i$, to wartość tę zaproponował jakiś inny proces.
ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości
ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości
DOWÓD
Decyzja jest podejmowana deterministycznie, a więc dwa procesy mające te same zbiory propozycji muszą wybrać tę samą wartość jako decyzję.
W danej turze dla każdego $P_j$, $P_i$ czeka na propozycję albo decyzję $P_j$, albo na uznanie $P_j$ za niepoprawnego.
ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość
INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz
WAŻNOŚĆ - jeżeli proces $\displaystyle P_{i}$ decyduje się na wartość $v_i$, to wartość tę zaproponował jakiś inny proces.
ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości
DOWÓD
W danej rundzie dla każdego $P_j$, $P_i$ czeka na propozycję albo decyzję $P_j$, albo na uznanie $P_j$ za niepoprawnego.
Jeżeli jakiś proces $P_j$ ulegnie awarii, przyjście wiadomości od $P_j$ musiałoby skutkować wstawieniem $P_j$ z powrotem do $correct_i$, a więc pomyłką, a przecież zakładamy, że detektor jest doskonały i się nie myli! A więc zakładamy, że po usunięciu $P_j$ z $correct_i$ nie otrzymamy od niego już żadnej wiadomości.
ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość
INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz
WAŻNOŚĆ - jeżeli proces $\displaystyle P_{i}$ decyduje się na wartość $v_i$, to wartość tę zaproponował jakiś inny proces.
ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości
DOWÓD
Decyzję procesy mogą podjąć albo, jeżeli w danej rundzie nie wykryją żadnej nowej awarii (I) albo gdy otrzymają decyzję od innego procesu (II).
Przypomnienie: w każdej rundzie czekam na propozycję, decyzję lub awarię każdego innego procesu!
ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość
INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz
WAŻNOŚĆ - jeżeli proces $\displaystyle P_{i}$ decyduje się na wartość $v_i$, to wartość tę zaproponował jakiś inny proces.
ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości
DOWÓD
Jeżeli proces $P_i$ podejmie decyzję w danej rundzie, to musiał nie wykryć żadnej nowej awarii i otrzymać wiadomości od wszystkich procesów uznawanych za poprawne w poprzedniej turze.
Dla każdego innego procesu $P_j$, zachodzi:
ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość
INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz
WAŻNOŚĆ - jeżeli proces $\displaystyle P_{i}$ decyduje się na wartość $v_i$, to wartość tę zaproponował jakiś inny proces.
ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości
DOWÓD
Dla każdego innego procesu $P_j$, zachodzi:
ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość
INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz
WAŻNOŚĆ - jeżeli proces $\displaystyle P_{i}$ decyduje się na wartość $v_i$, to wartość tę zaproponował jakiś inny proces.
ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości
DOWÓD
Dla każdego innego procesu $P_j$, zachodzi:
ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość
INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz
WAŻNOŚĆ - jeżeli proces $\displaystyle P_{i}$ decyduje się na wartość $v_i$, to wartość tę zaproponował jakiś inny proces.
ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości
DOWÓD
Dla każdego innego procesu $P_j$, zachodzi:
W tym przypadku więc wszystkie procesy, które podejmą decyzję, decydują się na tę samą wartość.
ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość
INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz
WAŻNOŚĆ - jeżeli proces $\displaystyle P_{i}$ decyduje się na wartość $v_i$, to wartość tę zaproponował jakiś inny proces.
ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości
DOWÓD
Jeżeli proces $P_i$ podejmie decyzję w danej rundzie, rozgłosił ją i uległ awarii, to jeżeli żaden inny proces nie otrzymał jego decyzji, nic się nie stało - interesują nas tylko decyzje procesów poprawnych. A jeżeli część dostała decyzję, a część nie?
ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość
INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz
WAŻNOŚĆ - jeżeli proces $\displaystyle P_{i}$ decyduje się na wartość $v_i$, to wartość tę zaproponował jakiś inny proces.
ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości
DOWÓD
Jeżeli $P_i$ jest niepoprawny, jego decyzja mogła nie dotrzeć do wszystkich procesów. Załóżmy, że dotarła do jakiegoś $P_j$, który decyduje się na wartość od $P_i$ i rozgłasza decyzję.
Pozostałe procesy ostatecznie wykryją awarię $P_i$ i przejdą do nowej rundy nie podejmując decyzji. W następnej turze muszą czekać na wiadomość od $P_j$, a więc albo otrzymają decyzję $P_j$ i podejmą taką samą decyzję, albo $P_j$ ulegnie awarii, co tamte ostatecznie wykryją i przejdą do nowej tury nie podejmując decyzji.
ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość
INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz
WAŻNOŚĆ - jeżeli proces $\displaystyle P_{i}$ decyduje się na wartość $v_i$, to wartość tę zaproponował jakiś inny proces.
ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości
DOWÓD
Przez rekurencję - albo decyzja w końcu dotrze do jakiegoś poprawnego procesu i wtedy wszystkie poprawne procesy podejmą tę samą decyzję; albo nie dotrze do żadnego poprawnego procesu, wtedy tę decyzję podejmą tylko procesy niepoprawne, a takie w konsensusie podstawowym nas nie obchodzą
Widać z tego, że w obu przypadkach, w których jakiś poprawny proces podejmie decyzję - wszystkie inne poprawne procesy też podejmą taką samą decyzję.
ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość
INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz
WAŻNOŚĆ - jeżeli proces $\displaystyle P_{i}$ decyduje się na wartość $v_i$, to wartość tę zaproponował jakiś inny proces.
PYTANIE SPRAWDZAJĄCE
A co jeżeli dwa procesy ulegną awarii: $P_k$ oraz $P_l$. $P_i$ otrzymał propozycję od $P_k$ i wykrył awarię $P_l$, zaś $P_j$ wykrył awarię $P_k$ oraz dostał propozycję od $P_l$? Czy mogą podjąć wtedy różne decyzje?
Zarówno procesy $P_i$ jak i $P_j$ muszą przejść do nowej rundy (skoro wykryły nową awarię). W następnej rundzie zaś wysyłają $proposalSet$ zawierający otrzymane propozycje.
ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości
ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość
INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz
WAŻNOŚĆ - jeżeli proces $\displaystyle P_{i}$ decyduje się na wartość $v_i$, to wartość tę zaproponował jakiś inny proces.
KONCEPCJA
Algorytm działa w rundach. W każdej rundzie lider rozgłasza swoją decyzję. Inni tą decyzję przyjmują jako swoją propozycję i czekają na swoją rundę, by zadecydować.
Nowa runda zaczyna się po otrzymaniu decyzji poprzedniego lidera albo wykryciu jego awarii przy pomocy doskonałego detektora awarii.
message ~~decision~~ is a struct of ~~\langle~~int ~~value~~, int ~~roundNo \rangle~~
local int $roundNo_i$ := 1
local int $propRoundNo_i$ := 0
local int $decided_i$ := $nil$
local array of int $delivered_i\left[1 \ldots n\right]$ := $\{ false, \ldots false\}$
local array of int $bcast_i\left[1 \ldots n\right]$ := $\{ false, \ldots false\}$
local set of processes $suspected_i$ := $\emptyset$
local array of processes $liderSet_i$ := $\{ P_1, P_2, \ldots P_n \}$
ZAŁOŻENIE: dostępny jest doskonały detektor awarii $FD_i$
when process ~~P_i~~ proposes a value ~~v_i~~ do
~~proposal_i~~ := ~~ v_i ~~
end when
when $FD_i$ starts suspecting $P_j$ do
$suspected_i \xleftarrow{append} P_j$
end when
ZAŁOŻENIE: używamy podstawowego rozgłaszania niezawodnego (ang. best-effort bcast)
when ~~liderSet_i[roundNo_i] = P_i \land proposal\not= nil \land bcast_i[i] = \mbox{false}~~ do
~~bcast_i[i]~~ := true
decide ~~proposal_i~~
~~decision.roundNo~~ := ~~roundNo_i~~
~~decision.value~~ := ~~decided_i~~
broadcast ~~decision~~ to ~~\mathcal{P}~~
end when
ZAŁOŻENIE: używamy podstawowego rozgłaszania niezawodnego (ang. best-effort bcast)
when ~~liderSet_i[roundNo_i] \in suspected_i \lor delivered_i[roundNo_i] = \mbox{true}~~ do
~~roundNo_i = roundNo_i + \mbox{1}~~
end when
when a message ~~decision~~ arrives at ~~{P}_{i}~~ from ~~{P}_{j}~~ do
if ~~i > decision.roundNo > propRoundNo_i~~ then
~~proposal_i~~ := ~~decision.value~~
~~propRoundNo_i~~ := ~~decision.roundNo~~
end if
~~delivered_i[decision.roundNo]~~ := true
end when
ZŁOŻONOŚĆ KOMUNIKACYJNA CZASOWA
Przypadek optymistyczny pesymistyczny
Brak awarii : lider wysyła wszystkim $n$ decyzji, rund jest $n$ a więc $n^2$.
Kontrowersyjne - wszyscy ulegli awarii od razu oprócz jednego. Lider wysyła wszystkim $n$ decyzji, rund jedna, a więc $n$.
ZŁOŻONOŚĆ KOMUNIKACYJNA CZASOWA
Przypadek optymistyczny pesymistyczny
Brak awarii : wszyscy decydują w swojej rundzie po otrzymaniu decyzji poprzedniego lidera więc $n$
ZŁOŻONOŚĆ KOMUNIKACYJNA CZASOWA
Przypadek optymistyczny pesymistyczny
Najwięcej awarii jak się da : $n$ - 1 awarii, za każdym razem ktoś otrzymuje, rozgłasza i ulega awarii, inni to wykrywają i przechodzą do nowej rundy, wreszcie pakiet dociera do ostatniego procesu czyli - i tak $n$ rund
ZŁOŻONOŚĆ KOMUNIKACYJNA CZASOWA
Przypadek optymistyczny pesymistyczny
Najwięcej awarii jak się da : $n$ - 1 awarii, za każdym razem ktoś otrzymuje, rozgłasza i ulega awarii, inni to wykrywają i przechodzą do nowej rundy, wreszcie pakiet dociera do ostatniego procesu czyli $n$ rund, w każdej $n$ propozycji, a więc $n^2$
Zakładamy DETEKTOR
Z silną dokładnością oraz silną kompletnością
Oczywiście działa, a co jeżeli zmienimy własności detektora?
Zakładamy DETEKTOR
Ze słabą dokładnością oraz silną kompletnością
Słaba dokładność oznacza, że istnieje jeden proces poprawny, który nie jest nigdy podejrzewany, a więc mogą istnieć procesy poprawne, które są podejrzewane. Załóżmy, że proces $P_1$ jest poprawny, decydując się na swoją wartość początkową $v_1$; jednakże proces $P_2$ podejrzewa $P_1$ o awarię.
Zakładamy DETEKTOR
Ze słabą dokładnością oraz silną kompletnością
Słaba dokładność oznacza, że istnieje jeden proces poprawny, który nie jest nigdy podejrzewany, a więc mogą istnieć procesy poprawne, które są podejrzewane. Załóżmy, że proces $P_1$ jest poprawny, decydując się na swoją wartość początkową $v_1$; jednakże proces $P_2$ podejrzewa $P_1$ o awarię.
Zgodnie z algorytmem, $P_2$ przejdzie do nowej rundy, w której będzie liderem, a więc zdecyduje się na swoją wartość początkową $v_2$. Zakłóca to własność zgodności, bo dwa poprawne procesy zdecydowały się na różne wartości.
Zakładamy DETEKTOR
Z silną dokładnością oraz słabą kompletnością
W słabej kompletności każdy niepoprawny proces jest podejrzewany przez jakiś poprawny proces. A więc, jeżeli proces ulegnie awarii, nie wszystkie muszą go podejrzewać. Niech $P_1$, lider pierwszej rundy, ulegnie awarii.
Zakładamy DETEKTOR
Z silną dokładnością oraz słabą kompletnością
W słabej kompletności każdy niepoprawny proces jest podejrzewany przez jakiś poprawny proces. A więc, jeżeli proces ulegnie awarii, nie wszystkie muszą go podejrzewać. Niech $P_1$, lider pierwszej rundy, ulegnie awarii.
Niech $P_3$ podejrzewa $P_1$ - spełniona jest więc własność słabej kompletności. $P_2$ jednak nie podejrzewa $P_1$, a więc czeka na jego decyzję. Zakłóca to własność zakończenia (która jest własnością postępu/żywotności) - algorytm nigdy się nie zakończy.