Pr-1st-1.1-m13-Slajd24

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Rozgłoszeniowy algorytm konsensusu podstawowego : Złożoność

Rozgłoszeniowy algorytm konsensusu podstawowego : Złożoność


Załóżmy jak zwykle, że topologię przetwarzania reprezentuje graf w pełni połączony.

Jeżeli żaden proces nie ulega awarii, procesy podejmują decyzję w pierwszej rundzie. Wymaga ona wymiany wiadomości typu MYPROP przed osiągnięciem decyzji i drugie tyle wiadomości typu DECIDED. Złożoność czasowa wynosi więc 1, a komunikacyjna W przypadku, w którym kolejno ulegają awarii wszystkie procesy, algorytm wymaga kroków (rund), a więc złożoność czasowa wynosi n . W każdej dodatkowej rundzie wymienianych jest dodatkowe wiadomości, z czego wynika, że złożoność komunikacyjna w przypadku pesymistycznym wynosi .


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