Pr-1st-1.1-m13-Slajd22

Działanie rozgłoszeniowego algorytmu konsensusu podstawowego: Przykład 1

Przykład prezentowany na slajdzie przedstawia cztery procesy uzgadniające wspólną decyzję za pomocą rozgłoszeniowego algorytmu konsensusu podstawowego. Wszystkie procesy proponują pewną wartość, a odpowiadające im monitory rozsyłają ją za pomocą podstawowego rozgłaszania niezawodnego. Załóżmy, że proces $P_1$ ulega jednak awarii w trakcie rozgłaszania, w wyniku czego jego propozycję otrzymuje jedynie monitor $Q_2$. Ponieważ monitor $Q_2$ zebrał wiadomości od wszystkich monitorów, więc może podjąć decyzję wybierając minimalną wartość, na przykład $v_1$, i rozgłosić ją w systemie. Monitory otrzymując wiadomość o decyzji $Q_1$ podporządkowują się jej, podejmując identyczną decyzję. Należy zauważyć tutaj, że monitory $Q_3$ i $Q_4$ nie mogą same podjąć decyzji, gdyż nie otrzymały wiadomości od wszystkich monitorów procesów, które były uznawane za poprawne na początku tej rundy. Co więcej, po wykryciu awarii procesu $P_1$ monitory mogą rozpocząć nową rundę, rozgłaszając wszystkie znane sobie propozycje.

Fakt wykrycia awarii procesu $P_1$ nie wpływa na decyzję monitora $Q_2$, gdyż otrzymał on już wcześniej wiadomość od tego procesu dodając go do zbioru $correctThisRoun{d}_2$. Proces $P_1$ usunięty jest więc wprawdzie z zbioru correct2, ale ponieważ zbiór $correc{t}_2$ zawiera się w zbiorze $correctThisRoun{d}_2$, zachodzi warunek z wiersza 14-tego algorytmu prowadzący do podjęcia decyzji.

<< Poprzedni slajd | Spis treści | Następny slajd >>