Parallel graph algorithms in constant adaptive rounds: theory meets practice
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...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
VLDB Endowment
2021
|
| Online Access: | https://hdl.handle.net/1721.1/136701 |
| _version_ | 1826202170419052544 |
|---|---|
| author | Behnezhad, Soheil Dhulipala, Laxman Esfandiari, Hossein Lacki, Jakub Mirrokni, Vahab Schudy, Warren |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Behnezhad, Soheil Dhulipala, Laxman Esfandiari, Hossein Lacki, Jakub Mirrokni, Vahab Schudy, Warren |
| author_sort | Behnezhad, Soheil |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T12:03:37Z |
| format | Article |
| id | mit-1721.1/136701 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T12:03:37Z |
| publishDate | 2021 |
| publisher | VLDB Endowment |
| record_format | dspace |
| spelling | mit-1721.1/1367012024-03-22T19:34:38Z Parallel graph algorithms in constant adaptive rounds: theory meets practice Behnezhad, Soheil Dhulipala, Laxman Esfandiari, Hossein Lacki, Jakub Mirrokni, Vahab Schudy, Warren Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory 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. 2021-10-28T14:04:29Z 2021-10-28T14:04:29Z 2020-09 Article http://purl.org/eprint/type/ConferencePaper 2150-8097 https://hdl.handle.net/1721.1/136701 Behnezhad, Soheil, Dhulipala, Laxman, Esfandiari, Hossein, Lacki, Jakub, Mirrokni, Vahab et al. 2020. "Parallel graph algorithms in constant adaptive rounds: theory meets practice." 13 (13). 10.14778/3424573.3424579 Creative Commons Attribution-NonCommercial-NoDerivs License http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf VLDB Endowment VLDB Endowment |
| spellingShingle | Behnezhad, Soheil Dhulipala, Laxman Esfandiari, Hossein Lacki, Jakub Mirrokni, Vahab Schudy, Warren Parallel graph algorithms in constant adaptive rounds: theory meets practice |
| title | Parallel graph algorithms in constant adaptive rounds: theory meets practice |
| title_full | Parallel graph algorithms in constant adaptive rounds: theory meets practice |
| title_fullStr | Parallel graph algorithms in constant adaptive rounds: theory meets practice |
| title_full_unstemmed | Parallel graph algorithms in constant adaptive rounds: theory meets practice |
| title_short | Parallel graph algorithms in constant adaptive rounds: theory meets practice |
| title_sort | parallel graph algorithms in constant adaptive rounds theory meets practice |
| url | https://hdl.handle.net/1721.1/136701 |
| work_keys_str_mv | AT behnezhadsoheil parallelgraphalgorithmsinconstantadaptiveroundstheorymeetspractice AT dhulipalalaxman parallelgraphalgorithmsinconstantadaptiveroundstheorymeetspractice AT esfandiarihossein parallelgraphalgorithmsinconstantadaptiveroundstheorymeetspractice AT lackijakub parallelgraphalgorithmsinconstantadaptiveroundstheorymeetspractice AT mirroknivahab parallelgraphalgorithmsinconstantadaptiveroundstheorymeetspractice AT schudywarren parallelgraphalgorithmsinconstantadaptiveroundstheorymeetspractice |