Low-Congestion shortcuts without embedding
Low-Congestion shortcuts without embedding
复制标题
无需嵌入的低拥塞快捷方式
DOI：
10.1007/s00446-020-00383-2
复制
发表时间：
2021
影响因子：
1.3
通讯作者：
Zuzic, Goran
中科院分区：
文献类型：
--
作者：
Haeupler, Bernhard;Izumi, Taisuke;Zuzic, Goran
分布式优化算法经常面临解决网络不相交连接部分的子问题。不幸的是，这些部分的直径可能明显大于底层网络的直径，导致运行时间缓慢。这种现象可以被视为适用于 CONGEST 模型中大多数优化问题的普遍 Ω~(n+ D) 下界的广泛根本原因。从积极的一面来看，[加法里和豪普勒； SODA’16] 引入了低拥塞捷径作为一种优雅的解决方案，可以在某些感兴趣的拓扑中规避此问题。特别是，他们表明任何平面网络以及更一般的任何有界属网络都存在良好的捷径。这直接导致了用于 MST 和 Min-Cut 近似的快速 O (D log O (1) n) 分布式算法，假设人们可以以分布式方式有效地构造这些快捷方式。不幸的是，[Ghaffari 和 Hauepler；的捷径建设； SODA'16] 很大程度上依赖于访问网络的属嵌入。然而，分布式计算这种嵌入是一个难题——即使对于平面网络也是如此。目前还没有用于有界属图的分布式嵌入算法。在这项工作中，我们通过定义树限制的快捷方式来回避这个问题：一种更加结构化和受限的快捷方式形式。我们给出了一种新颖的构造算法，它可以有效地找到这样的捷径，这些捷径在对数因子范围内与给定网络存在的最佳受限捷径一样好。这种新的构造算法直接导致 O (D log O (1) n) 轮算法，用于解决存在良好受限捷径的任何拓扑的优化问题，例如 MST，而无需计算任何嵌入。这极大地简化了现有的平面算法，并包括第一个用于有界属图的有效算法。
Distributed optimization algorithms are frequently faced with solving sub-problems on disjoint connected parts of a network. Unfortunately, the diameter of these parts can be significantly larger than the diameter of the underlying network, leading to slow running times. This phenomenon can be seen as the broad underlying reason for the pervasive Ω~(n+ D) lower bounds that apply to most optimization problems in the CONGEST model. On the positive side,[Ghaffari and Hauepler; SODA’16] introduced low-congestion shortcuts as an elegant solution to circumvent this problem in certain topologies of interest. Particularly, they showed that there exist good shortcuts for any planar network and more generally any bounded genus network. This directly leads to fast O (D log O (1) n) distributed algorithms for MST and Min-Cut approximation, given that one can efficiently construct these shortcuts in a distributed manner. Unfortunately, the shortcut construction of [Ghaffari and Hauepler; SODA’16] relies heavily on having access to a genus embedding of the network. Computing such an embedding distributedly, however, is a hard problem—even for planar networks. No distributed embedding algorithm for bounded genus graphs is in sight. In this work, we side-step this problem by defining tree-restricted shortcuts: a more structured and restricted form of shortcuts. We give a novel construction algorithm which efficiently finds such shortcuts that are, up to a logarithmic factor, as good as the best restricted shortcuts that exist for a given network. This new construction algorithm directly leads to an O (D log O (1) n)-round algorithm for solving optimization problems like MST for any topology for which good restricted shortcuts exist—without the need to compute any embedding. This greatly simplifies the existing planar algorithms and includes the first efficient algorithm for bounded genus graphs.
登录
查看更多内容
DOI：
10.1145/2488608.2488656
发表时间：
2012-10
期刊：
--
影响因子：
--
作者：
C. Lenzen;B. Patt-Shamir
通讯作者：
C. Lenzen;B. Patt-Shamir
轮次和消息最优分布式图算法
DOI：
10.1145/3212734.3212737
发表时间：
2018
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
Haeupler, Bernhard;Hershkowitz, D. Ellis;Wajc, David
通讯作者：
Wajc, David
平面网络的分布式算法 I：平面嵌入
DOI：
10.1145/2933057.2933109
发表时间：
2016
期刊：
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing
影响因子：
--
作者：
M. Ghaffari;Bernhard Haeupler
通讯作者：
Bernhard Haeupler
影响因子：
--
作者：
Danupon Nanongkai;Hsin
通讯作者：
Hsin
分布式距离预言机的时间下限
DOI：
--
发表时间：
2014
期刊：
International Conference on Principles of Distributed Systems
影响因子：
--
作者：
Taisuke Izumi;Roger Wattenhofer
通讯作者：
Roger Wattenhofer