Distributed Computation of Large-scale Graph Problems

Motivated by the increasing need for fast distributed processing of large-scale graphs such as the Web graph and various social networks, we study a number of fundamental graph problems in the message-passing model, where we have k machines that jointly perform computation on an arbitrary n -node (typically, n ≫ k) input graph. The graph is assumed to be randomly partitioned among the k ≥ 2 machines (a common implementation in many real world systems). The communication is point-to-point, and the goal is to minimize the time complexity, i. e. , the number of communication rounds, of solving various fundamental graph problems. We present lower bounds that quantify the fundamental time limitations of distributively solving graph problems. We first show a lower bound of Ω( n/k ) rounds for computing a spanning tree (ST) of the input graph. This result also implies the same bound for other fundamental problems such as computing a minimum spanning tree (MST), breadth-first tree (BFS), and shortest paths tree (SPT). We also show an Ω( n / k 2 ) lower bound for connectivity, ST verification and other related problems. Our lower bounds develop and use new bounds in random-partition communication complexity. To complement our lower bounds, we also give algorithms for various fundamental graph problems, e. g. , PageRank, MST, connectivity, ST verification, shortest paths, cuts, spanners, covering problems, densest subgraph, subgraph isomorphism, finding triangles, etc. We show that problems such as PageRank, MST, connectivity, and graph covering can be solved in Õ(n/k) time (the notation Õ hides polylog( n ) factors and an additive polylog( n ) term); this shows that one can achieve almost linear (in k ) speedup, whereas for shortest paths, we present algorithms that run in time (for (1 + ε)-factor approximation) and in time (for O (log n )-factor approximation) respectively. Our results step towards understanding the complexity of distributively solving large-scale graph problems.

Authors

• Hartmut Klauck
• Danupon Nanongkai
• Gopal Pandurangan
• Peter Robinson 0002

Keywords

No keywords are indexed for this paper.