The Library
Round compression for parallel matching algorithms
Tools
Tools
Tools
Czumaj, Artur, Łącki, Jakub, Mądry, Aleksander, Mitrović, Slobodan, Onak, Krzysztof and Sankowski, Piotr (2018) Round compression for parallel matching algorithms. In: The 50th Annual ACM Symposium on Theory of Computing (STOC 2018), Los Angeles, 25-29 Jun 2018. Published in: STOC 2018 Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing pp. 471-484. ISBN 9781450355599 . doi:10.1145/3188745.3188764
|
PDF
WRAP-round-compression-parallel-matching-algorithms-Czumaj-2018.pdf - Accepted Version - Requires a PDF viewer. Download (1336Kb) | Preview |
Official URL: https://doi.org/10.1145/3188745.3188764
Abstract
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(logn) 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 $n^{1+Ω(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(logn) 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.
In this paper, we finally refute that possibility. That is, we break the above O(logn) round complexity bound even in the case of slightly sublinear memory per machine. In fact, our improvement here is almost exponential:we are able to deliver a (2+ϵ)-approximate maximum matching, for any fixed constant ϵ > 0, in $O((loglog n)^2)$ rounds.
To establish our result we need to deviate from the previous work in two important ways that are crucial for exploiting the power of the MPC model, as compared to the PRAM model. Firstly, we use vertex–based graph partitioning, instead of the edge–based approaches that were utilized so far. Secondly, we develop a technique of round compression. This technique enables one to take a (distributed) algorithm that computes an O(1) approximation of maximum matching in O(logn) independent PRAM phases and implement a super-constant number of these phases in only a constant number of MPC rounds.
| Item Type: | Conference Item (Paper) | |||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||||||||||||||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Parallel algorithms, Distributed algorithms | |||||||||||||||||||||||||||||||||
| Journal or Publication Title: | STOC 2018 Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | |||||||||||||||||||||||||||||||||
| Publisher: | ACM Press | |||||||||||||||||||||||||||||||||
| ISBN: | 9781450355599 | |||||||||||||||||||||||||||||||||
| Official Date: | 2018 | |||||||||||||||||||||||||||||||||
| Dates: |
|
|||||||||||||||||||||||||||||||||
| Page Range: | pp. 471-484 | |||||||||||||||||||||||||||||||||
| DOI: | 10.1145/3188745.3188764 | |||||||||||||||||||||||||||||||||
| Status: | Peer Reviewed | |||||||||||||||||||||||||||||||||
| Publication Status: | Published | |||||||||||||||||||||||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||||||||||||||||||||
| Date of first compliant deposit: | 3 May 2018 | |||||||||||||||||||||||||||||||||
| Date of first compliant Open Access: | 3 May 2018 | |||||||||||||||||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||||||||||||||||||||||||||
| Conference Paper Type: | Paper | |||||||||||||||||||||||||||||||||
| Title of Event: | The 50th Annual ACM Symposium on Theory of Computing (STOC 2018) | |||||||||||||||||||||||||||||||||
| Type of Event: | Conference | |||||||||||||||||||||||||||||||||
| Location of Event: | Los Angeles | |||||||||||||||||||||||||||||||||
| Date(s) of Event: | 25-29 Jun 2018 | |||||||||||||||||||||||||||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
