Pr-1st-1.1-m08-Slajd17

Złożoność czasowa algorytmu Chandy-Lamporta

Przyjmujemy teraz, że graf zorientowany odpowiadający topologii przetwarzania rozproszonego scharakteryzowany jest przez następujące parametry:

m –liczba krawędzi grafu (jednokierunkowych kanałów komunikacyjnych),

d –średnica grafu,

l –długość najdłuższej ścieżki w grafie.

Zatem złożoność czasowa algorytmu Chandy-Lamporta wynosi $d+1$, a złożoność komunikacyjna, w sensie liczby przesyłanych znaczników i pomijając zbieranie wiadomości przez $Q_{b}$, wynosi $2m$.

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