The Library
Component stability in low-space massively parallel computation
Tools
Tools
Tools
Czumaj, Artur, Davies, Peter and Parter, Merav (2021) Component stability in low-space massively parallel computation. In: 40th Annual ACM Symposium on Principles of Distributed Computing (PODC 2021), Virtual, Italy, 26-30 Jul 2021. Published in: PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing pp. 481-491. ISBN 9781450385480. doi:10.1145/3465084.3467903
|
PDF
WRAP-component-stability-low-space-massively-parallel-computation-Czumaj-2021.pdf - Accepted Version - Requires a PDF viewer. Download (1196Kb) | Preview |
Official URL: https://doi.org/10.1145/3465084.3467903
Abstract
In this paper, we study the power and limitations of componentstable algorithms in the low-space model of Massively Parallel Computation (MPC). Recently Ghaffari, Kuhn and Uitto (FOCS 2019) introduced the class of component-stable low-spaceMPCalgorithms, which are, informally, defined as algorithms for which the outputs reported by the nodes in different connected components are required to be independent. This very natural notion was introduced to capture most (if not all) of the known efficient MPC algorithms to date, and it was the first general class of MPC algorithms for which one can show non-trivial conditional lower bounds. In this paper we enhance the framework of component-stable algorithms and investigate its effect on the complexity of randomized and deterministic low-space MPC. Our key contributions include:
• We revise and formalize the lifting approach of Ghaffari, Kuhn and Uitto. This requires a very delicate amendment of the notion of component stability, which allows us to fill in gaps in the earlier arguments.
• We also extend the framework to obtain conditional lower bounds for deterministic algorithms and fine-grained lower bounds that depend on the maximum degree Δ.
• We demonstrate a collection of natural graph problems for which non-component-stable algorithms break the conditional lower bound obtained for component-stable algorithms. This implies that, for both deterministic and randomized algorithms, component-stable algorithms are conditionally weaker than the non-component-stable ones.
Altogether our results imply that component-stability might limit the computational power of the low-space MPC model, paving the way for improved upper bounds that escape the conditional lower bound setting of Ghaffari, Kuhn, and Uitto.
| Item Type: | Conference Item (Paper) | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics 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): | Machine theory, Computational complexity, Parallel algorithms , Distributed algorithms , Graph algorithms , Numbers, Random | |||||||||||||||||||||
| Journal or Publication Title: | PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing | |||||||||||||||||||||
| Publisher: | ACM | |||||||||||||||||||||
| ISBN: | 9781450385480 | |||||||||||||||||||||
| Official Date: | 21 July 2021 | |||||||||||||||||||||
| Dates: |
|
|||||||||||||||||||||
| Page Range: | pp. 481-491 | |||||||||||||||||||||
| DOI: | 10.1145/3465084.3467903 | |||||||||||||||||||||
| Status: | Peer Reviewed | |||||||||||||||||||||
| Publication Status: | Published | |||||||||||||||||||||
| Reuse Statement (publisher, data, author rights): | © ACM, 2021. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of the 40th Annual ACM Symposium on Principles of Distributed Computing (PODC 2021) http://doi.acm.org/10.1145/nnnnnn.nnnnn | |||||||||||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||||||||
| Copyright Holders: | Copyright © 2021 ACM | |||||||||||||||||||||
| Date of first compliant deposit: | 8 June 2021 | |||||||||||||||||||||
| Date of first compliant Open Access: | 8 June 2021 | |||||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||||||||||||||
| Is Part Of: | 1 | |||||||||||||||||||||
| Conference Paper Type: | Paper | |||||||||||||||||||||
| Title of Event: | 40th Annual ACM Symposium on Principles of Distributed Computing (PODC 2021) | |||||||||||||||||||||
| Type of Event: | Conference | |||||||||||||||||||||
| Location of Event: | Virtual, Italy | |||||||||||||||||||||
| Date(s) of Event: | 26-30 Jul 2021 | |||||||||||||||||||||
| Related URLs: | ||||||||||||||||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
