Pr-1st-1.1-m13-Slajd51
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ść.
