Component stability in low-space massively parallel computation

Czumaj A, Davies P, Parter M. 2021. Component stability in low-space massively parallel computation. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. PODC: Principles of Distributed Computing, 481–491.

Download (ext.)
OA https://arxiv.org/abs/2106.01880 [Submitted Version]

Conference Paper | Published | English
Author
Czumaj, Artur; Davies, PeterISTA ; Parter, Merav
Department
Abstract
In this paper, we study the power and limitations of component-stable 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-space MPC algorithms, 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: 1) 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. 2) We also extend the framework to obtain conditional lower bounds for deterministic algorithms and fine-grained lower bounds that depend on the maximum degree Δ. 3) 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.
Publishing Year
Date Published
2021-07-21
Proceedings Title
Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing
Publisher
Association for Computing Machinery
Acknowledgement
This work is partially supported by a Weizmann-UK Making Connections Grant, the Centre for Discrete Mathematics and its Applications (DIMAP), IBM Faculty Award, EPSRC award EP/V01305X/1, European Research Council (ERC) Grant No. 949083, the Minerva foundation with funding from the Federal German Ministry for Education and Research No. 713238, and the European Union’s Horizon 2020 programme under the Marie Skłodowska-Curie grant agreement No 754411.
Page
481–491
Conference
PODC: Principles of Distributed Computing
Conference Location
Virtual, Italy
Conference Date
2021-07-26 – 2021-07-30
IST-REx-ID

Cite this

Czumaj A, Davies P, Parter M. Component stability in low-space massively parallel computation. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery; 2021:481–491. doi:10.1145/3465084.3467903
Czumaj, A., Davies, P., & Parter, M. (2021). Component stability in low-space massively parallel computation. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (pp. 481–491). Virtual, Italy: Association for Computing Machinery. https://doi.org/10.1145/3465084.3467903
Czumaj, Artur, Peter Davies, and Merav Parter. “Component Stability in Low-Space Massively Parallel Computation.” In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, 481–491. Association for Computing Machinery, 2021. https://doi.org/10.1145/3465084.3467903.
A. Czumaj, P. Davies, and M. Parter, “Component stability in low-space massively parallel computation,” in Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, Virtual, Italy, 2021, pp. 481–491.
Czumaj A, Davies P, Parter M. 2021. Component stability in low-space massively parallel computation. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. PODC: Principles of Distributed Computing, 481–491.
Czumaj, Artur, et al. “Component Stability in Low-Space Massively Parallel Computation.” Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2021, pp. 481–491, doi:10.1145/3465084.3467903.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Web of Science

View record in Web of Science®

Sources

arXiv 2106.01880

Search this title in

Google Scholar
ISBN Search