Pr-1st-1.1-m12-Slajd78

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 $n$ komunikatów, zaś w drugim co najwyżej $(n-1)\times n$ komunikatów. Stąd, złożoność komunikacyjna wynosi więc $O(n^{2})$.

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