Question 4 – Time Complexity for Distributed Algorithms
(a) Briefly describe one of the typical definitions of the time complexity for synchronous distributed algorithms.
(b) Briefly describe the typical definition of the normalised time complexity for asynchronous distributed algorithms, detailing its specific variants for
I. the FIFO scenario, and
II. the NON-FIFO scenario.
(c) Briefly discuss the relationship between the synchronous and normalised asynchronous cases. Which one is always greater or equal than the other, and why? Outline a convincing argument (proof).
(d) Mention well-known algorithms where there is a wide difference between:
I. the synchronous and normalised asynchronous time complexities, and
II. the FIFO and NON-FIFO normalised asynchronous time complexities. For items I and II, NO proof or evidence is required, but indicate the order of magnitude of each time complexity (e.g. linear, polynomial, exponential, in N, in M)
