Pr-1st-1.1-m13-Slajd24

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 $n^2$ 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 $2n^2$ W przypadku, w którym kolejno ulegają awarii wszystkie procesy, algorytm wymaga $n$ kroków (rund), a więc złożoność czasowa wynosi n . W każdej dodatkowej rundzie wymienianych jest dodatkowe $O(n^2)$ wiadomości, z czego wynika, że złożoność komunikacyjna w przypadku pesymistycznym wynosi $O(n^3)$.

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