






















The $CONGEST$ model for distributed network computing is well suited for analyzing the impact of limiting the throughput of a network on its capacity to solve tasks efficiently. For many "global" problems there exists a lower bound of $Ω(D + \sqrt{n/B})$, where $B$ is the amount of bits that can be exchanged between two nodes in one round of communication, $n$ is the number of nodes and $D$ is the diameter of the graph. Typically, upper bounds are given only for the case $B=O(\log n)$, or for the case $B = +\infty$. For $B=O(\log n)$, the Minimum Spanning Tree (MST) construction problem can be solved in $O(D + \sqrt{n}\log^* n)$ rounds, and the Single Source Shortest Path (SSSP) problem can be $(1+ε)$-approximated in $\widetilde{O}(ε^{-O(1)} (D+\sqrt{n}) )$ rounds. We extend these results by providing algorithms with a complexity parametric on $B$. We show that, for any $B=Ω(\log n)$, there exists an algorithm that constructs a MST in $\widetilde{O}(D + \sqrt{n/B})$ rounds, and an algorithm that $(1+ε)$-approximate the SSSP problem in $\widetilde{O}(ε^{-O(1)} (D+\sqrt{n/B}) )$ rounds. We also show that there exist problems that are bandwidth insensitive.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。