Distributed MST: A Smoothed Analysis
Distributed MST: A Smoothed Analysis
复制标题
分布式 MST：平滑分析
DOI：
10.1145/3369740.3369778
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Pham, Nguyen Dinh
中科院分区：
文献类型：
--
作者：
Chatterjee, Soumyottam;Pandurangan, Gopal;Pham, Nguyen Dinh
我们研究分布式图算法的平滑分析，重点关注基本的最小生成树（MST）问题。为了研究分布式 MST 的时间复杂度作为输入图“扰动”的函数，我们提出了一个平滑模型，该模型由平滑参数 0 ≤ ϵ(n) ≤ 1 参数化，该参数控制每轮可以添加到输入图 G 的随机边的数量。非正式地，ϵ(n) 是每轮可以将随机边添加到节点的概率（通常是 n 的小函数，例如 n--1/4）。添加的随机边一旦添加，就可以（仅）用于通信。我们在上述平滑模型中显示了分布式 MST 时间复杂度的上限和下限。我们提出了一种分布式算法，以高概率计算 MST 并以 Õ(min{1/√ϵ(n)2O(√log n), D+ √n}) 轮数运行，其中 ϵ 是平滑参数，D 是网络直径，n 是网络大小。为了补充我们的上限，我们还显示了 Ω(min{1/√ϵ(n), D + √n}）。我们注意到，除了乘法 2O(√log n) polylog(n) 因子之外，上限和下限基本上匹配。我们的工作可以被视为理解分布式图算法的平滑复杂性的第一步。
We study smoothed analysis of distributed graph algorithms, focusing on the fundamental minimum spanning tree (MST) problem. With the goal of studying the time complexity of distributed MST as a function of the "perturbation" of the input graph, we posit a smoothing model that is parameterized by a smoothing parameter 0 ≤ ϵ(n) ≤ 1 which controls the amount of random edges that can be added to an input graph G per round. Informally, ϵ(n) is the probability (typically a small function of n, e.g., n--¼) that a random edge can be added to a node per round. The added random edges, once they are added, can be used (only) for communication.We show upper and lower bounds on the time complexity of distributed MST in the above smoothing model. We present a distributed algorithm that, with high probability, 1 computes an MST and runs in Õ(min{1/√ϵ(n)2O(√log n), D+ √n}) rounds2 where ϵ is the smoothing parameter, D is the network diameter and n is the network size.To complement our upper bound, we also show a lower bound of Ω(min{1/√ϵ(n), D + √n}). We note that the upper and lower bounds essentially match except for a multiplicative 2O(√log n) polylog(n) factor.Our work can be considered as a first step in understanding the smoothed complexity of distributed graph algorithms.
登录
查看更多内容
(Δ + 1) 拥塞团模型中的着色
DOI：
--
发表时间：
2018
期刊：
影响因子：
--
作者：
M. Parter
通讯作者：
M. Parter
DOI：
--
发表时间：
2018
期刊：
Bull. EATCS
影响因子：
--
作者：
Gopal Pandurangan;Peter Robinson;Michele Scquizzato
通讯作者：
Michele Scquizzato
DOI：
10.1145/3087801.3087827
发表时间：
2017-07
期刊：
Proceedings of the ACM Symposium on Principles of Distributed Computing
影响因子：
--
作者：
M. Ghaffari;F. Kuhn;Hsin-Hao Su
通讯作者：
M. Ghaffari;F. Kuhn;Hsin-Hao Su
随机图中哈密顿环的快速高效分布式计算
DOI：
10.1109/icdcs.2018.00079
发表时间：
2018
期刊：
38th IEEE International Conference on Distributed Computing Systems (ICDCS
影响因子：
--
作者：
Chatterjee, Soumyottam;Fathi, Reza;Pandurangan, Gopal;Pham, Nguyen Dinh
通讯作者：
Pham, Nguyen Dinh
针对拥塞派系的分布式对称破缺算法
DOI：
--
发表时间：
2018
期刊：
Computer Science Symposium in Russia
影响因子：
--
作者：
Leonid Barenboim;V. Khazanov
通讯作者：
V. Khazanov