On the Distributed Complexity of Large-Scale Graph Computations
On the Distributed Complexity of Large-Scale Graph Computations
复制标题
DOI：
10.1145/3210377.3210409
复制
发表时间：
2016-02
期刊：
影响因子：
--
通讯作者：
Gopal Pandurangan;Peter Robinson;Michele Scquizzato
中科院分区：
文献类型：
--
作者：
Gopal Pandurangan;Peter Robinson;Michele Scquizzato
由于增加了大规模图计算的分布式算法基础的越来越需要的动机，我们研究了用于分布式计算的消息通话模型中的一些基本图问题，其中$ k \ geq 2 $机器共同执行与n个节点的图表（通常，$ n \ gg k $）被认为是在K机器中随机分区的，这是许多现实世界中的常见实现。目的是最大程度地减少我们主要贡献的通信\ em回合的数量。数据计算是通过信息理论方法建立的，该方法将圆形复杂性与解决问题所需的最小信息相关联。该定理可以以“食谱”方式使用，以在几个问题的背景下显示分布式的下限，包括我们通过（几乎）（几乎）紧密的下限来提出两个基本图形问题的应用程序。 ，即\ em pagerank计算和\ em三角枚举。在三角列举的情况下，与使用通信复杂性技术相比，沟通复杂性技术并不明显。 Pagerank和三角形的枚举具有（几乎）与相对下限相匹配的圆形复杂性； ，大大改善了这些问题的先前结果[Klauck等，Soda，2015年]，我们显示以下结果：\ beginitemizeıtem\ em pagerank：我们显示了$ \tildeømega的下限（n/k^2） $圆，并提出分布式算法，该算法计算$ \ tildeo（n/k^2）$ rounds中所有图的所有节点的pagerank。任何分布式算法都需要$ \tildeømega（m/k^5/3）$ rounds的边缘。集团模型，直到对数因素。 enditemize
Motivated by the increasing need to understand the distributed algorithmic foundations of large-scale graph computations, we study some fundamental graph problems in a message-passing model for distributed computing where $k \geq 2$ machines jointly perform computations on graphs with n nodes (typically, $n \gg 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 \em rounds of the computation. Our main contribution is the \em General Lower Bound Theorem, a theorem that can be used to show non-trivial lower bounds on the round complexity of distributed large-scale data computations. The General Lower Bound Theorem is established via an information-theoretic approach that relates the round complexity to the minimal amount of information required by machines to solve the problem. Our approach is generic and this theorem can be used in a "cookbook" fashion to show distributed lower bounds in the context of several problems, including non-graph problems. We present two applications by showing (almost) tight lower bounds for the round complexity of two fundamental graph problems, namely \em PageRank computation and \em triangle enumeration. Our approach, as demonstrated in the case of PageRank, can yield tight lower bounds for problems (including, and especially, under a stochastic partition of the input) where communication complexity techniques are not obvious. Our approach, as demonstrated in the case of triangle enumeration, can yield stronger round lower bounds as well as message-round tradeoffs compared to approaches that use communication complexity techniques. We then present distributed algorithms for PageRank and triangle enumeration with a round complexity that (almost) matches the respective lower bounds; these algorithms exhibit a round complexity which scales superlinearly in k , improving significantly over previous results for these problems [Klauck et al., SODA 2015]. Specifically, we show the following results: \beginitemize ıtem \em PageRank: We show a lower bound of $\tildeØmega (n/k^2)$ rounds, and present a distributed algorithm that computes the PageRank of all the nodes of a graph in $\tildeO (n/k^2)$ rounds. ıtem \em Triangle enumeration: We show that there exist graphs with m edges where any distributed algorithm requires $\tildeØmega (m/k^5/3 )$ rounds. This result also implies the first non-trivial lower bound of $\tildeØmega(n^1/3 )$ rounds for the \em congested clique model, which is tight up to logarithmic factors. We then present a distributed algorithm that enumerates all the triangles of a graph in $\tildeO (m/k^5/3 + n/k^4/3 )$ rounds. \enditemize