Pr-1st-1.1-m13-Slajd09

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Konsensus w systemach częściowo synchronicznych

Konsensus w systemach częściowo synchronicznych


Twierdzenie 13.2

Nie istnieje algorytm rozwiązujący problem konsensusu w środowisku (modelu) z synchronicznymi procesami i asynchronicznymi kanałami, jeżeli istnieje możliwość załamania (awarii) choćby jednego procesu.

Wynika to oczywiście z braku ograniczeń na czas przesyłania wiadomości, co powoduje, że nie można odróżnić procesu niepoprawnego od takiego, który połączony jest wyjątkowo wolnymi łączami.


Twierdzenie 13.3


Nie istnieje algorytm rozwiązujący problem konsensusu w modelu z asynchronicznymi procesami i kanałami o znanych maksymalnych opóźnieniach, jeżeli istnieje możliwość choć jednej awarii procesu.

Wynika to oczywiście z braku ograniczeń na różnice prędkości między procesami, co powoduje, że nie można odróżnić procesu niepoprawnego od takiego, który jest bardzo wolny.


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