Pr-1st-1.1-m13-Slajd07

Konsensus podstawowy: Specyfikacja

Mechanizm konsensusu podstawowego charakteryzują własności ważności, zakończenia, integralności oraz zgodności.

Własność ważności (ang. validity ) oznacza, że jeżeli którykolwiek proces $P_{i}$ decyduje się na wartość $v_{i}$, to wartość ta została wcześniej zaproponowana przez pewien proces. Innymi słowy, procesy nie mogą decydować się na dowolną wartość, lecz muszą zgodzić się na którąś z przedstawionych propozycji.

Własność zakończenia (ang. termination ) oznacza, że wszystkie poprawne procesy ostatecznie decydują się na jakąś wartość. W systemie asynchronicznym, czas podejmowania decyzji jest przy czym skończony, ale nieznany.

Własność integralności (ang. agreement ) oznacza, że każdy proces decyduje się tylko raz. Procesy nie mogą więc zmieniać raz podjętych decyzji.

Własność zgodności (ang. agreement ) oznacza, że nie istnieją dwa poprawne procesy, które zdecydowałyby się na inne wartości. Tym samym, poprawne procesy uzgadniają wspólną wartość.

Dodatkowo wymagane jest by mechanizm konsensusu miał własność nietrywialności rozwiązania (ang. non-triviality ), którą zazwyczaj pomija się definiując konsensus z uwagi na jej oczywistość. Własność ta mówi, że wartość decyzji nie może być ustalona z góry.

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