Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice
Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice
复制标题
DOI：
10.14778/3424573.3424579
复制
发表时间：
2020-09-01
影响因子：
2.5
通讯作者：
Schudy, Warren
中科院分区：
文献类型：
--
作者：
Behnezhad, Soheil;Dhulipala, Laxman;Schudy, Warren
我们研究基本的图形问题，如图的连通性，最小生成森林（MSF），和近似最大（重量）匹配在分布式设置。特别是，我们专注于自适应大规模并行计算（AMPC）模型，这是一个理论模型，捕获MapReduce类计算与分布式哈希表增强。我们展示了第一个AMPC算法的所有研究的问题，运行在一个恒定的轮数和每台机器只使用O（n（n））空间，其中0 <n < 1。我们的结果改进了AMPC模型中的先前结果，以及MPC模型中最著名的结果，MPC模型是支撑许多流行的分布式计算框架的理论模型，如MapReduce，Hadoop，Beam，Pregel和Gibration.Finally，我们提供了在容错分布式计算环境中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(epsilon)) space per machine, where 0 < epsilon < 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 distributed 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.