论文标题
恒定自适应回合中的平行图算法：理论符合实践
Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice
论文作者
论文摘要
我们研究了基本的图形问题，例如图形连接性，最小跨越森林（MSF）以及在分布式设置中的近似最大（重量）匹配。特别是，我们专注于自适应大规模平行计算（AMPC）模型，该模型是一个理论模型，可捕获具有分布式哈希表的MapReduce样计算。 我们显示了所有在恒定回合数量的研究问题，仅使用$ O（n^ε）$空间，其中$ 0 <ε<1 $。我们的结果在AMPC模型中的先前结果以及MPC模型中最著名的结果（这是基于许多流行的分布式计算框架（例如MapReduce，Hadoop，Beam，Pregel，Pregel和Giraph）的理论模型。 最后，我们在MPC和AMPC模型中提供了易于分散的分散计算环境中的算法的经验比较。我们在一组大型现实世界图上经验评估了我们的算法，并表明我们的AMPC算法可以在运行时间和圆形复杂性方面改善优化的MPC碱基。
We study fundamental graph problems such as graph connectivity, minimum spanning forest (MSF), and approximate maximum (weight) matching in a distributed setting. In particular, we focus on the Adaptive Massively Parallel Computation (AMPC) model, which is a theoretical model that captures MapReduce-like computation augmented with a distributed hash table. We show the first AMPC algorithms for all of the studied problems that run in a constant number of rounds and use only $O(n^ε)$ space per machine, where $0 < ε< 1$. Our results improve both upon the previous results in the AMPC model, as well as the best-known results in the MPC model, which is the theoretical model underpinning many popular distributed computation frameworks, such as MapReduce, Hadoop, Beam, Pregel and Giraph. Finally, we provide an empirical comparison of the algorithms in the MPC and AMPC models in a fault-tolerant distriubted computation environment. We empirically evaluate our algorithms on a set of large real-world graphs and show that our AMPC algorithms can achieve improvements in both running time and round-complexity over optimized MPC baselines.
