Question 1 [10 marks] – Time Complexity for Distributed Algorithms
Discuss the time complexity measures for distributed algorithms, comparing the synchronous and the asynchronous measures (with and without FIFO).
(a) Briefly describe 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).
