Przetwarzanie rozproszone

Niezawodność przetwarzania

dr inż. Arkadiusz Danilecki

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

Plan wykładu

Podstawowe pojęcia
Kanały komunikacyjne z gwarancjami
Jak formalnie myśleć o poprawności i awariach ?
Detektory awarii
Własności detektorów awarii
Implementacje detektorów awarii
Algorytm detekcji zakończenia statycznego a awarie

Podstawowe pojęcia

Proces poprawny działa zgodnie ze specyfikacją

Wysyła wiadomości wtedy i tylko wtedy, gdy tego oczekujemy, wykonuje kroki algorytmu, ostatecznie osiąga wyznaczone cele...

$$correct(P_i) = \mbox{ true }$$

Podstawowe pojęcia

Proces poprawny działa zgodnie ze specyfikacją

Wysyła wiadomości wtedy i tylko wtedy, gdy tego oczekujemy, wykonuje kroki algorytmu, ostatecznie osiąga wyznaczone cele...

$$correct(P_i) = \mbox{ true }$$

Proces niepoprawny działa niezgodnie ze specyfikacją (w szczególności, nie działa)

... albo prościej - nie jest poprawny

$$\neg correct(P_i) = \mbox{ true }$$

Podstawowe pojęcia: awaria, błąd, wada

ISO/IEC 2382-14:1997(en):

Failure The termination of the ability of a functional unit to perform a required function.

Error A discrepancy between a computed, observed or measured value or condition and the true, specified or theoretically correct value or condition

Fault An abnormal condition that may cause a reduction in, or loss of, the capability of a functional unit to perform a required function.

Podstawowe pojęcia: awaria, błąd, wada

ISO 10303-226

Failure The lack of ability of a component, equipment, sub system, or system to perform its intended function as designed. A failure may be the result of one or many faults

Error ??

Fault an abnormal condition or defect at the component, equipment, or sub-system level which may lead to a failure

Podstawowe pojęcia: awaria, błąd, wada

Federal Standard 1037C

Failure The temporary or permanent termination of the ability of an entity to perform its required function.

Error

The difference between a computed, estimated, or measured value and the true, specified, or theoretically correct value.
A deviation from a correct value caused by a malfunction in a system or a functional unit.

Fault

An accidental condition that causes a functional unit to fail to perform its required function.
A defect that causes a reproducible or catastrophic malfunction.

Podstawowe pojęcia: awaria, błąd, wada

Awaria (ang. failure) - działanie procesu niezgodne z algorytmem czy specyfikacją.

Błąd (ang. error) - część stanu procesu odpowiedzialna za będącą jego następstwem awarię

Wada (ang. fault) - stwierdzona lub hipotetyczna przyczyna wystąpienia błędu

Rodzaje wad

jednorazowe (ang. transient) - Przy wykonaniu operacji może pojawić się błąd, ale przy ponownym wykonaniu błąd znika.

powtarzalne (ang. intermittent) - W efekcie wady regularnie pojawiają się błędy, zdarzają się też okresy pracy bezbłędnej.

stałe (ang. permanent) - Wada powoduje cały czas błędy przy wykonywaniu operacji aż do wymiany całego komponentu.

Rodzaje wad

Heisenbug - Symptomy wady są różnorakie, błędy często nie pojawiają się przy powtórzeniu operacji mimo replikacji warunków.

Bohrbug - Błędy są powtarzalne przy zreplikowaniu warunków ich występowania, ale ich przyczyna jest nieznana.

Jak sobie radzić z awariami?

Replikacja - Zwielokrotnienie komponentów systemu (plus np. algorytmy głosowania).

Replikacja - Wznawianie pracy komponentów systemu po ich awarii, być może z przywracaniem stanu

Dywersyfikacja - Komponenty różnią się budową, chociaż dostarczają tę samą funkcjonalność.

Rejuwenacja (rejuvenation) - Restartujemy co jakiś czas, ot tak na wszelki wypadek.

Klasy awarii procesów

Komunikacja... ale z gwarancjami

Kanały niezawodne (perfect): własności

niezawodne dostarczanie (ang. fair loss delivery) - jeżeli wiadomość $M$ wysłana jest przez proces $P_{i}$ do procesu $P_{j}$ i żaden z tych procesów nie ulega awarii (oba są poprawne), to wiadomość $M$ jest dostarczona do $P_{j}$.
brak powielania (ang. no duplication ) - żadna wiadomość $M$ nie jest dostarczona więcej niż raz.
brak samogeneracji (ang. no creation ) - jeżeli wiadomość $M$ została dostarczona do procesu $P_{j}$, to została ona wcześniej wysłana do tego procesu przez jakiś inny proces $P_{i}$. Innymi słowy, kanał nie tworzy samorzutnie wiadomości.

Rozgłaszanie

Nieformalnie, rozgłaszanie to mechanizm komunikacyjny, za pomocą którego proces może wysłać wiadomość do grupy procesów. Mechanizmy rozgłaszania niezawodnego gwarantują pewne własności, pomimo występowania awarii. Gwarancje te tyczą się przede wszystkim zapewnienia dostarczenia wiadomości do adresatów, identyczności zbioru wiadomości dostarczanych do wszystkich procesów poprawnych, oraz kolejności dostarczanych wiadomości.

Rozgłaszanie

Mechanizm a algorytm

MECHANIZM - abstrakcyjna specyfikacja czego chcemy; zbiór własności, które muszą być zagwarantowane procesom korzystającym z mechanizmu.

ALGORYTM - realizuje mechanizm, zapewniając wszystkie gwarancje/własności wyszczególnione w mechanizmie.

Podstawowe rozgłaszanie niezawodne

Własności

WAŻNOŚĆ - jeżeli procesy $\displaystyle P_{i}$ oraz $\displaystyle P_{j}$ są poprawne, to każda wiadomość rozgłaszana przez $\displaystyle P_{i}$ jest ostatecznie dostarczona do $\displaystyle P_{j}$.

BRAK POWIELANIA - jeżeli wiadomość jest dostarczona, to jest dostarczona co najwyżej raz.

BRAK SAMOGENERACJI - jeżeli wiadomość jest dostarczona, to została wcześniej rozgłoszona przez jakiś proces.

Podstawowe rozgłaszanie niezawodne

Algorytm

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


when process ~~P_i~~ wants to broadcast a message ~~m~~ to ~~\mathcal{P}~~ do
    for all ~~P_j \in \mathcal{P}~~ do
        send ~~m~~ to ~~P_j~~
    end for
end when

when a message ~~m~~ arrives at ~~{P}_{i}~~ from ~~{P}_{j}~~ do
	deliver ~~m~~
end when

Podstawowe rozgłaszanie niezawodne

Złożoność

Przy założeniach standardowych (pomijamy czasy przetwarzania lokalnego, przyjmujemy jednostkowy czas przesyłu wiadomości):

czasowa : 1

komunikacyjna : n (zakładając, że wysyłamy sami do siebie również)

Podstawowe rozgłaszanie niezawodne

Poprawność

Zapewnienie wszystkich własności mechanizmu w tym algorytmie wynika wprost z użycia kanałów niezawodnych i ich własności.

Zgodne rozgłaszanie niezawodne

Własności

WAŻNOŚĆ - jeżeli proces $P_{i}$ jest poprawny, to każda wiadomość rozgłaszana przez $P_{i}$ jest ostatecznie dostarczona do $P_{i}$.

BRAK POWIELANIA - jeżeli wiadomość jest dostarczona, to jest dostarczona co najwyżej raz.

BRAK SAMOGENERACJI - jeżeli wiadomość jest dostarczona, to została wcześniej rozgłoszona przez jakiś proces.

ZGODNOŚĆ - jeżeli wiadomość jest dostarczona przez jakiś poprawny proces, to ostatecznie będzie dostarczona przez wszystkie inne poprawne procesy.

Zgodne rozgłaszanie niezawodne

Czy przedstawiony wcześniej algorytm dla mechanizmu podstawowego rozgłaszania niezawodnego zapewnia własności zgodnego rozgłaszania niezawodnego?

Więcej o rozgłaszaniu niezawodnym na Algorytmach Rozproszonych

Modele systemów a rozumowanie o poprawności w obecności awarii

Problemy, które musimy rozważyć:

Jakie cechy systemów są ważne przy analizie poprawności?
Jak opisywać wymagania algorytmów wobec systemu?
Jakie są minimalne wymagania dla danego mechanizmu/algorytmu wobec systemu?

Systemy asynchroniczne

Brak zegara globalnego, brak synchronizacji zegarów
Brak ograniczeń na czas komunikacji
Brak ograniczeń na czas przetwarzania

Systemy synchroniczne

Zegar globalny/synchronizacja zegarów
Znane ograniczenia na czas komunikacji
Znane ograniczenia na czas przetwarzania

Systemy częściowo synchroniczne

Znane są maksymalne czasy komunikacji oraz/lub przetwarzania, lecz nie jest znany moment, po którym zaczną one obowiązywać
Istnieją pewne odcinki czasu, w których system działa jak system asynchroniczny, ale są też okresy, w których system działa jak synchroniczny

Systemy częściowo synchroniczne

synchroniczność procesorów - istnieje stała $k_{0}$ taka, że jeżeli pewien proces $P_{i}$ wykona $k_{0}+1$ kroków, to każdy inny proces wykona co najmniej 1 krok.
istnieją ograniczenia na czas przesyłania wiadomości (opóźnienie komunikacyjne).
porządek wiadomości - porządek synchroniczny oznacza, że jeżeli proces $P_{i}$ wysyła wiadomość $M$ do procesu $P_{j}$ w czasie $\tau _{i}$ oraz proces $P_{k}$ wysyła wiadomość $M'$ do procesu $P_{j}$ w czasie $\tau _{j}>\tau _{i}$, to wiadomość $M$ zostanie dostarczona do $P_{j}$ przed wiadomością $M'$.
rodzaj komunikacji, za pomocą niepodzielnej komunikacji rozgłaszania, czy też za pomocą komunikacji punkt-punkt.
typ operacji send/receive - operacje atomowe (tzn., czy operacja wysłania wiadomości $M$ kończy się dopiero po zakończeniu odbioru tej wiadomości przez adresata), czy też są rozłączne. Innymi słowy, czy komunikacja między procesami jest synchroniczna, czy też nie.

$2^5 = 32$ kombinacje

Detektory awarii

Jeżeli proces działa i kanał jest niezawodny, to w końcu się doczekamy na odpowiedź...

... a więc do rozważań o samej poprawności, wystarczy wiedzieć, które procesy uległy awarii!

Detektory awarii

Rozproszona oraz zawodna "wyrocznia" odpowiadająca na pytania o to, czy dany inny proces działa, czy też nie;

rozproszona - każdy proces może otrzymywać inne odpowiedzi. W praktyce wynika to z tego, że każdy proces będzie miał dostęp de facto do własnej instancji detektora.
zawodna - "wyrocznia" może się mylić, a więc detektor może twierdzić, że poprawny proces jest niepoprawny i na odwrót, detektor może też zmieniać zdanie.

Detektory awarii

${\mathcal {P}}=\{P_{1},P_{2},P_{3},\ldots ,P_{n}\}$
Kanały komunikacyjne są niezawodne.
Zegar globalny jest dyskretny, a jego dziedzina ${\mathcal {T}}$ jest zbiorem liczb naturalnych $\mathbb {N}$.
Czasy komunikacji i przetwarzania są ograniczone lecz nieznane.

Wzorzec awarii

Cel - ujęcie w formalne zapisy faktu, że w systemie podczas wykonania zdarzają się w pewnych chwilach awarie.

Wzorzec awarii

Cel - ujęcie w formalne zapisy faktu, że w systemie podczas wykonania zdarzają się w pewnych chwilach awarie.

Niech wzorzec awarii $F$ będzie funkcją $F:{\mathcal {T}}\rightarrow 2^{\mathcal {P}}$, gdzie $F(\tau )$ oznacza zbiór procesów, które uległy awarii do momentu $\tau$. Po awarii proces nie powraca do pracy, czyli prawdziwe jest wyrażenie: $$\forall \tau :F(\tau )\subseteq F(\tau +1)$$

Wzorzec awarii opisuje więc faktyczny stan wszystkich procesów w różnych odcinkach czasu. Ponadto zbiór procesów podejrzanych oraz poprawnych jest opisany odpowiednio przez równości: $$crashed(F)=\bigcup \tau \in {\mathcal {T}},F(\tau )$$ $$correct(F)={\mathcal {P}}\setminus crashed(F)$$

Historia detektora awarii

Cel - ujęcie w formalne zapisy tego, że procesy mają lokalne "wyrocznie", z których każda w różnych chwilach może uznawać inne procesy za niepoprawne (podejrzewa je o awarie).

Historia detektora awarii

Cel - ujęcie w formalne zapisy tego, że procesy mają lokalne "wyrocznie", z których każda w różnych chwilach może uznawać inne procesy za niepoprawne (podejrzewa je o awarie).

Rozważamy tylko wzorce uszkodzeń $\displaystyle F$, w których co najmniej jeden proces jest poprawny, czyli $correct(F)\neq \emptyset$.

Każdy detektor utrzymuje listę (zbiór) procesów, które podejrzewa.

Historia detektora awarii

Cel - ujęcie w formalne zapisy tego, że procesy mają lokalne "wyrocznie", z których każda w różnych chwilach może uznawać inne procesy za niepoprawne (podejrzewa je o awarie).

Rozważamy tylko wzorce uszkodzeń $\displaystyle F$, w których co najmniej jeden proces jest poprawny, czyli $correct(F)\neq \emptyset$.

Każdy detektor utrzymuje listę (zbiór) procesów, które podejrzewa.

Historia detektora awarii to funkcja której dziedziną jest iloczyn kartezjański zbioru procesów i czasu, a zbiór wartości to rodzina wszystkich podzbiorów zbioru ${\mathcal {P}}$.

Wartość $H^{FD}(P_{i},\tau )$ oznacza zbiór procesów podejrzewanych przez $P_{i}$ w chwili $\tau$.

Formalna definicja detektora awarii

Niech ${\mathcal {D}}(F)$ oznacza zbiór możliwych historii detektora awarii i jest sumę mnogościową wszystkich możliwych historii detektora awarii, które mogły się przydarzyć z wzorcem awarii $F$ i detektorem awarii $FD$.

$$FD: F(\tau) \rightarrow D(F)$$

Detektor awarii $FD$ jest to funkcja odwzorowująca wzorzec awarii $F$ w zbiór możliwych historii detektora ${\mathcal {D}}(F)$.

Własności detektorów awarii

NIEFORMALNIE

W formalnych definicjach $FD$ odwzorowywał "wzorzec awariii" w zbiór "możliwych historii", tj. rzeczywistemu zachowaniu systemu (gdzie procesy były poprawne lub ulegały awariom) przypisywał "historie detektora" tj. odpowiedzi "ten czy ów proces jest teraz poprawny".

Detektor, który by po prostu losował odpowiedzi, byłby zgodny z tą definicją.

Własności detektorów awarii

NIEFORMALNIE

Jak dobrze możliwe historie naszego detektora odwzorowują faktyczne awarie?

Kompletność (ang. completeness) - zdolność do podejrzewania wszystkich procesów niepoprawnych.

Czy możemy liczyć na to, że nasz (dla przypomnienia - rozproszony!) detektor wykryje awarię?

Dokładność (ang. accuracy) - zdolność do nie podejrzewania wszystkich procesów poprawnych.

Czy możemy ufać naszemu detektorowi, że wykrywa rzeczywiste awarie?

Własności detektorów awarii

Kompletność

Kompletność (ang. completeness) - zdolność do podejrzewania wszystkich procesów niepoprawnych.

Silna Kompletność (ang. strong completeness):

$$\forall F \forall H^{FD} \in D(F), \exists \tau \in \mathcal{T}: \forall P_i \in crashed(F), \forall P_j \in correct(F) : \forall \tau ^i \geq \tau, P_i \in H^{FD}(P_j,\tau ^i ) $$

Dokładność (ang. accuracy) - zdolność do nie podejrzewania wszystkich procesów poprawnych. Czy możemy ufać naszemu detektorowi, że wykrywa rzeczywiste awarie?

Własności detektorów awarii

Kompletność

Kompletność (ang. completeness) - zdolność do podejrzewania wszystkich procesów niepoprawnych.

Silna Kompletność (ang. strong completeness):

$$ \forall P_i: crashed(P_i) \Rightarrow \forall P_j : correct(P_j), \Diamond \Box suspects( P_j, P_i ) $$

$\Diamond$ - eventually, ostatecznie coś się zdarzy;

$\Box$ - always, zawsze coś będzie/jest prawdziwe;

$\Diamond \Box$ ostatecznie dojdzie do tego, że coś będzie już zawsze prawdziwe

Dokładność (ang. accuracy) - zdolność do nie podejrzewania wszystkich procesów poprawnych. Czy możemy ufać naszemu detektorowi, że wykrywa rzeczywiste awarie?

Własności detektorów awarii

Kompletność

Kompletność (ang. completeness) - zdolność do podejrzewania wszystkich procesów niepoprawnych.

Słaba Kompletność (ang. weak completeness):

$$\forall F \forall H^{FD} \in D(F), \exists \tau \in \mathcal{T}: \forall P_i \in crashed(F), \exists P_j \in correct(F) : \forall \tau ^i \geq \tau, P_i \in H^{FD}(P_j,\tau ^i ) $$

Dokładność (ang. accuracy) - zdolność do nie podejrzewania wszystkich procesów poprawnych. Czy możemy ufać naszemu detektorowi, że wykrywa rzeczywiste awarie?

Własności detektorów awarii

Kompletność

Kompletność (ang. completeness) - zdolność do podejrzewania wszystkich procesów niepoprawnych.

Słaba Kompletność (ang. weak completeness):

$$ \forall P_i: crashed(P_i) \Rightarrow \exists P_j : correct(P_j), \Diamond \Box suspects( P_j, P_i ) $$

Dokładność (ang. accuracy) - zdolność do nie podejrzewania wszystkich procesów poprawnych. Czy możemy ufać naszemu detektorowi, że wykrywa rzeczywiste awarie?

Własności detektorów awarii

Dokładność

Dokładność (ang. accuracy) - zdolność do nie podejrzewania wszystkich procesów poprawnych. Czy możemy ufać naszemu detektorowi, że wykrywa rzeczywiste awarie?

Silna dokładność (ang. strong accuracy):

$$\forall F \forall H^{FD} \in D(F), \forall \tau \in \mathcal{T}, \forall P_i,P_j \not\in F(\tau): P_i \not\in H^{FD}(P_j,\tau ^i ) $$

Własności detektorów awarii

Dokładność

Dokładność (ang. accuracy) - zdolność do nie podejrzewania wszystkich procesów poprawnych. Czy możemy ufać naszemu detektorowi, że wykrywa rzeczywiste awarie?

Silna dokładność (ang. strong accuracy):

$$ \forall P_i: correct(P_i) \Rightarrow \forall P_j: \Box \neg suspects( P_j, P_i ) $$

Własności detektorów awarii

Dokładność

Dokładność (ang. accuracy) - zdolność do nie podejrzewania wszystkich procesów poprawnych. Czy możemy ufać naszemu detektorowi, że wykrywa rzeczywiste awarie?

Słaba dokładność (ang. weak accuracy):

$$\forall F \forall H^{FD} \in D(F), \forall \tau \in \mathcal{T}, \exists P_i \in correct(F), \forall P_j \not\in F(\tau) : P_i \not\in H^{FD}(P_j,\tau ^i ) $$

Własności detektorów awarii

Dokładność

Dokładność (ang. accuracy) - zdolność do nie podejrzewania wszystkich procesów poprawnych. Czy możemy ufać naszemu detektorowi, że wykrywa rzeczywiste awarie?

Słaba dokładność (ang. weak accuracy):

$$ \exists P_i: correct(P_i) \Rightarrow \forall P_j: \Box \neg suspects( P_j, P_i ) $$

Rodzaje detektorów awarii

Redukcje i równoważność detektorów awarii

Detektor pewnej klasy może "udawać" detektor innej klasy, w sensie, że wyjście detektora klasy X można z łatwością tak przerobić, by spełniało własności klasy Y.

Gdy relacja ta zachodzi w obie strony, mówimy, że detektory są równoważne

Redukcje i równoważność detektorów awarii

Przykład: detektor klasy P w trywialny sposób może udawać detektor klasy Q (wynika to wprost z definicji - detektor klasy Q różni się tylko słabą kompletnością).

Pokażemy teraz, jak łatwo można zaproponować algorytm symulujący detektor klasy P przy pomocy detektora klasy Q.

Redukcje i równoważność detektorów awarii

Symulowanie klasy $P$ przy pomocy $Q$


				    message $gossip$ is a struct $\left\langle \mbox{set of processId } suspected \right\rangle$

				    local set of processId ~~suspected_i~~ := ~~\emptyset~~ 
				    local const int ~~period_i^{to}~~

Redukcje i równoważność detektorów awarii

Symulowanie klasy $P$ przy pomocy $Q$

~~FD_i~~ jest detektorem klasy ~~Q~~


when a detector ~~FD_i~~ suspects ~~P_j~~ do
    ~~suspected_i \xleftarrow{append} P_j~~
end when

at each ~~period_i^{to}~~ tick at ~~P_i~~ do
    ~~gossip.suspected~~ := ~~suspected_i~~
    send ~~gossip~~ to ~~\mathcal{P}~~
end at each

Redukcje i równoważność detektorów awarii

Symulowanie klasy $P$ przy pomocy $Q$


when message ~~gossip~~ arrives at ~~P_i~~ from ~~P_j~~ do
    ~~suspected_i \xleftarrow{append} gossip.suspected~~
end when

Czy faktycznie spełnimy własności detektora klasy ~~P~~?

Jakość detektorów awarii

Pomyłka: gdy proces poprawny jest błędnie uważany za niepoprawny.

Czas wykrycia awarii
Czas trwania pomyłki
Czas między pomyłkami
Prawdopodobieństwo trafności zapytania
Średni współczynnik pomyłek
Okres pracy bezbłędnej

Czas wykrycia awarii

Czas trwania pomyłki

Czas między pomyłkami

Detektory "przyrostowe"

Tradycyjne detektory: wartość podejrzewam lub nie podejrzewam.

Detektory przyrostowe (ang. accrual failure detector): wartością jest liczba rzeczywista określająca prawdopodobieństwo, czy proces uległ awarii.

Przykładowa implementacja: obserwacja zachowania pulsu w przeszłości i wyliczanie na tej podstawie prawdopodobieństwa, czy pewnym okresie puls przychodzi z opóźnieniem, czy też proces uległ awarii.

Modele przetwarzania

Model z jawnymi awariami (fail-stop)

Model z ukrytymi awariami (fail-silent)

Model z ostatecznie jawnymi awariami (fail-noisy)

Model z wznowieniami po awariach (fail-recovery)

Model z wyrocznią (randomized)

Modele przetwarzania

Model z jawnymi awariami (fail-stop)

Procesy wykonują deterministyczne algorytmy, chyba że zaprzestaną działania w wyniku awarii. Kanały są niezawodne i jest dostępny doskonały detektor awarii.

Model z ukrytymi awariami (fail-silent)

Model z ostatecznie jawnymi awariami (fail-noisy)

Model z wznowieniami po awariach (fail-recovery)

Model z wyrocznią (randomized)

Modele przetwarzania

Model z jawnymi awariami (fail-stop)

Model z ukrytymi awariami (fail-silent)

Procesy wykonują deterministyczne algorytmy, chyba że zaprzestaną działania w wyniku awarii, kanały są niezawodne, ale nie jest dostępny doskonały detektor awarii.

Model z ostatecznie jawnymi awariami (fail-noisy)

Model z wznowieniami po awariach (fail-recovery)

Model z wyrocznią (randomized)

Modele przetwarzania

Model z jawnymi awariami (fail-stop)

Model z ukrytymi awariami (fail-silent)

Model z ostatecznie jawnymi awariami (fail-noisy)

Procesy wykonują deterministyczne algorytmy, chyba że zaprzestaną działania w wyniku awarii. Kanały są niezawodne, dostępny jest ostatecznie doskonały detektor awarii

Model z wznowieniami po awariach (fail-recovery)

Model z wyrocznią (randomized)

Modele przetwarzania

Model z jawnymi awariami (fail-stop)

Model z ukrytymi awariami (fail-silent)

Model z ostatecznie jawnymi awariami (fail-noisy)

Model z wznowieniami po awariach (fail-recovery)

Procesy wykonują deterministyczne algorytmy, chyba że zaprzestaną działania w wyniku awarii. Po awarii działanie procesu jest wznawiane

Model z wyrocznią (randomized)

Dygresja notacyjna

Które jest bardziej zrozumiałe?


    ~~suspected_i~~ := ~~suspected_i \cup gossip.suspected~~
    ~~suspected_i \leftarrow gossip.suspected~~
    ~~suspected_i \xleftarrow{append} gossip.suspected~~
    ~~var_i, var_j~~ := ~~val^1, val^2~~
    ~~var_i\langle field^1, field^2\rangle~~ := ~~\langle val^1, val^2 \rangle~~
   send ~~\langle field^1 = val^1, field^2 = val^2\rangle~~ to ~~P_j~~

Implementacje detektorów awarii

Mechanizm pulsu

Implementacje detektorów awarii

Mechanizm odpytywania

Implementacje detektorów awarii

Detektor klasy $P$

Implementacje detektorów awarii

Detektor klasy $P$

Algorytm z użyciem mechanizmu pulsu.

Zakładamy istnienie niezawodnych kanałów komunikacyjnych łączących procesy. Ponadto znany jest maksymalny czas transmisji komunikatu. W porównaniu do tej wartości czasy przetwarzania lokalnego i ewentualne różnice w szybkościach zegarów lokalnych są pomijalnie małe.

Implementacje detektorów awarii

Detektor klasy $P$


				    message $hearbeat$ 

				    local set of channels ~~suspected_i~~ := ~~\emptyset~~ 
				    local set of channels ~~correct_i~~ := ~~\mathcal{P}~~ 
				    local const int ~~period_i^{to}~~ 
				    local const int ~~period_i^{p}~~

Implementacje detektorów awarii

Detektor klasy $P$


				    at each ~~period_i^{to}~~ tick at ~~P_i~~ do
				        for all ~~P_k \in \mathcal{P}~~
				            if ~~P_k \not\in correct_i \land P_k \not\in suspected_i~~ then
				               ~~suspected_i \xleftarrow{append} P_k~~
				            end if
				        end for
				        ~~correct_i~~ := ~~\emptyset~~
				    end at each

Implementacje detektorów awarii

Detektor klasy $P$


at each ~~period_i^{p}~~ tick at ~~P_i~~ do
    for all ~~P_k \in \mathcal{P}~~
        send ~~hearbeat~~ to ~~P_k~~
    end for
end at each

when message ~~heartbeat~~ arrives at ~~P_i~~ from ~~P_j~~ do
    ~~correct_i \xleftarrow{append} P_j~~
end when

Implementacje detektorów awarii

Detektor klasy $\Diamond P$

Implementacje detektorów awarii

Detektor klasy $\Diamond P$

Algorytm z użyciem mechanizmu pulsu.

Zakładamy istnienie niezawodnych kanałów komunikacyjnych łączących procesy. Ponadto istnieje maksymalny czas transmisji komunikatu, chociaż nie jest on znany. W porównaniu do tej wartości czasy przetwarzania lokalnego i ewentualne różnice w szybkościach zegarów lokalnych są pomijalnie małe.

Implementacje detektorów awarii

Detektor klasy $\Diamond P$


				    message $hearbeat$ 

				    local set of channels ~~suspected_i~~ := ~~\emptyset~~ 
				    local set of channels ~~correct_i~~ := ~~\mathcal{P}~~ 
				    local int ~~period_i^{to}~~ := ~~t^1~~ 
				    local const ~~period_i^{p}~~

Implementacje detektorów awarii

Detektor klasy $\Diamond P$


at each ~~period_i^{p}~~ tick at ~~P_i~~ do
    for all ~~P_k \in \mathcal{P}~~
        send ~~hearbeat~~ to ~~P_k~~
    end for
end at each

when message ~~heartbeat~~ arrives at ~~P_i~~ from ~~P_j~~ do
    ~~correct_i \xleftarrow{append} P_j~~
end when

Implementacje detektorów awarii

Detektor klasy $\Diamond P$


				    at each ~~period_i^{to}~~ tick at ~~P_i~~ do
				        for all ~~P_k \in \mathcal{P}~~
				            if ~~P_k \not\in correct_i \land P_k \not\in suspected_i~~ then
						~~suspected_i \xleftarrow{append} P_k~~
				            else if ~~P_k \in correct_i \land P_k \in suspected_i~~ then
				                ~~suspected_i~~ := ~~suspected_i \setminus P_k~~
				                ~~period_i^{to}~~ := ~~period_i^{to} + \Delta~~
				            end if
				        end for
				        ~~correct_i~~ := ~~\emptyset~~
				    end at each

Implementacje detektorów awarii

Detektor klasy $\Diamond P$

Dowód poprawności.

Silna kompletność - ostatecznie wszystkie błędne procesy będą podejrzewane.

Ostatecznie silna dokładność - ostatecznie żaden poprawny proces nie będzie podejrzewany.

Implementacje detektorów awarii

Detektor klasy $\Diamond P$

Dowód poprawności.

Postęp

Silna kompletność - ostatecznie wszystkie błędne procesy będą podejrzewane.

Bezpieczeństwo

Ostatecznie silna dokładność - ostatecznie żaden poprawny proces nie będzie podejrzewany.

Implementacje detektorów awarii

Detektor klasy $\Diamond P$

Dowód poprawności.

Postęp

Błędne procesy przestaną wysyłać nowe wiadomości, a wcześniej wysłane wiadomości ostatecznie wszystkie dotrą. Ostatecznie więc przestaną przychodzić nowe wiadomości od tych procesów, i gdy minie czas $period_i^{to}$, zostaną dodane do zbioru $suspected_i$

Implementacje detektorów awarii

Detektor klasy $\Diamond P$

Dowód poprawności.

Bezpieczeństwo

Zakładamy pomijalnie małe różnice w zegarach, oraz że istnieje ograniczenie na maksymalny czas przesyłania wiadomości (częściowo synchroniczny model systemu).

Załóżmy, że pewien poprawny proces $P_j$ został niesłusznie dodany do zbioru ~~suspected_i~~ w procesie $P_i$. Poprawne procesy zawsze wysyłają ~~heartbeat~~, a więc $P_j$ już wysłał albo ostatecznie wyśle ~~heartbeat~~ do $P_i$.

Implementacje detektorów awarii

Detektor klasy $\Diamond P$

Dowód poprawności.

Bezpieczeństwo

Kanały są niezawodne, więc wiadomości ~~hearbeat~~ od ~~P_j~~ w końcu dotrą do ~~P_i~~, co spowoduje usunięcie ~~P_j~~ ze zbioru ~~suspected_i~~ i zwiększenie stałej ~~period_i^{to}~~. Skoro istnieje ograniczenie na czas transmisji, to ostatecznie stała ta zostanie zwiększona tak, że będzie większa od tego czasu i wiadomości ~~heartbeat~~ będą przychodzić do $P_i$ na czas, i ostatecznie ~~P_j~~ przestanie być dodawany do ~~suspected_i~~.

Implementacje detektorów awarii

Detektor klasy $\Diamond P$

Dowód poprawności.

Bezpieczeństwo

Kanały są niezawodne, więc wiadomości ~~heartbeat~~ od ~~P_j~~ w końcu dotrą do ~~P_i~~, co spowoduje usunięcie ~~P_j~~ ze zbioru ~~suspected_i~~ i zwiększenie stałej ~~period_i^{to}~~. Skoro istnieje ograniczenie na czas transmisji, to ostatecznie stała ta zostanie zwiększona tak, że będzie większa od tego czasu i wiadomości ~~heartbeat~~ będą przychodzić do $P_i$ na czas, i ostatecznie ~~P_j~~ przestanie być dodawany do ~~suspected_i~~.

Rozumowanie to można powtórzyć dla każdego niesłusznie podejrzewanego $P_j$, a więc każdy poprawny proces ostatecznie nie będzie już podejrzewany.

Implementacje detektorów awarii

Detektor klasy $\Diamond P$

Czy ten algorytm zapewnia własności dla detektora klasy $P$ w systemie częściowo synchronicznym?

Czy ten algorytm zapewnia własności dla detektora klasy $P$ w systemie synchronicznym?

Algorytm detekcji zakończenia statycznego

Dla przypomnienia: łączymy procesy w wirtualną gwiazdę. Inicjator okresowo sprawdza, czy wszystkie procesy są pasywne i czy wszystkie wysłane przez nie wiadomości zostały już odebrane.

Przeanalizujmy, jak na poprawność algorytmu może wpłynąć obecność awarii.

Algorytm detekcji zakończenia statycznego


				    message $reply$ is a struct $\left\langle \mbox{ bool } contPassive \right\rangle$
				    message $query$, $ack$

				    local int ~~notAck_i~~ := ~~0~~
				    local bool ~~contPassive_i~~ := true
				    local bool ~~AV_i~~ := ~~\emptyset~~
				    local set of processId ~~correct_i~~ := ~~\mathcal{P}~~
				    local set of ~~\left<\mbox{message},\mbox{processId}\right>~~ ~~notAck_i~~ := ~~\emptyset~~

Algorytm detekcji zakończenia statycznego


				    when ~~{P}_{\alpha}~~ wants to start termination detection
				       repeat
				          local bool sTermDetected := true
  				          send ~~query~~ to all ~~P_k~~ in ~~\mathcal{ P }~~ 
  				          for all ~~P_k~~ in ~~\mathcal{ P }~~ do 
  				              wait until a ~~reply~~ arrives from ~~P_k~~ 
  				              ~~sTermDetected~~ := ~~sTermDetected \land reply.contPassive~~
  				          end for
  				       until sTermDetected = true

				       decide "termination detected"
				    end when

Algorytm detekcji zakończenia statycznego


				    when ~~{P}_{\alpha}~~ wants to start termination detection
				       repeat
				          local bool sTermDetected := true
  				          send ~~query~~ to all ~~P_k~~ in ~~\mathcal{ P }~~ 
  				          for all ~~P_k~~ in ~~\mathcal{ P }~~ do 
  				              wait until either a ~~reply~~ arrives from ~~P_k~~ or 
  				                                                    ~~P_k\not\in correct_i~~
  				              if ~~P_k\in correct_i~~ then
  				                  ~~sTermDetected~~ := ~~sTermDetected \land reply.contPassive~~
  				              end if
  				          end for
  				       until sTermDetected = true

				       decide "termination detected"
				    end when

Algorytm detekcji zakończenia statycznego


when process ~~P_i~~ wants to sent a message ~~m~~ to ~~{P}_{j}~~ do
    ~~notAck_i~~ := ~~notAck_i~~ + 1 
    send ~~m~~ to ~~P_j~~
end when

when a message ~~m~~ arrives at process ~~P_i~~ from ~~{P}_{j}~~ do
    send ~~ack~~ to ~~P_j~~
    deliver ~~m~~ 
end when

when a message ~~ack~~ arrives at process ~~P_i~~ from ~~{P}_{j}~~ do
    ~~notAck_i~~ := ~~notAck_i~~ - 1 
end when

Algorytm detekcji zakończenia statycznego


when process ~~P_i~~ wants to sent a message ~~m~~ to ~~{P}_{j}~~ do
    ~~notAck_i \xleftarrow{append}\left\{ m, P_j\right\}~~
    send ~~m~~ to ~~P_j~~
end when

when a message ~~m~~ arrives at process ~~P_i~~ from ~~{P}_{j}~~ do
    send ~~ack~~ to ~~P_j~~
    deliver ~~m~~ 
end when

when a message ~~ack~~ arrives at process ~~P_i~~ from ~~{P}_{j}~~ do
    ~~notAck_i~~ := ~~notAck_i\setminus\left\{m,P_j\right\}~~ - 1 
end when

Algorytm detekcji zakończenia statycznego


when a message ~~query~~ arrives at process ~~P_i~~ from ~~{P}_{j}~~ do
    wait until ~~passive_i~~ and ~~notAck_i = 0~~ and ~~\neg activate( AV_i )~~
    ~~reply.contPassive~~ := ~~contPassive_i~~
    ~~contPassive_i~~ := true
    send ~~reply~~ to ~~P_j~~
end when

when a process ~~P_i~~ activates do
    ~~contPassive_i~~ := false
end when

Algorytm detekcji zakończenia statycznego


when a message ~~query~~ arrives at process ~~P_i~~ from ~~{P}_{j}~~ do
    wait until ~~passive_i~~ and ~~notAck_i = \emptyset~~ and ~~\neg activate( AV_i )~~
    ~~reply.contPassive~~ := ~~contPassive_i~~
    ~~contPassive_i~~ := true
    send ~~reply~~ to ~~P_j~~
end when

when a process ~~P_i~~ activates do
    ~~contPassive_i~~ := false
end when

Algorytm detekcji zakończenia statycznego


when a detector ~~FD_i~~ suspects ~~P_j~~ do
    ~~correct_i~~ := ~~correct_i \setminus P_j~~
    for all ~~x = \left\{ *, P_q \right\} :: x \in notAck_i :: P_q = P_j ~~ do
        ~~notAck_i~~ := ~~notAck_i \setminus x~~
    end for
end when

Problem wyboru lidera

Ostateczna dokładność (ang. eventual accuracy) - ostatecznie wszystkie poprawne procesy uznają za lidera jakiś poprawny proces.

Ostateczna zgodność (ang. eventual agreement) - ostatecznie jeżeli jakiś proces jest uznany za lidera przez pewien poprawny proces, to nie istnieje inny proces uznawany za lidera przez jakikolwiek inny poprawny proces.

Problem wyboru lidera

Założenia

Doskonały detektor awarii

Liderem wybrany będzie proces poprawny o najwyższym identyfikatorze.

Problem wyboru lidera


				    local processId ~~leader_i~~ := nil
				    local set of processId ~~correct_i~~ := ~~\mathcal{P}~~

Problem wyboru lidera


when a detector ~~FD_i~~ suspects ~~P_j~~ do
    ~~correct_i~~ := ~~correct_i \setminus P_j~~
    if ~~leader_i = P_j~~ then ~~leader_i~~ := nil 
end when

when ~~leader_i~~ = nil do
    ~~leader_i~~ := ~~P_q\in correct_i~~ such that ~~\forall P_k\in correct_i: q\gt k~~
end when

Problem wyboru lidera

Założenia

Dostępność pamięci stałej (logu) zdolnej przetrwać awarie

Nb. "pamięć stała" to nie musi być dysk - pamięć trwała NVRAM, pamięć innego procesu...

Doskonały detektor awarii
Poprawny proces ulega skończonej liczbie awarii i po każdej zostaje odtworzony

Problem wyboru lidera

Zarys algorytmu

Liderem wybrany będzie proces poprawny o najwyższym identyfikatorze spośród tych o najmniejszej liczbie awarii

Problem wyboru lidera


				    message $heartbeat$ is a struct $\left\langle \mbox{ int } epochNo \right\rangle$
				    message $trusted$ is a struct $\left\langle \mbox{ processId } pId, \mbox{int} epochNo \right\rangle$

				    local processId ~~leader_i~~ := ~~P_i~~
				    local set of ~~trusted~~ messages ~~candidateSet_i~~ := ~~\forall P_k\in\mathcal{P}: \left\{P_k,0\right\}~~
				    local int ~~epochNo_i~~ := 0

Problem wyboru lidera


when a process ~~P_i~~ recovers from failure do
    retrieve ~~epochNo_i~~ from log
    ~~epochNo_i~~ := ~~epochNo_i~~ + 1
    store ~~epochNo_i~~ to log
    sent ~~heartbeat~~ to ~~\mathcal{P}~~
end when

when a message ~~heartbeat~~ arrives at process ~~P_i~~ from ~~P_j~~ do
    ~~candidateSet_i \xleftarrow{append} \left\{ P_j, heartbeat.epoch\right\}~~
end when

Problem wyboru lidera


when a detector ~~FD_i~~ suspects ~~P_j~~ do
    ~~candidateSet_i~~ := ~~candidateSet_i \setminus \left\{ P_j, * \right\}~~
    if ~~leader_i~~ = ~~P_j~~ then
       ~~leader_i, \mbox{local int } epoch~~ := nil, 0
       for all ~~\left\{ P_q, epoch_q \right\} \in candidateSet_i~~ do
           if ~~leader_i~~ = nil then 
              ~~leader_i, epoch~~ := ~~P_q, epoch_q~~
           else
              if ~~epoch_q \lt epoch~~ then 
                 ~~leader_i, epoch~~ := ~~P_q, epoch_q~~
              else if ~~epoch_q~~ = ~~epoch~~ and ~~P_q \gt leader_i~~ then
                 ~~leader_i, epoch~~ := ~~P_q, epoch_q~~
              end if
           end if
       end for
end when

Problem wyboru lidera

Zamiast używania detektora, można wprost co pewien czas wysyłać wiadomości ~~heartbeat~~ i sprawdzać, czy lider ostatnio wysłał nam ~~heartbeat~~, albo periodycznie inicjować procedurę wyboru lidera.

Okresy reelekcji można dynamicznie dostosowywać do czasów komunikacji.

Przy okazji omawiania konsensusu zobaczymy inny algorytm wyboru lidera.

Po co nam lider?

Wprawdzie rozwiązania w pelni rozproszone są bardziej eleganckie, odporniejsze na błędy, ale... Bywają mniej wydajne, a już zdecydowanie są cięższe do zrozumienia (porównaj Paxos vs Raft!).

Zastosowania:

Replikacja
Skład grupy (omówiony na następnym wykładzie)
Konsensus (omówiony na następnym wykładzie)

Replikacja

Odporność na awarie
Zwiększona dostępność (np. w wypadku partycji sieci)
Zwiększona wydajność (np. interakcje z najbliższą repliką)

Replikacja

Przykład: serwer prowadzący interakcję z klientami plus jego kopie zapasowe.

Załóżmy deterministyczne operacje i/lub możliwość transferu stanu. Repliki możemy wtedy traktować jako maszyny stanowe (state machines), w których dla danego stanu początkowego, powtórzenie operacji w dokładnie tym samym porządku na każdej replice zakończy się identycznymi zmianami stanu.

Replikacja

W przypadku interakcji z klientem, kiedy można zwrócić odpowiedź do klienta?

Co w przypadku awarii lidera?

Tylko część replik mogła otrzymać ostatnią operację...

Replikacja

Zgodne rozgłaszanie z całkowitym uporządkowaniem wiadomości (TOcast)

W skrócie:

jeżeli jakiś poprawny proces dostarczył wiadomość ~~m~~, to wszystkie poprawne procesy dostarczą ~~m~~
jeżeli proces dostarczył wiadomości ~~m^1~~ przed ~~m^2~~, to wszystkie poprawne procesy dostarczą ~~m^1~~ przed ~~m^2~~

Replikacja

Zgodne rozgłaszanie z całkowitym uporządkowaniem wiadomości może być zastąpione mechanizmem konsensusu. W praktyce pojawia się jednak kilka problemów...

Co w przypadku modelu z powtarzalnymi awariami (crash recovery)?

Co jeżeli skład grupy replik się zmieni?

Co w przypadku podziału (partycji) sieci?

Replikacja

Inne podejście: Algorytm z kworum.

Przy zapisie odwołujemy się do W replik, zapisujemy razem z wartością znacznik wersji.

Przy odczycie odwołujemy się do R replik, wybieramy najnowszą wartość.

Dobieramy wartości R oraz W tak, by zawsze istniała część wspólna kworum odczytów i zapisów.

Widzimy jakieś problemy?

Więcej o replikacji na Systemach Wysokiej Niezawodności

Skład grupy

Do tej pory zakładaliśmy, że zbiór ~~\mathcal{P}~~ jest niezmienny, ale w praktyce mogą pojawiać się nowe procesy, inne mogą odchodzić (nie tylko w efekcie awarii). W literaturze mówi się wtedy o zmianie konfiguracji i/lub o problemie zapewnienia spójnego widoku grupy (i "instalowaniu widoku" grupy).

Problem: co jeżeli kilka procesów jednocześnie chce się dostać do grupy lub z niej odejść?

Problem: Jak zapewnić, by komunikaty docierały do wszystkich procesów w danym obrazie grupy? (Komunikacja zsynchronizowana z obrazami grup, view synchronous communication).

Skład grupy

Detektory błędów (nawet doskonałe!) nie rozwiązują problemu, bo ich wiedza jest rozproszona, a procesy widzą awarie w różnej kolejności.

Chcemy więc, by poglądy na skład grupy ("widoki") procesów zmieniały się w sposób spójny.

Widok (ang. view) - obraz składu grupy. Każdy widok posiada unikalny identyfikator. Identyfikatory widoków można jednoznacznie uporządkować.

Proces instaluje widok (ang. installs view) - gdy uznaje widok o danym identyfikatorze za aktualny.

Skład grupy

Własności

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

Skład grupy


				    message $install$ is a struct $\left\langle \mbox{ set of processId } proc, \mbox{ int } id \right\rangle$
				    message $ack$ is a struct $\left\langle \mbox{ set of processId } proc, \mbox{ int } id \right\rangle$
				    message $done$ is a struct $\left\langle \mbox{ set of processId } proc, \mbox{ int } id \right\rangle$

				    local ~~view_i~~ is a struct ~~$\left\langle \mbox{ set of processId} proc, \mbox{ int } id \right\rangle~~ := ~~\langle \mathcal{P}, 0\rangle~~
				    local bool ~~block_i~~ := false

Skład grupy


when a leader ~~P_i~~ receives ~~remove\langle P_j \rangle~~ do
   wait until ~~\neg block~~
   if ~~P_j\in view_i.proc~~ then
      ~~block_i~~ := true
      broadcast ~~install\langle proc := view_i \setminus P_j, id := view_i.id + \mbox{1}\rangle~~ to ~~\mathcal{P}~~
      receive ~~ack\langle view = view_i \rangle~~ from ~~\mathcal{P}~~
      broadcast ~~done\langle view = view_i \rangle~~ to ~~\mathcal{P}~~
      ~~block_i~~ := false
   end if
end when

Skład grupy


when a message ~~install~~ arrives at process ~~P_i~~ from ~~P_j~~ do
    ~~block_i~~ := true
    ~~view_i~~ := ~~install.view~~
    sent ~~ack\langle view \rangle~~ to ~~P_j~~
end when

when a message ~~done~~ arrives at process ~~P_i~~ from ~~P_j~~ do
    ~~block_i~~ := false
end when

when a detector ~~FD_i~~ suspects ~~P_j~~ do
   sent ~~remove\langle P_j \rangle~~ to ~~leader_i~~
end when

Skład grupy

Co jeżeli lider ulegnie awarii?

Wybieramy jako nowego lidera ten proces, który ma największy numer widoku.

Co jeżeli ulegnie awarii podczas zmiany widoku?

Podczas elekcji lidera blokujemy przetwarzanie. Lider przed rozpoczęciem pracy sprawdza, czy istnieją procesy, które uległy awarii, a są w jego widoku; usuwa je i instaluje nowy widok.

Jak uzupełnić algorytm o dodawanie nowych procesów?

Przy dodawaniu banalnie prosto - proces dodawany musi tylko powtarzać prośbę o dodanie, gdyby lider uległ awarii. Przy elekcji - sprawdzamy, czy trzeba rozszerzyć widok.

Skład grupy

Co z odtwarzaniem stanu?

Proces po odtworzeniu zyskuje nową tożsamość (traktujemy go tak, jakby to był nowy proces proszący o dołączenie do grupy).

Czy dałoby się pozbyć lidera?

Zmiany widoku bez lidera najprościej zaimplementować z użyciem mechanizmu konsensusu (jednolitego), więc przykładowy algorytm pokażemy na następnym wykładzie.

Koniec wykładu!

Kolory

Placeholder

Zwykły Thistle zwykły Orange Tomato blue lightsalmon zwykły moccasin zwykły white zwykły PowderBlue zwykły MintCrem zwykły chartreuse zwykły Palegreen mistyrose zwykły silver zwykły azure zwykły