On the Distributed Complexity of Large-Scale Graph Computations
On the Distributed Complexity of Large-Scale Graph Computations
复制标题
DOI：
10.1145/3460900
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Gopal Pandurangan;Peter Robinson;Michele Scquizzato
中科院分区：
文献类型：
--
作者：
Gopal Pandurangan;Peter Robinson;Michele Scquizzato
由于越来越需要了解大规模图计算的分布式算法基础，我们研究了分布式计算的消息传递模型中的一些基本图问题，其中k≥2台机器共同对具有n个节点（通常为n >> k）的图进行计算。假设输入图最初在k台机器之间随机划分，这是许多实际系统中的常见实现。通信是点对点的，目标是尽量减少计算的通信轮数。我们的主要贡献是一般下界定理，该定理可用于显示分布式大规模数据计算的轮复杂度的非平凡下界。这一结果是通过一种信息理论方法建立的，该方法将轮复杂度与机器解决问题所需的最小信息量联系起来。我们的方法是通用的，这个定理可以用“食谱”的方式来显示一些问题的分布下界，包括非图问题。我们给出了两个基本图问题（即PageRank计算和三角枚举）的圆复杂度（几乎）紧下界的应用。这些应用表明，我们的方法可以为通信复杂性技术的应用似乎不明显或给出弱边界的问题产生下界，包括特别是在输入的随机划分下。然后，我们提出了PageRank和三角形枚举的分布式算法，其循环复杂度（几乎）匹配各自的下界；这些算法表现出在k中超线性扩展的圆复杂度，与以前的结果相比有显著改善[Klauck等人，SODA 2015]。具体来说，我们展示了以下结果：PageRank：我们展示了Ὼ（n/k2）轮的下界，并提出了一个分布式算法，该算法在Õ（n/k2）轮中计算图中所有节点的PageRank近似值。三角形枚举：我们证明存在有m条边的图，其中任何分布式算法都需要Ὼ（m/k5/3）轮。这一结果还暗示了拥挤团模型的第一个非平凡下界Ὼ（n /3）轮，该模型紧绷到对数因子。然后，我们提出了一种分布式算法，该算法在Õ（m/k5/3 + n/k4/3）轮中枚举图的所有三角形。
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 ≥ 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 contribution is the 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. This result 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 for several problems, including non-graph problems. We present two applications by showing (almost) tight lower bounds on the round complexity of two fundamental graph problems, namely, PageRank computation and triangle enumeration. These applications show that our approach can yield lower bounds for problems where the application of communication complexity techniques seems not obvious or gives weak bounds, including and especially under a stochastic partition of the input. 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 that scales superlinearly in k, improving significantly over previous results [Klauck et al., SODA 2015]. Specifically, we show the following results: PageRank: We show a lower bound of Ὼ(n/k2) rounds and present a distributed algorithm that computes an approximation of the PageRank of all the nodes of a graph in Õ(n/k2) rounds. Triangle enumeration: We show that there exist graphs with m edges where any distributed algorithm requires Ὼ(m/k5/3) rounds. This result also implies the first non-trivial lower bound of Ὼ(n1/3) rounds for the 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 Õ(m/k5/3 + n/k4/3) rounds.