Przetwarzanie rozproszone

Problemy konsensusu

dr inż. Arkadiusz Danilecki

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

Plan wykładu

Konsensus jednolity

Algorytm hierarchiczny
Algorytm rozgłoszeniowy

Konsensus probabilistyczny

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

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

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

Wątpliwości?

A czemu pominęliśmy złożoność komunikacyjną zgodnego rozgłaszania niezawodnego, przecież ona nie jest n? Gdyż albowiem.
Sporo za nas robi tutaj to zgodne rozgłaszanie. Nie wystarczyłoby od razu rozgłosić decyzji przy pomocy zgodnego rozgłaszania? Nie.

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

Spróbujmy wymyślić algorytm!

Nie mamy detektorów błędów. Jak sobie z tym poradzić? Czekajmy na ~~n-f~~ lub ~~n/2~~ wiadomości

Jak wybrać, na jaką wartość się zdecydować?

Deterministyczna funkcja?
Losowo?
Większość z odebranych?

Konsensus probabilistyczny

Spróbujmy wymyślić algorytm!

Czekajmy na ~~n-f~~ lub ~~n/2~~ wiadomości

Decydujemy się na większość z odebranych

A wysyła 1, B wysyła 1, C wysyła 2, D wysyła 2, E wysyła 2
A odebrało od B oraz C, ma {A:1, B:1, C:2} decyduje się na 1
B odebrało od C oraz D, ma {B:1, C:2, D:2} decyduje się na 2

Konsensus probabilistyczny

Spróbujmy wymyślić algorytm!

Czekajmy na ~~n-f~~ lub ~~n/2~~ wiadomości

Decydujemy się gdy wszystkie odebrane są takie same.

Jeżeli nie są takie same, wybieramy losowo jedną z propozycji i rozsyłamy ponownie do wszystkich.

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 Ben-Or


				    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?