Pr-1st-1.1-m13-Slajd54

Algorytm konsensusu probabilistycznego: Założenia

Obecnie zostanie przedstawiony algorytm rozwiązujący problem konsensusu probabilistycznego. Algorytm ten jest modyfikacją dobrze znanego probabilistycznego algorytmu rozwiązującego konsensus binarny. Używa on mechanizmów zgodnego oraz podstawowego rozgłaszania. Wymaga on również, by większość procesów pozostała poprawna. Nie wymaga natomiast obecności detektora awarii.

Każda runda podzielona jest na dwie fazy. W pierwszej fazie używane jest podstawowe rozgłaszanie niezawodne, a w drugiej zgodne rozgłaszanie niezawodne do rozsyłania decyzji. W każdej rundzie istnieje prawdopodobieństwo większe od zera, że algorytm się zakończy; tak więc ostatecznie prawdopodobieństwo zakończenia wynosi 1.

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