Minor Excluded Network Families Admit Fast Distributed Algorithms
Minor Excluded Network Families Admit Fast Distributed Algorithms
复制标题
少数被排除在外的网络家族承认快速分布式算法
DOI：
10.1145/3212734.3212776
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Zuzic, Goran
中科院分区：
文献类型：
--
作者：
Haeupler, Bernhard;Li, Jason;Zuzic, Goran
分布式网络优化问题，如最小生成树、最小割、最短路径等，是分布式计算中的一个活跃研究领域。针对网络拥塞模型中的这类问题，本文提出了一种快速分布式算法。在一般图上，许多优化问题，包括上面提到的问题，都需要在拥塞模型中进行Ω(√n)轮通信，即使网络图的直径要小得多。当然，算法设计的下一步是设计有效的算法，绕过受限图类的这个下界。目前，唯一已知的这样做的方法是使用Ghaffari和Haeupler的低拥堵快捷框架[Soda‘16]。在他们工作的基础上，本文证明了排除的次图允许高质量的捷径，从而得到了上述问题的(D^2)轮算法，其中D是网络图的直径。为了处理排除的次图族，我们利用Robertson和Seymour的图结构定理。据我们所知，这是第一次将图结构定理用于分布式环境中的算法结果。即使涉及证明，仅显示存在好的捷径就足以获得简单、高效的分布式算法。特别是，该捷径框架可以有效地构造出接近最优的捷径，然后用它们来求解优化问题。这一点，再加上包括大多数其他重要图类的排除次图的非常一般的族，使得这个结果引起了人们的极大兴趣。
Distributed network optimization problems, such as minimum spanning tree, minimum cut, and shortest path, are an active research area in distributed computing. This paper presents a fast distributed algorithm for such problems in the CONGEST model, on networks that exclude a fixed minor. On general graphs, many optimization problems, including the ones mentioned above, require Ω(√ n) rounds of communication in the CONGEST model, even if the network graph has a much smaller diameter. Naturally, the next step in algorithm design is to design efficient algorithms which bypass this lower bound on a restricted class of graphs. Currently, the only known method of doing so uses the low-congestion shortcut framework of Ghaffari and Haeupler [SODA'16]. Building off of their work, this paper proves that excluded minor graphs admit high-quality shortcuts, leading to an Õ(D^2) round algorithm for the aforementioned problems, where D is the diameter of the network graph. To work with excluded minor graph families, we utilize the Graph Structure Theorem of Robertson and Seymour. To the best of our knowledge, this is the first time the Graph Structure Theorem has been used for an algorithmic result in the distributed setting. Even though the proof is involved, merely showing the existence of good shortcuts is sufficient to obtain simple, efficient distributed algorithms. In particular, the shortcut framework can efficiently construct near-optimal shortcuts and then use them to solve the optimization problems. This, combined with the very general family of excluded minor graphs, which includes most other important graph classes, makes this result of significant interest.
登录
查看更多内容
随机分布式最短路径算法
DOI：
--
发表时间：
1989
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
B. Awerbuch
通讯作者：
B. Awerbuch
影响因子：
--
作者：
Danupon Nanongkai;Hsin
通讯作者：
Hsin
分布式距离预言机的时间下限
DOI：
--
发表时间：
2014
期刊：
International Conference on Principles of Distributed Systems
影响因子：
--
作者：
Taisuke Izumi;Roger Wattenhofer
通讯作者：
Roger Wattenhofer
小树宽图的 NC 算法
DOI：
--
发表时间：
1988
期刊：
International Workshop on Graph-Theoretic Concepts in Computer Science
影响因子：
--
作者：
H. Bodlaender
通讯作者：
H. Bodlaender
DOI：
--
发表时间：
2003
期刊：
J. Comb. Theory B
影响因子：
--
作者：
N. Robertson;P. Seymour
通讯作者：
P. Seymour