Parallel graph algorithms in constant adaptive rounds
Open Access
- 1 September 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 13 (13) , 3588-3602
Abstract
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 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.Keywords
This publication has 42 references indexed in Scilit:
- The Graph Structure in the Web − Analyzed on Different Aggregation LevelsThe Journal of Web Science, 2015
- Access to Data and Number of Iterations2015
- PageRank Beyond the WebSIAM Review, 2015
- Streaming algorithms for k-core decompositionProceedings of the VLDB Endowment, 2013
- Greedy sequential maximal independent set and matching are parallel on average2012
- Sorting, Searching, and Simulation in the MapReduce Framework2011
- Fast incremental and personalized PageRankProceedings of the VLDB Endowment, 2010
- FlumeJavaACM SIGPLAN Notices, 2010
- MapReduceCommunications of the ACM, 2008
- A randomized linear-time algorithm to find minimum spanning treesJournal of the ACM, 1995