2017/04/20 by Dennis Olivetti, Olivetti, Dennis
Computer Science · #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.1704.06092
arxiv created 2017/04/20 · arxiv updated 2017/04/21
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 + √(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 = +∞. For B=O(log n), the Minimum Spanning Tree (MST) construction problem can be solved in O(D + √(n)log^* n) rounds, and the Single Source Shortest Path (SSSP) problem can be (1+ε)-approximated in \widetildeO(ε-O(1) (D+√(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 \widetildeO(D + √(n/B)) rounds, and an algorithm that (1+ε)-approximate the SSSP problem in \widetildeO(ε-O(1) (D+√(n/B)) ) rounds. We also show that there exist problems that are bandwidth insensitive.