Round compression for parallel matching algorithms
© 2018 Association for Computing Machinery. For over a decade now we have been witnessing the success of massive parallel computation (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for their success is the fact that these frameworks are able to accurately capture th...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
ACM
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137790 |
| _version_ | 1826202748997074944 |
|---|---|
| author | Czumaj, Artur Łącki, Jakub Mądry, Aleksander Mitrović, Slobodan Onak, Krzysztof Sankowski, Piotr |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Czumaj, Artur Łącki, Jakub Mądry, Aleksander Mitrović, Slobodan Onak, Krzysztof Sankowski, Piotr |
| author_sort | Czumaj, Artur |
| collection | MIT |
| description | © 2018 Association for Computing Machinery. For over a decade now we have been witnessing the success of massive parallel computation (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for their success is the fact that these frameworks are able to accurately capture the nature of large-scale computation. In particular, compared to the classic distributed algorithms or PRAM models, these frameworks allow for much more local computation. The fundamental question that arises in this context is though: can we leverage this additional power to obtain even faster parallel algorithms? A prominent example here is the maximum matching problem—one of the most classic graph problems. It is well known that in the PRAM model one can compute a 2-approximate maximum matching in O(log n) rounds. However, the exact complexity of this problem in the MPC framework is still far from understood. Lattanzi et al. (SPAA 2011) showed that if each machine has n1+Ω(1) memory, this problem can also be solved 2-approximately in a constant number of rounds. These techniques, as well as the approaches developed in the follow up work, seem though to get stuck in a fundamental way at roughly O(log n) rounds once we enter the (at most) near-linear memory regime. It is thus entirely possible that in this regime, which captures in particular the case of sparse graph computations, the best MPC round complexity matches what one can already get in the PRAM model, without the need to take advantage of the extra local computation power. |
| first_indexed | 2024-09-23T12:17:10Z |
| format | Article |
| id | mit-1721.1/137790 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:17:10Z |
| publishDate | 2021 |
| publisher | ACM |
| record_format | dspace |
| spelling | mit-1721.1/1377902023-12-06T21:56:20Z Round compression for parallel matching algorithms Czumaj, Artur Łącki, Jakub Mądry, Aleksander Mitrović, Slobodan Onak, Krzysztof Sankowski, Piotr Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 2018 Association for Computing Machinery. For over a decade now we have been witnessing the success of massive parallel computation (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for their success is the fact that these frameworks are able to accurately capture the nature of large-scale computation. In particular, compared to the classic distributed algorithms or PRAM models, these frameworks allow for much more local computation. The fundamental question that arises in this context is though: can we leverage this additional power to obtain even faster parallel algorithms? A prominent example here is the maximum matching problem—one of the most classic graph problems. It is well known that in the PRAM model one can compute a 2-approximate maximum matching in O(log n) rounds. However, the exact complexity of this problem in the MPC framework is still far from understood. Lattanzi et al. (SPAA 2011) showed that if each machine has n1+Ω(1) memory, this problem can also be solved 2-approximately in a constant number of rounds. These techniques, as well as the approaches developed in the follow up work, seem though to get stuck in a fundamental way at roughly O(log n) rounds once we enter the (at most) near-linear memory regime. It is thus entirely possible that in this regime, which captures in particular the case of sparse graph computations, the best MPC round complexity matches what one can already get in the PRAM model, without the need to take advantage of the extra local computation power. 2021-11-08T19:24:12Z 2021-11-08T19:24:12Z 2018-06-20 2019-06-13T17:26:16Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137790 Czumaj, Artur, Łącki, Jakub, Mądry, Aleksander, Mitrović, Slobodan, Onak, Krzysztof et al. 2018. "Round compression for parallel matching algorithms." en 10.1145/3188745.3188764 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf ACM arXiv |
| spellingShingle | Czumaj, Artur Łącki, Jakub Mądry, Aleksander Mitrović, Slobodan Onak, Krzysztof Sankowski, Piotr Round compression for parallel matching algorithms |
| title | Round compression for parallel matching algorithms |
| title_full | Round compression for parallel matching algorithms |
| title_fullStr | Round compression for parallel matching algorithms |
| title_full_unstemmed | Round compression for parallel matching algorithms |
| title_short | Round compression for parallel matching algorithms |
| title_sort | round compression for parallel matching algorithms |
| url | https://hdl.handle.net/1721.1/137790 |
| work_keys_str_mv | AT czumajartur roundcompressionforparallelmatchingalgorithms AT łackijakub roundcompressionforparallelmatchingalgorithms AT madryaleksander roundcompressionforparallelmatchingalgorithms AT mitrovicslobodan roundcompressionforparallelmatchingalgorithms AT onakkrzysztof roundcompressionforparallelmatchingalgorithms AT sankowskipiotr roundcompressionforparallelmatchingalgorithms |