TY - GEN
T1 - Fast distributed algorithms for connectivity and MST in large graphs
AU - Pandurangan, Gopal
AU - Robinson, Peter
AU - Scquizzato, Michele
N1 - Funding Information:
Supported, in part, by US-Israel Binational Science Foundation grant 2008348, NSF grant CCF-1527867, and NSF grant CCF-1540512.
PY - 2016/7/11
Y1 - 2016/7/11
N2 - Motivated by the increasing need to understand the algorithmic foundations of distributed large-scale graph computations, we study a number of fundamental graph problems in a message-passing model for distributed computing where k ≥ 2 machines jointly perform computations on graphs with n nodes (typically, n > k). The input graph is assumed to be initially randomly partitioned among the k machines, a common implementation in many real-world systems. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation. Our main result is an (almost) optimal distributed randomized algorithm for graph connectivity. Our algorithm runs in Õ(n/k) rounds (Õ notation hides a polylog(n) factor and an additive polylog(n) term). This improves over the best previously known bound of Õ(n/k)[Klauck et al., SODA 2015], and is optimal (up to a polylogarithmic factor) in view of an existing lower bound of Ω(n/k2). Our improved algorithm uses a bunch of techniques, including linear graph sketching, that prove useful in the design of efficient distributed graph algorithms. We then present fast randomized algorithms for computing minimum spanning trees, (approximate) min-cuts, and for many graph verification problems. All these algorithms take Õ(n/k2) rounds, and are optimal up to polylogarithmic factors. We also show an almost matching lower bound of Ω(n/k2) for many graph verification problems using lower bounds in random-partition communication complexity.
AB - Motivated by the increasing need to understand the algorithmic foundations of distributed large-scale graph computations, we study a number of fundamental graph problems in a message-passing model for distributed computing where k ≥ 2 machines jointly perform computations on graphs with n nodes (typically, n > k). The input graph is assumed to be initially randomly partitioned among the k machines, a common implementation in many real-world systems. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation. Our main result is an (almost) optimal distributed randomized algorithm for graph connectivity. Our algorithm runs in Õ(n/k) rounds (Õ notation hides a polylog(n) factor and an additive polylog(n) term). This improves over the best previously known bound of Õ(n/k)[Klauck et al., SODA 2015], and is optimal (up to a polylogarithmic factor) in view of an existing lower bound of Ω(n/k2). Our improved algorithm uses a bunch of techniques, including linear graph sketching, that prove useful in the design of efficient distributed graph algorithms. We then present fast randomized algorithms for computing minimum spanning trees, (approximate) min-cuts, and for many graph verification problems. All these algorithms take Õ(n/k2) rounds, and are optimal up to polylogarithmic factors. We also show an almost matching lower bound of Ω(n/k2) for many graph verification problems using lower bounds in random-partition communication complexity.
KW - Distributed graph algorithms
KW - Graph connectivity
KW - Graph sketching
KW - Massive graphs
KW - Minimum spanning trees
UR - http://www.scopus.com/inward/record.url?scp=84979761867&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84979761867&partnerID=8YFLogxK
U2 - 10.1145/2935764.2935785
DO - 10.1145/2935764.2935785
M3 - Conference contribution
AN - SCOPUS:84979761867
T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures
SP - 429
EP - 438
BT - SPAA 2016 - Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
PB - Association for Computing Machinery
T2 - 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016
Y2 - 11 July 2016 through 13 July 2016
ER -