Near-Optimal Scheduling of Distributed Algorithms
Near-Optimal Scheduling of Distributed Algorithms
复制标题
分布式算法的近最优调度
DOI：
10.1145/2767386.2767417
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
M. Ghaffari
中科院分区：
文献类型：
--
作者：
M. Ghaffari
本文研究了如何以最快的速度运行多个分布式算法，共同解决独立的问题。假设我们想要在拥塞模型中运行分布式算法A_1，…，A_k，每个算法至多占用$膨胀$轮，并且对于每个网络边缘，至多需要通过$拥塞$消息，在所有这些算法中。Leighton、Maggs和Rao[Combinatorica 1994]的一项著名工作表明，在这些算法中的每一个都只是数据包路由的特殊情况下-即沿着给定的路径从源向目的地发送消息-存在$O(拥塞+扩张)$循环调度。请注意，这个界限并不是最优的。(A)Ω(拥塞+扩张logn/logn)轮次的存在调度长度下界；(B)在O(扩张logn)轮预计算后，产生一个接近最优的O(拥塞+扩张logn)轮次调度的分布式算法。后一种结果的一个关键挑战是仅用私人随机性来解决问题，因为全球共享的随机性大大简化了问题。我们用于这个问题的技术实际上更一般，它可以用来从广泛的分布式算法中去除共享随机性的假设，代价是减慢因子O(Log2n)。
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. Generalizing the framework of LMR, we study scheduling general distributed algorithms and present two results: (a) an existential schedule-length lower bound of Ω(congestion + dilation log n/log log n) rounds, (b) a distributed algorithm that produces a near-optimal O(congestion + dilation log n) round schedule, after O(dilation log2 n) rounds of pre-computation. A key challenge in the latter result is to solve the problem with only private randomness, as globally-shared randomness simplifies it significantly. The technique we use for this problem is in fact more general, and it can be used to remove the assumption of having shared randomness from a broad range of distributed algorithms, at the cost of a slow down factor of O(log2 n).