Small Cuts and Connectivity Certificates: A Fault Tolerant Approach
Small Cuts and Connectivity Certificates: A Fault Tolerant Approach
复制标题
小削减和连接证书：容错方法
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
M. Parter
中科院分区：
文献类型：
--
作者：
M. Parter
我们重新审视分布式计算的拥塞（CONGEST）模型中的经典连通性问题。通过使用容错网络设计技术，我们展示了改进的构造，其中一些对于与困难的全局问题密切相关的问题（即具有$\Omega(直径 + \sqrt{n})$轮的下界）甚至是“局部的”（即具有$\widetilde{O}(1)$轮）。
我们的主要结果如下：
(1) 对于具有常数边连通性的直径为$D$的无权图，我们展示了在$poly(D)$轮内对最小割进行精确的分布式确定性计算。这解决了Daga、Henzinger、Nanongkai和Saranurak在STOC'19中最近提出的开放问题之一。
(2) 对于直径为$D$的无权图，我们提出了一种确定性算法，该算法在$poly(D) \cdot 2^{O(\sqrt{\log n \log\log n})}$轮内计算所有直至常数的边连通性。
(3) 在$\widetilde{O}(\lambda)$轮内计算稀疏的$\lambda$连通性证书。先前的构造仅对于$\lambda \leq 3$已知且需要$O(D)$轮。这解决了Dori在PODC'18中提出的问题。
We revisit classical connectivity problems in the CONGEST model of distributed computing. By using techniques from fault tolerant network design, we show improved constructions, some of which are even "local" (i.e., with $\widetilde{O}(1)$ rounds) for problems that are closely related to hard global problems (i.e., with a lower bound of $\Omega(Diam+\sqrt{n})$ rounds).
Our main results are:
(1) For $D$-diameter unweighted graphs with constant edge connectivity, we show an exact distributed deterministic computation of the minimum cut in $poly(D)$ rounds. This resolves one the open problems recently raised in Daga, Henzinger, Nanongkai and Saranurak, STOC'19.
(2) For $D$-diameter unweighted graphs, we present a deterministic algorithm that computes of all edge connectivities up to constant in $poly(D)\cdot 2^{O(\sqrt{\log n\log\log n})}$ rounds.
(3) Computation of sparse $\lambda$ connectivity certificates in $\widetilde{O}(\lambda)$ rounds. Previous constructions where known only for $\lambda \leq 3$ and required $O(D)$ rounds. This resolves the problem raised by Dori PODC'18.