Pr-1st-1.1-m05-Slajd50

Złożoność czasowa algorytmu detekcji zakleszczenia w środowisku synchronicznym dla modelu k spośród r (1)

Przeanalizujmy teraz złożoność czasową tego algorytmu, przyjmując, że graf niezorientowany odpowiadający grafowi zorientowanemu, scharakteryzowany jest przez średnicę grafu d i najdłuższą ścieżkę w grafie – l. W ostatnim z prezentowanych przykładów, d = 1 a l = 3.

Ponieważ faza potwierdzania jest zagnieżdżona w fazie powiadamiania, to aby wyznaczyć złożoność całego algorytmu trzeba dodać do złożoności fazy potwierdzania złożoność powiadomienia inicjatora fazy potwierdzania (przekazania mu wiadomości typu NOTIFY), jak również złożoność odpowiadającą przesłaniu wiadomości typu DONE od inicjatora fazy potwierdzania do inicjatora detekcji.

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