[2018] COMPSCI 711 Parallel and Distributed Computing - Time Complexity
Question 4
(a) Discuss the typical definition of the normalised time complexity for asynchronous distributed algorithms, and its specifics in the FIFO scenario.
(b) Discuss the exponential message complexity of the asynchronous Bellman-Ford algorithm. Base your discussion on a sample diagram as used in the lectures (see also the figure below).
(c) Based on (b), discuss why this algorithm has an exponential time complexity, in the FIFO scenario.
(d) Discuss why the arguments used in (c) fail, in the NON-FIFO scenario.
Get the Solution to This Question
WeChat (微信)
WhatsApp
