Przetwarzanie rozproszone

Problemy konsensusu

dr inż. Arkadiusz Danilecki

W oparciu o wykłady prof. J. Brzezińskiego

Plan wykładu

  1. Rozwiązywalność problemu konsensusu
  2. Konsensus podstawowy
  3. Konsensus jednolity
  4. Konsensus probabilistyczny

Wstęp

Wstęp

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.

Wstęp

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

Wstęp

Problemy uzgadniania a konsensus

Konsensus jest przykładem klasy problemów nazywanych zbiorczo problemami uzgadniania.

Przykładem takich problemów są:

  • Bizantyjskie zatwierdzanie (ang. byzantine agreement)
  • Problem elekcji
  • Problem zatwierdzania
  • Aproksymowany konsensus

Wstęp

Przypadek trywialny

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.

Wstęp

Dlaczego konsensus?

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.

  • Bizantyjskie zatwierdzanie - w pierwszej rundzie inicjator wysyła swoją wartość, którą wszyscy odbiorcy biorą jako wartość początkową dla problemu konsensusu
  • Problem elekcji
  • Atomowe niezawodne rozgłaszanie z globalnym porządkiem wiadomości

Wstęp

Dlaczego konsensus?

Problem konsensusu można także rozwiązać, mając do dyspozycji mechanizmy rozwiązujące inne problemy (uzgadniania i nie tylko).

  • Atomowe niezawodne rozgłaszanie z globalnym porządkiem wiadomości - wszystkie procesy rozgłaszają wiadomości, wartością konsensusu jest wartość z tej wiadomości, którą uznajemy jako pierwszą.

Konsensus podstawowy

Własnoś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

Rozwiązywalność problemu konsensusu

Twierdzenie (Fisher, Lynch, Patterson)

Problem konsensus nie ma rozwiązania w systemie w pełni asynchronicznym, jeżeli chociaż jeden proces może ulec awarii.

Rozwiązywalność problemu konsensusu

Twierdzenie

Problem konsensus nie ma rozwiązania w systemie z synchronicznymi kanałami i asynchronicznymi procesami, jeżeli chociaż jeden proces może ulec awarii.

Twierdzenie

Problem konsensus nie ma rozwiązania w systemie z asynchronicznymi kanałami i synchronicznymi procesami, jeżeli chociaż jeden proces może ulec awarii.

Rozwiązywalność problemu konsensusu

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.

Rozwiązywalność problemu konsensusu

Rozwiązywalność a obecność detektorów awarii

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$)

Konsensus podstawowy

Algorytm rozgłoszeniowy

Konsensus podstawowy

Algorytm rozgłoszeniowy

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.

Konsensus podstawowy

Algorytm rozgłoszeniowy

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.

Konsensus podstawowy

Algorytm rozgłoszeniowy 


				    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$

Konsensus podstawowy

Algorytm rozgłoszeniowy

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

Konsensus podstawowy

Algorytm rozgłoszeniowy

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

Konsensus podstawowy

Algorytm rozgłoszeniowy

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

Konsensus podstawowy

Algorytm rozgłoszeniowy

Konsensus podstawowy

Algorytm rozgłoszeniowy

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$.

Konsensus podstawowy

Algorytm rozgłoszeniowy

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ę)

Konsensus podstawowy

Algorytm rozgłoszeniowy

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

Konsensus podstawowy

Algorytm rozgłoszeniowy

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)$

Konsensus podstawowy

Algorytm rozgłoszeniowy

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

Konsensus podstawowy

Algorytm rozgłoszeniowy

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

Konsensus podstawowy

Algorytm rozgłoszeniowy

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

Konsensus podstawowy

Algorytm rozgłoszeniowy

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

Konsensus podstawowy

Algorytm rozgłoszeniowy

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

Konsensus podstawowy

Algorytm rozgłoszeniowy

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

Konsensus podstawowy

Algorytm rozgłoszeniowy

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

Konsensus podstawowy

Algorytm rozgłoszeniowy

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

Konsensus podstawowy

Algorytm rozgłoszeniowy

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.

Konsensus podstawowy

Algorytm rozgłoszeniowy

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.

Konsensus podstawowy

Algorytm rozgłoszeniowy

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.

Konsensus podstawowy

Algorytm rozgłoszeniowy

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.

Konsensus podstawowy

Algorytm rozgłoszeniowy

ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości

DOWÓD

Dla każdego innego procesu $P_j$, zachodzi:

  • $P_j$ także nie wykrył nowych awarii i dostał takie same propozycje, więc musiał podjąć taką samą decyzję jak $P_i$, albo...

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.

Konsensus podstawowy

Algorytm rozgłoszeniowy

ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości

DOWÓD

Dla każdego innego procesu $P_j$, zachodzi:

  • $P_j$ także nie wykrył nowych awarii i dostał takie same propozycje, więc musiał podjąć taką samą decyzję jak $P_i$, albo...
  • $P_j$ wykrył awarię i nie podjął decyzji, przeszedł do kolejnej rundy i tam będzie czekał na wiadomość od $P_i$. Jeżeli $P_i$ jest poprawny, $P_j$ otrzyma wówczas jego decyzję i przyjmie ją jako swoją.

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.

Konsensus podstawowy

Algorytm rozgłoszeniowy

ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości

DOWÓD

Dla każdego innego procesu $P_j$, zachodzi:

  • $P_j$ także nie wykrył nowych awarii i dostał takie same propozycje, więc musiał podjąć taką samą decyzję jak $P_i$, albo...
  • $P_j$ wykrył awarię i nie podjął decyzji, przeszedł do kolejnej rundy i tam będzie czekał na wiadomość od $P_i$. Jeżeli $P_i$ jest poprawny, $P_j$ otrzyma wówczas jego decyzję i przyjmie ją jako swoją.

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.

Konsensus podstawowy

Algorytm rozgłoszeniowy

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.

Konsensus podstawowy

Algorytm rozgłoszeniowy

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.

Konsensus podstawowy

Algorytm rozgłoszeniowy

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.

Konsensus podstawowy

Algorytm rozgłoszeniowy

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.

Konsensus podstawowy

Algorytm hierarchiczny

Konsensus podstawowy

Algorytm hierarchiczny

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.

Konsensus podstawowy

Algorytm hierarchiczny 


				    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 \}$

Konsensus podstawowy

Algorytm hierarchiczny

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

Konsensus podstawowy

Algorytm hierarchiczny

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

Konsensus podstawowy

Algorytm hierarchiczny

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

Konsensus podstawowy

Algorytm hierarchiczny

Konsensus podstawowy

Algorytm hierarchiczny

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$.

Konsensus podstawowy

Algorytm hierarchiczny

ZŁOŻONOŚĆ KOMUNIKACYJNA CZASOWA

Przypadek optymistyczny pesymistyczny

Brak awarii : wszyscy decydują w swojej rundzie po otrzymaniu decyzji poprzedniego lidera więc $n$

Konsensus podstawowy

Algorytm hierarchiczny

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

Konsensus podstawowy

Algorytm hierarchiczny

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$

Konsensus podstawowy

Algorytm hierarchiczny

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?

Konsensus podstawowy

Algorytm hierarchiczny

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ę.

Konsensus podstawowy

Algorytm hierarchiczny

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.

Konsensus podstawowy

Algorytm hierarchiczny

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.

Konsensus podstawowy

Algorytm hierarchiczny

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.

Konsensus jednolity

Konsensus jednolity

Własnoś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 proces w końcu decyduje się na jakąś wartość

INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz

JEDNOLITA ZGODNOŚĆ - Żadne dwa procesy, nieważne poprawne czy nie, nie decydują się na różne wartości

Konsensus jednolity

Własnoś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 proces w końcu decyduje się na jakąś wartość

INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz

JEDNOLITA ZGODNOŚĆ - Żadne dwa procesy, nieważne poprawne czy nie, nie decydują się na różne wartości

A więc proces musi się wstrzymać z decyzją, dopóki nie ma pewności, że każdy inny proces, jeżeli by zadecydował - zadecydowałby tak samo.

Konsensus jednolity

Próbujemy wymyślić algorytm

Algorytm z potwierdzeniami od wszystkich

Wyznaczmy $P_i$ na lidera. Niech pewien proces $P_i$ zaproponuje wartość $v_i$, wyśle ją do wszystkich. Każdy po otrzymaniu $v_i$ rozgłasza $v_i$ do wszystkich. Proces decyduje się na $v_i$ po otrzymaniu $v_i$ od wszystkich (czyli zdobyciu potwierdzeń od wszystkich).

A jeżeli $P_i$ ulegnie awarii? Jak długo mają inni czekać?

Użyjemy detektora klasy $P$ i jeżeli wykryjemy awarię, wyznaczymy innego lidera

Konsensus jednolity

Próbujemy wymyślić algorytm

Algorytm z potwierdzeniami od wszystkich

Wyznaczmy $P_i$ na lidera. Niech pewien proces $P_i$ zaproponuje wartość $v_i$, wyśle ją do wszystkich. Każdy po otrzymaniu $v_i$ rozgłasza $v_i$ do wszystkich. Proces decyduje się na $v_i$ po otrzymaniu $v_i$ od wszystkich (czyli zdobyciu potwierdzeń od wszystkich).

Proces $P_i$ nie może zadecydować $v_i$ od razu, bo jeżeli ulegnie awarii, być może nikt nie otrzyma jego wiadomości i nikt nie zdecyduje się na $v_i$ (co by zakłóciło własność albo zakończenia, albo jednolitej zgodności)

Jeżeli pewien proces $P_j$ otrzyma $v_i$ od $P_i$ i wyśle potwierdzenie. $P_j$ nie może zdecydować się od razu na $v_i$. Dlaczego?

Konsensus jednolity

Próbujemy wymyślić algorytm

Algorytm z potwierdzeniami od wszystkich

Jeżeli pewien proces $P_j$ otrzyma $v_i$ od $P_i$ i wyśle potwierdzenie. $P_j$ nie może zdecydować się od razu na $v_i$. Dlaczego?

Powiedzmy, że $P_j$ zdecydowałby od razu po wysłaniu potwierdzenia $v_i$, a tymczasem $P_i$ uległ awarii.

Jeżeli więc $P_j$ zdecyduje i nagle ulegnie awarii, to...

Konsensus jednolity

Próbujemy wymyślić algorytm

Algorytm z potwierdzeniami od wszystkich

Jeżeli pewien proces $P_j$ otrzyma $v_i$ od $P_i$ i wyśle potwierdzenie. $P_j$ nie może zdecydować się od razu na $v_i$. Dlaczego?

Powiedzmy, że $P_j$ zdecydowałby od razu po wysłaniu potwierdzenia $v_i$, a tymczasem $P_i$ uległ awarii. Wówczas mogłoby się zdarzyć, że nikt oprócz $P_j$ nie otrzymałby $v_i$.

Jeżeli więc $P_j$ zdecyduje i ulegnie awarii, to być może nikt nie otrzyma od niego wiadomości i nikt inny nie zdecyduje $v_i$ (co by zakłóciło własność jednolitej zgodności... albo zakończenia)

Konsensus jednolity

Próbujemy wymyślić algorytm

Algorytm z potwierdzeniami od wszystkich

Jeżeli pewien proces $P_j$ otrzyma $v_i$ od $P_i$ i wyśle potwierdzenie. $P_j$ nie może zdecydować się od razu na $v_i$. Dlaczego?

Powiedzmy, że $P_j$ zdecydowałby od razu po wysłaniu potwierdzenia $v_i$, a tymczasem $P_i$ uległ awarii. Wówczas mogłoby się zdarzyć, że nikt oprócz $P_j$ nie otrzymałby $v_i$.

Jeżeli więc $P_j$ zdecyduje i ulegnie awarii, to być może nikt nie otrzyma od niego wiadomości i nikt inny nie zdecyduje $v_i$ (co by zakłóciło własność jednolitej zgodności... albo zakończenia)

Ale gdyby każdy proces po otrzymaniu $v_i$ przejmowałby ją jako swoją propozycję i po wykryciu awarii $P_i$ sam próbował ją rozgłaszać... otrzymalibyśmy prawie gotowy dobry algorytm!

Konsensus jednolity

Algorytm hierarchiczny

Konsensus jednolity

Algorytm hierarchiczny

Założenie algorytmu

Zakładamy dostępność zgodnego rozgłaszania niezawodnego oraz podstawowego rozgłaszania niezawodnego.

Podstawowe rozgłaszanie niezawodne: jeżeli ani nadawca, ani odbiora nie ulegną awarii, to odbiorca odbierze dokładnie raz wysłaną wiadomość.

Zakładamy dostępność doskonałego detektora awarii

Konsensus jednolity

Algorytm hierarchiczny

Założenie algorytmu

Zakładamy dostępność zgodnego rozgłaszania niezawodnego oraz podstawowego rozgłaszania niezawodnego.

Zgodne rozgłaszanie niezawodne: jeżeli chociaż jeden poprawny proces dostarczy wiadomość, to wszystkie poprawne procesy dostarczą wiadomość.

Zakładamy dostępność doskonałego detektora awarii

Konsensus jednolity

Algorytm hierarchiczny 


				    message ~~proposal~~ is a struct of ~~\langle~~int ~~value~~, int ~~roundNo \rangle~~
				    message ~~decision~~ is a struct of ~~\langle~~int ~~value \rangle~~
				    message ~~ack~~ is a struct of ~~\langle~~int ~~value \rangle~~

				    local int $roundNo_i$ := 1
				    local int $decided_i$ := $nil$
				    local int $proposal_i$ := $nil$
				    local array of int $proposed_i\left[1 \ldots n\right]$ := $\{ nil, \ldots nil\}$
				    local array of processes $liderSet_i$ := $\{ P_1, P_2, \ldots P_n \}$
				    local set of processes $suspected_i$ := $\emptyset$
				    local set of processes $ackSet_i$ := $\emptyset$

Konsensus jednolity

Algorytm hierarchiczny

ZAŁOŻENIE: dostępny jest doskonały detektor awarii $FD_i$ 


when process ~~P_i~~ proposes a value ~~v_i \land proposal_i = nil~~ do
    ~~proposal_i~~ := ~~v_i~~
end when
when $FD_i$ starts suspecting $P_j$ do
    $suspected_i \xleftarrow{append} P_j$
end when

Konsensus jednolity

Algorytm hierarchiczny

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 decided_i = nil~~ do
     ~~proposal.roundNo~~ := ~~roundNo_i~~
     ~~proposal.value~~ := ~~proposal_i~~
     broadcast ~~proposal~~ to ~~\mathcal{P}~~ using best-effort broadcast
end when

Konsensus jednolity

Algorytm hierarchiczny

ZAŁOŻENIE: używamy kanałów niezawodnych (ang. perfect links) 


when a message ~~proposal~~ arrives at ~~{P}_{i}~~ from ~~{P}_{j}~~ do
     ~~proposed_i[proposal.roundNo]~~ := ~~proposal.value~~
     if ~~proposal.roundNo \geq roundNo_i~~ then
         ~~ack.roundNo~~ := ~~proposal.roundNo~~
         send ~~ack~~ to ~~P_j~~
     end if
end when

Konsensus jednolity

Algorytm hierarchiczny

ZAŁOŻENIE: używamy kanałów niezawodnych (ang. perfect links) 


when ~~liderSet_i[roundNo_i] \in suspected_i~~ do
     if ~~proposed_i[roundNo_i] \neq nil~~ then
         ~~proposal_i~~ := ~~proposed_i[roundNo_i]~~
     end if
     ~~roundNo_i~~ := ~~roundNo_i~~ + 1
end when
when a message ~~ack~~ arrives at ~~{P}_{i}~~ from ~~{P}_{j}~~ do
     ~~ackSet_i \xleftarrow{append} P_j~~
end when

Konsensus jednolity

Algorytm hierarchiczny

ZAŁOŻENIE: używamy zgodnego niezawodnego rozgłaszania (ang. regular reliable broadcast) 


when ~~ackSet_i \cup suspected_i == \mathcal{P}~~ do
     ~~decision.value~~ := ~~proposal_i~~
     broadcast ~~decision~~ to ~~\mathcal{P}~~ using regular reliable broadcast
end when
when a message ~~decision~~ arrives at ~~{P}_{i}~~ from ~~{P}_{j} \land decision_i = nil~~ do
     ~~decided_i~~ := ~~decision.value~~
     decide ~~decided_i~~
end when

Konsensus jednolity

Algorytm hierarchiczny

ZŁOŻONOŚĆ KOMUNIKACYJNA CZASOWA

Przypadek optymistyczny pesymistyczny

Brak awarii : lider wysyła $n$ propozycji, dostaje $n$ potwierdzeń, wysyła wszystkim decyzję - a więc $3 * n$.

Konsensus jednolity

Algorytm hierarchiczny

ZŁOŻONOŚĆ KOMUNIKACYJNA CZASOWA

Przypadek pesymistyczny

Wszyscy oprócz ostatniego ulegają awarii : lider każdej rundy wysyła $n$ propozycji, dostaje w pierwszej rundzie $n$ potwierdzeń, w drugiej $n-1$ potwierdzeń, w trzeciej $n-2$ ... na koniec wysyła wszystkim decyzję - a więc $O(n^2)$.

Konsensus jednolity

Algorytm hierarchiczny

ZŁOŻONOŚĆ CZASOWA KOMUNIKACYJNA

Przypadek optymistyczny pesymistyczny

Brak awarii : lider wysyła równocześnie $n$ propozycji, wszyscy dostają w tej samej chwili, odsyłają potwierdzenia, lider wysyła wszystkim decyzję - a więc $3$.

Konsensus jednolity

Algorytm hierarchiczny

ZŁOŻONOŚĆ CZASOWA

Przypadek pesymistyczny

Wszyscy liderzy po kolei ulegają awarii, oprócz ostatniego: W każdej któryś proces wykrywa awarię nie dostając decyzji (bo gdyby dostał, zadecydowałby sam), więc każda runda oprócz ostatniej może zająć dwie jednostki. W trzeciej mamy trzy jednostki czasu. Ostatecznie więc $2n + 1$.

Konsensus jednolity

Algorytm hierarchiczny

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

JEDNOLITA ZGODNOŚĆ - Żadne dwa procesy, nieważne poprawne czy nie, nie decydują się na różne wartości

Konsensus jednolity

Algorytm hierarchiczny

DOWÓD POPRAWNOŚCI

INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz

Procesy podejmują decyzję tylko jeżeli ~~decided_i = nil~~ i przed decyzją ustawiają ~~decided_i~~, a więc jest niemożliwe by zadecydowały dwa razy - c.n.d.

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ść

JEDNOLITA ZGODNOŚĆ - Żadne dwa procesy, nieważne poprawne czy nie, nie decydują się na różne wartości

Konsensus jednolity

Algorytm hierarchiczny

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.

Proces $P_i$ decyduje się albo na własną wartość $v_i$, albo na odebraną w wiadomości $proposal$ od jakiegoś procesu $P_j$. Skoro kanały same nie generują wiadomości, wiadomość $proposal$ musi zawierać wartość wysłaną przez inny proces $P_j$, która albo jest jego propozycją $v_j$, albo została wzięta z wiadomości $proposal$ od jakiegoś proces $P_k$.

Przez rekurencję, skoro procesów jest skończona ilość, ostatecznie dochodzimy do wniosku, że $P_i$ mógł się zdecydować tylko na wartość zaproponowaną przez inny proces - c.b.d.u.

ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość

JEDNOLITA ZGODNOŚĆ - Żadne dwa procesy, nieważne poprawne czy nie, nie decydują się na różne wartości

Konsensus jednolity

Algorytm hierarchiczny

DOWÓD POPRAWNOŚCI

ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość

Jeżeli proces $P_r$, lider rundy $r$, nie ulegnie awarii, to podejmie decyzję po otrzymaniu $ack$ od wszystkich innych procesów, które uznaje za poprawne. Nie będzie czekał nieskończenie długo; jeżeli jest poprawny, kanały niezawodne ostatecznie dostarczą jego $proposal$ do innych procesów, tamte procesy albo wyślą $ack$, które kanały niezawodne ostatecznie dostarczą, albo ulegną awarii, co zostanie wykryte przez doskonały detektor awarii.

JEDNOLITA ZGODNOŚĆ - Żadne dwa procesy, nieważne poprawne czy nie, nie decydują się na różne wartości

Konsensus jednolity

Algorytm hierarchiczny

DOWÓD POPRAWNOŚCI

ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość

Jeżeli proces $P_r$ lider rundy $r$ nie ulegnie awarii i podejmie decyzję, to ją roześle, a z własności zgodnego niezawodnego rozgłaszania wszystkie poprawne procesy ją otrzymają i też podejmą decyzję. Z własności rozgłaszania, jeżeli choć jeden poprawny proces otrzyma tę decyzję (i sam się zdecyduje), wszystkie ją otrzymają (i się zdecydują). W tym wypadku własność byłaby zachowana.

JEDNOLITA ZGODNOŚĆ - Żadne dwa procesy, nieważne poprawne czy nie, nie decydują się na różne wartości

Konsensus jednolity

Algorytm hierarchiczny

DOWÓD POPRAWNOŚCI

ZAKOŃCZENIE - Każdy poprawny proces w końcu decyduje się na jakąś wartość

Jeżeli proces $P_r$ lider rundy $r$ nie ulegnie awarii i podejmie decyzję, to ją roześle, a z własności zgodnego niezawodnego rozgłaszania wszystkie poprawne procesy ją otrzymają i też podejmą decyzję. Z własności rozgłaszania, jeżeli choć jeden poprawny proces otrzyma tę decyzję (i sam się zdecyduje), wszystkie ją otrzymają (i się zdecydują). W tym wypadku własność byłaby zachowana.

Jeżeli proces $P_r$ lider rundy $r$ ulegnie awarii i nikt poprawny nie otrzyma jego decyzji, to zostanie to wykryte przez wszystkie poprawne procesy, które przejdą do rundy $P_{r+1}$. Przez rekurencję powtarzamy rozumowanie dla procesu $P_{r+1}$. Skoro zakładamy, że co najmniej jeden proces musi być poprawny, to rekurencja ostatecznie zakończy się na jakimś poprawnym procesie $P_x$, który podejmie decyzję i ją wyśle, a zgodnie z rozumowaniem powyżej wszystkie poprawne procesy ją otrzymają i się na nią zdecydują (być może będzie wtedy tylko jeden poprawny proces, właśnie $P_x$) c.b.d.u.

JEDNOLITA ZGODNOŚĆ - Żadne dwa procesy, nieważne poprawne czy nie, nie decydują się na różne wartości

Konsensus jednolity

Algorytm hierarchiczny

DOWÓD POPRAWNOŚCI

JEDNOLITA ZGODNOŚĆ - Żadne dwa procesy, nieważne poprawne czy nie, nie decydują się na różne wartości

Jeżeli proces $P_r$ lider rundy $r$ nie ulegnie awarii, to zgodnie z rozumowaniem przy rozważaniu własności zakończenia, wszystkie poprawne procesy otrzymają wartość, na jaką chce się zdecydować i wszystkie podejmą identyczną decyzję.

Jeżeli proces $P_r$ lider rundy $r$ ulegnie awarii i chociaż jeden poprawny proces otrzyma jego decyzję, to z własności zgodnego rozgłaszania niezawodnego wszystkie inne poprawne procesy też ją otrzymają, a więc wszystkie podejmą identyczną decyzję.

Pozostaje rozważyć przypadek, co jeżeli lider uległ awarii, jakiś proces niepoprawny podjął decyzję, ale żaden proces poprawny jej nie otrzymał.

Konsensus jednolity

Algorytm hierarchiczny

DOWÓD POPRAWNOŚCI

JEDNOLITA ZGODNOŚĆ - Żadne dwa procesy, nieważne poprawne czy nie, nie decydują się na różne wartości

Proces $P_r$ lider rundy $r$ decyduje się na $v_x$ dopiero, gdy otrzyma $ack$ od wszystkich poprawnych procesów. Proces odsyła $ack$ dopiero, gdy otrzyma $proposal$ z wartością $v_x$. Wartość $v_x$ przyjmuje jako swoją wartość propozycji, gdy wykryje awarię aktualnego lidera. Propozycje przestarzałe są ignorowane.

A więc $P_r$ podejmie decyzję dopiero wtedy, gdy wszystkie poprawne procesy otrzymały $v_x$, a więc gdy wie, że nawet gdy ulegnie awarii, nowy lider przyjmie $v_x$ za swoją nową wartość. Jeżeli $P_r$ ulegnie awarii, ostatecznie to zostanie wykryte przez inne procesy, w szczególności proces $P_{r+1}$, który rozpocznie nową rundę - proponując $v_x$ jako wartość decyzji.

Konsensus jednolity

Algorytm hierarchiczny

DOWÓD POPRAWNOŚCI

JEDNOLITA ZGODNOŚĆ - Żadne dwa procesy, nieważne poprawne czy nie, nie decydują się na różne wartości

Przez rekurencję, ostatecznie trafimy na proces poprawny, który dokończy rundę i zapewni, że wszystkie procesy poprawne zdecydują się na $v_x$.

Dla kompletności pokażmy, że jeżeli jakiś niepoprawny proces nie będący liderem podejmie decyzję, to każdy proces, który podejmie decyzję, zdecyduje tak samo.

Konsensus jednolity

Algorytm hierarchiczny

DOWÓD POPRAWNOŚCI

JEDNOLITA ZGODNOŚĆ - Żadne dwa procesy, nieważne poprawne czy nie, nie decydują się na różne wartości

Proces niepoprawny może podjąć decyzję tylko albo (1) jako lider rundy - a wyżej widzimy, że wówczas wszystkie inne procesy otrzymały już jego propozycję i mogą się potem zdecydować tylko na nią - albo (2) po otrzymaniu decyzji lidera. W tym drugim wypadku rozumujemy identycznie - decyzję lidera mogły otrzymać tylko, jeżeli wszystkie inne poprawne procesy otrzymały wcześniej propozycję lidera.

Podsumowując, jeżeli proces decyduje się na wartość $v_x$, to ma pewność, że każdy proces, który podejmie decyzję, także zdecyduje się na $v_x$ - c.b.d.u.

Konsensus jednolity

Algorytm hierarchiczny

PYTANIE SPRAWDZAJĄCE

Niech $P_1$ jest liderem. Wysłał $proposal$, zaczął dostawać $ack$ i uległ awarii. Tak więc tylko część procesów mogła dostać jego $proposal$, na przykład tylko jakiś proces $P_i$. Czy to coś zmienia?

Nie, bo $P_1$ może podjąć decyzję tylko, gdy jego propozycję dostaną wszystkie poprawne procesy. Każdy następny lider więc będzie też proponował $v_1$. Gdyby zaś $P_1$ nie podjął decyzji, ale uległby awarii i wykryłby to już $P_2$, proponując $v_2$ - a w jakimś procesie $P_i$ dotarłaby najpierw propozycja $P_2$, a potem przestarzała już propozycja $P_1$ - to propozycja przestarzała będzie zignorowana.

Konsensus jednolity

Algorytm hierarchiczny

Zakładamy DETEKTOR

Z silną dokładnością oraz silną kompletnością

Zastanówmy się, co się stanie, gdy zmienimy własności detektora?

Konsensus jednolity

Algorytm hierarchiczny

Zakładamy DETEKTOR

Z silną dokładnością oraz słabą kompletnością

Słaba kompletność oznacza, że dla każdego niepoprawnego procesu ostatecznie będzie on podejrzewany przez conajmniej jeden proces poprawny. Nb. nie wolno pisać "ten poprawny proces może powiadomić inne", bo gdyby tak robił, to byłby to algorytm transformujący nasze detektor w detektor o silnej kompletności, a my chcemy rozważyć słabą kompletność!

Konsensus jednolity

Algorytm hierarchiczny

Zakładamy DETEKTOR

Z silną dokładnością oraz słabą kompletnością

Rozważmy trzy procesy, gdzie $P_1$ ulega awarii, a pozostałe dwa są poprawne. Niech $P_1$ będzie podejrzewany przez $P_3$ - co spełni warunek słabej kompletności. Niech lider $P_2$ nie podejrzewa $P_1$ (słaba kompletność na to pozwala), a więc w nieskończoność czeka na wiadomość od niego. W efekcie zakłócony jest warunek postępu - nie spełniona jest własność zakończenia.

Konsensus jednolity

Algorytm rozgłoszeniowy

Decyzja w tym algorytmie jest wstrzymywana aż do ~~n~~-tej rundy. 


				    message ~~decision~~ is a struct of ~~\langle \mbox{int } value \rangle~~
				    message ~~proposal~~ is a struct of ~~\langle \mbox{set of int }value, \mbox{int }round \rangle~~

				    local int $roundNo_i$ := 1
				    local bool $decided_i$ := false
				    local set of int $proposed_i$ := $\emptyset$
				    local set of processId $correct_i$ := $\mathcal{P}$
				    local array ~~\left[1 \ldots n\right]~~ of set of processId $delivered_i$ := $\{ \emptyset, \ldots \emptyset\}$

Konsensus jednolity

Algorytm rozgłoszeniowy

ZAŁOŻENIE: dostępny jest doskonały detektor awarii $FD_i$ 


when process ~~P_i~~ proposes a value ~~v_i \land proposal_i = nil~~ do
    ~~proposed_i~~ := ~~v_i~~
    ~~proposal\langle value, round\rangle~~ := ~~\langle v_i,roundNo_i\rangle~~
    broadcast ~~proposal~~ to ~~\mathcal{P}~~
end when
when $FD_i$ starts suspecting $P_j$ do
    $correct_i$ := $correct_i \setminus P_j$
end when
when a message ~~proposal~~ arrives at ~~{P}_{i}~~ from ~~{P}_{j}~~ do
     ~~proposed_i \xleftarrow{append} proposal.value~~
     ~~delivered_i\left[roundNo_i\right] \xleftarrow{append} P_j~~
end when

Konsensus jednolity

Algorytm rozgłoszeniowy

ZAŁOŻENIE: dostępny jest doskonały detektor awarii $FD_i$ 


when ~~correct_i \subseteq delivered_i\left[roundNo_i\right]~~ and not ~~decided_i~~ at process ~~P_i~~ do
    if ~~roundNo_i~~ = ~~n~~ then
       decide MIN( ~~proposed_i~~ )
       ~~decided_i~~ := true
    else
       ~~roundNo_i~~ := ~~roundNo_i~~ + 1
       ~~proposal\langle value, round\rangle~~ := ~~\langle proposed_i,roundNo_i\rangle~~
       broadcast ~~proposal~~ to ~~\mathcal{P}~~
    end if
end when

Konsensus jednolity

Algorytm rozgłoszeniowy

ZŁOŻONOŚĆ KOMUNIKACYJNA CZASOWA

W danej rundzie każdy wysyła $n$ propozycji, jest $n$ rund, a więc łącznie jest przesyłanych $n^2$ wiadomości,

Konsensus jednolity

Algorytm rozgłoszeniowy

ZŁOŻONOŚĆ KOMUNIKACYJNA CZASOWA

W każdej rundzie wszyscy wysyłają wiadomości równocześnie, jest $n$ rund, a więc $n$.

Skład grupy

Algorytm wymaga dostępności mechanizmu konsensusu jednolitego oraz doskonałego detektora awarii

Skład grupy

Algorytm 


				    local bool $wait_i$ := false
				    local set of processId $correct_i$ := $\mathcal{P}$
				    local struct of $\langle \mbox{int} id, \mbox{set of processId} proc\rangle view_i$ := $\langle 0,\mathcal{P}\rangle$

Skład grupy

Algorytm

ZAŁOŻENIE: dostępny jest doskonały detektor awarii $FD_i$ 


when $FD_i$ starts suspecting $P_j$ do
    $correct_i$ := $correct_i \setminus P_j$
end when

when at process ~~P_i~~ ~~view_i.proc \neq correct_i~~ and ~~\neg wait~~ do
    ~~wait_i~~ := true
    propose ~~\langle view_i.id+1, correct_i\rangle~~ for UniformConsensus
end when
when at process ~~P_i~~ UniformConsensus decides ~~\langle vid, \mathcal{S}\rangle~~ do
    ~~view_i~~ := ~~\langle vid, \mathcal{S}\rangle~~
    ~~wait_i~~ := false
    installs ~~view_i~~
end when

Skład grupy

Czy można by zastąpić jednolity konsensus zwykłym konsensusem?

JEDNOLITA ZGODNOŚĆ - Żadne dwa procesy, nieważne poprawne czy nie, nie decydują się na różne wartości

ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości

Skład grupy

Własności (Przypomnienie)

Monotoniczność (ang. monotonicity) - Jeżeli proces ~~P_i~~ instaluje obraz ~~V(j,\mathcal{M})~~ po obrazie ~~V(k,\mathcal{N})~~ to ~~j\gt k~~ oraz ~~\mathcal{M}\subset\mathcal{N}~~ (drugi warunek często się pomija).

Zgodność (ang. agreement) - Jeżeli procesy ~~P_i~~ oraz ~~P_j~~ instalują obrazy ~~V(j,\mathcal{M})~~ oraz ~~V(k,\mathcal{N})~~ gdzie ~~j = k~~, to ~~\mathcal{M} = \mathcal{N}~~.

Kompletność (ang. completeness) - Jeżeli procesy ~~P_i~~ ulega awarii (opuszcza grupę) to ostatecznie istnieje takie ~~k~~, że każdy poprawny proces ostatecznie instaluje widok ~~V(k,\mathcal{M})~~ taki, że ~~P_i\not\in\mathcal{M}~~

Dokładność (ang. accuracy) - Jeżeli procesy ~~P_i~~ instaluje widok ~~V(k,\mathcal{M})~~ taki, że ~~P_j\not\in\mathcal{M}~~, to ~~P_j~~ uległ awarii (lub opuścił grupę).

Konsensus probabilistyczny

Własności

WAŻNOŚĆ - jeżeli proces $\displaystyle P_{i}$ decyduje się na wartość $v_i$, to wartość tę zaproponował jakiś inny proces.

INTEGRALNOŚĆ - Każdy proces decyduje się tylko raz

ZGODNOŚĆ - Żadne dwa poprawne procesy nie decydują się na różne wartości

ZAKOŃCZENIE - Wszystkie poprawne procesy z prawdopodobieństwem równym 1 w końcu decydują się na jakąś wartość

Konsensus probabilistyczny

Założenie algorytmu

Zakładamy dostępność zgodnego rozgłaszania niezawodnego oraz podstawowego rozgłaszania niezawodnego.

Zakładamy poprawność większości procesów.

Konsensus probabilistyczny

Algorytm 


				    message ~~decision~~ is a struct of ~~\langle~~int ~~value~~ \rangle~~
				    message ~~proposal~~ is a struct of ~~\langle~~int ~~value \rangle~~
				    message ~~phaseOne~~ is a struct of ~~\langle~~int ~~value~~, int ~~roundNo \rangle~~
				    message ~~phaseTwo~~ is a struct of ~~\langle~~int ~~value~~, int ~~roundNo \rangle~~

				    local int $roundNo_i$ := 1
				    local int $decided_i$ := $nil$
				    local set of int $proposed_i$ := $\emptyset$
				    local int $estimate_i$ := $nil$
				    local array of int $proposed_i\left[1 \ldots n\right]$ := $\{ nil, \ldots nil\}$
				    local array of set of int $phase1_i\left[1 \ldots n\right]$ := $\{ \emptyset, \ldots \emptyset\}$
				    local array of set of int $phase2_i\left[1 \ldots n\right]$ := $\{ \emptyset, \ldots \emptyset\}$

Konsensus probabilistyczny

Algorytm

ZAŁOŻENIE: używamy podstawowego rozgłaszania niezawodnego (ang. best-effort bcast) 


when process ~~P_i~~ proposes a value ~~v_i~~ do
    ~~proposal.value~~ := ~~\{ v_i \}~~
    broadcast ~~proposal~~ to ~~\mathcal{P}~~
    ~~roundNo_i~~ := ~~roundNo_i~~ + 1
    ~~proposal.roundNo~~ := ~~roundNo_i~~
    ~~proposed_i~~ := ~~\{ v_i \}~~
    ~~estimate_i~~ := ~~ v_i ~~
    ~~phaseOne\langle value,roundNo\rangle~~ := ~~estimate_i, roundNo_i~~
    broadcast ~~phaseOne~~ to ~~\mathcal{P}~~
end when

Konsensus probabilistyczny

Algorytm 


when a message ~~proposal~~ arrives at ~~{P}_{i}~~ from ~~{P}_{j}~~ do
    ~~proposed_i \xleftarrow{append} proposal.value~~
end when

when a message ~~phaseOne~~ arrives at ~~{P}_{i}~~ from ~~{P}_{j}~~ do
    ~~phase1_i\left[phaseOne.round\right] \xleftarrow{append} proposal.value~~
end when

when a message ~~phaseTwo~~ arrives at ~~{P}_{i}~~ from ~~{P}_{j}~~ do
    ~~phase2_i\left[phaseTwo.round\right] \xleftarrow{append} proposal.value~~
end when

Konsensus probabilistyczny

Algorytm

ZAŁOŻENIE: używamy podstawowego rozgłaszania niezawodnego (ang. best-effort bcast) 


when ~~decided_i~~ = nil and ~~\left| phase1_i\left[roundNo_i\right] \right| \geq n/2~~ at ~~{P}_{i}~~ do
    if ~~\exists v :: \forall k \in phase1_i\left[roundNo_i\right] :: k=v~~ then 
       ~~estimate_i~~ := ~~v~~
    else
       ~~estimate_i~~ := nil
    end if
    ~~phaseTwo\langle value,roundNo\rangle~~ := ~~estimate_i, roundNo_i~~
    broadcast ~~phaseTwo~~ to ~~\mathcal{P}~~
end when

Konsensus probabilistyczny

Algorytm

ZAŁOŻENIE: używamy zgodnego rozgłaszania niezawodnego (ang. reliable bcast) 


when ~~decided_i~~ = nil and ~~\left|phase2_i\left[roundNo_i\right]\right| \geq n/2~~ at ~~{P}_{i}~~ do
    if ~~\exists v\neq\mbox{nil } :: \forall k \in phase1_i\left[roundNo_i\right] :: k=v~~ then 
       ~~decided_i~~ := ~~v~~
       ~~decision.value~~ := ~~estimate_i~~
       broadcast ~~decision~~ to ~~\mathcal{P}~~ using reliable bcast
    else
       if ~~\exists v\neq\mbox{nil } \in phase2_i\left[roundNo_i\right]~~ then 
          ~~estimate_i~~ := ~~v~~
       else ~~estimate~~ := RANDOM(~~proposal_i~~)
       end if
       ~~roundNo_i~~ := ~~roundNo_i~~ + 1
       ~~phaseOne\langle value,roundNo\rangle~~ := ~~estimate_i, roundNo_i~~
       broadcast ~~phaseOne~~ to ~~\mathcal{P}~~ 
    end if
end when

Konsensus probabilistyczny

Algorytm 


when a message ~~decision~~ arrives at ~~{P}_{i}~~ from ~~{P}_{j}~~ do
    ~~decided_i~~ := ~~decision.value~~
    decide ~~decided_i~~
end when

Konsensus probabilistyczny

Algorytm

Po co randomizacja?