Pr-1st-1.1-m13-Slajd08

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Twierdzenie Fisher-Lynch-Paterson

Twierdzenie Fisher-Lynch-Paterson


W 1985 zostało udowodnione (Michael Fisher, Nancy Lynch, Michael Paterson) fundamentalne twierdzenie o nierozwiązywalności konsensusu w pełni asynchronicznym środowisku rozproszonym, o ile jest możliwe załamanie (awaria) chociaż jednego procesu. Innymi słowy, jeżeli nie ma ograniczeń na maksymalny czas przesyłania wiadomości i prędkość procesów, to problem konsensusu nie można w ogólności rozwiązać.


Dowód tego twierdzenia opiera się na wykazaniu, że nie jest możliwe odróżnienie procesu niepoprawnego od takiego, który po prostu jest bardzo wolny lub jest połączony bardzo wolnymi łączami.


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