Pr-1st-1.1-m08-Slajd17

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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

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 , a złożoność komunikacyjna, w sensie liczby przesyłanych znaczników i pomijając zbieranie wiadomości przez , wynosi .


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