Near-Optimal Scheduling of Distributed Algorithms
Mohsen Ghaffari · 2015
This paper studies the question of how to run many distributed algorithms, solving independent problems, together as fast as possible. Suppose that we want to run distributed algorithms A_1, ..., A_k in the CONGEST model, each taking at most $dilation$ rounds, and where for each network edge, at most $congestion$ messages need to go through it, in total over all these algorithms. A celebrated work of Leighton, Maggs, and Rao[Combinatorica 1994] shows that in the special case where each of these algorithms is simply a packet routing---that is, sending a message from a source to a destination along a given path---there is an $O(congestion+dilation)$ round schedule. Note that this bound is trivially optimal.