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 2 ) 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 light of an existing lower bound ofΩ(n/k 2 ). Our improved algorithm uses a bunch of techniques, including linear graph sketching, that prove useful in the design of efficient distributed graph algorithms. Using the connectivity algorithm as a building block, 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/k 2 ) rounds and are optimal up to polylogarithmic factors. We also show an almost matching lower bound ofΩ(n/k 2 ) rounds for many graph verification problems by leveraging lower bounds in random-partition communication complexity.
In REF , the authors present anÕ (n/k 2 )-round algorithm for graph connectivity, which then serves as the basis forÕ (n/k 2 )-round algorithms for other graph problems such as minimum spanning tree (MST) and approximate min-cut.
Fast Distributed Algorithms for Connectivity and MST in Large Graphs
TOPC
Computer Science