Pr-1st-1.1-m13-Slajd51

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Konsensus probabilistyczny: Specyfikacja

Konsensus probabilistyczny: Specyfikacja


Poprzednio omawiane algorytmy wymagały spełnienia dość silnego założenia dostępności doskonałego detektora błędów. Mechanizm konsensusu probabilistycznego (ang. randomized consensus , probabilistic consensus ), charakteryzujący się własnościami ważności, zgodności, integralności i zakończenia, nie ma tak silnych wymagań.


Pierwsze trzy własności konsensusu probabilistycznego są identyczne, jak w przypadku konsensusu podstawowego.

Własność ważności (ang. validity ) oznacza, że jeżeli proces decyduje się na wartość , to wartość ta została wcześniej zaproponowana przez pewien proces.

Własność zgodności (ang. agreement ) oznacza, że żadne dwa poprawne procesy nie decydują się na inne wartości.

Własność integralności (ang. agreement ) oznacza, że każdy proces decyduje się tylko raz.


Konsensus probabilistyczny odróżnia się jednak sformułowaniem warunku zakończenia.

Własność zakończenia probabilistycznego (ang. probabilistic termination ) oznacza, że wszystkie poprawne procesy, z prawdopodobieństwem równym 1, ostatecznie decydują się na jakąś wartość.


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