Pr-1st-1.1-m12-Slajd78

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Algorytm zgodnego rozgłaszania niezawodnego z globalnym uporządkowaniem wiadomości : Złożoność

Algorytm zgodnego rozgłaszania niezawodnego z globalnym uporządkowaniem wiadomości : Złożoność


Rozważając złożoność czasową i komunikacyjną przyjmiemy, że topologia przetwarzania ma postać grafu pełnego.

Jak łatwo zauważyć, w przedstawionym algorytmie rozgłoszenie wiadomości wymaga 2 kroków: w pierwszym nadawca rozgłasza wiadomość, w drugim otrzymuje komunikaty typu SNUPDATE. W pierwszym kroku wysłanych jest komunikatów, zaś w drugim co najwyżej komunikatów. Stąd, złożoność komunikacyjna wynosi więc .


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