aalto1 untyped-item.component.html
Brief Announcement: Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
4
Series
35th International Symposium on Distributed Computing (DISC 2021), Leibniz International Proceedings in Informatics, LIPIcs ; Volume 209
Abstract
We establish scalable Massively Parallel Computation (MPC) algorithms for a family of fundamental graph problems on trees. We give a general method that, for a wide range of LCL problems, turns their message passing counterparts into exponentially faster algorithms in the sublinear MPC model. In particular, we show that any LCL on trees that has a deterministic complexity of O(n) in the LOCAL model can be sped up to O(log n) (high-complexity regime) in the sublinear MPC model and similarly n^{o(1)} to O(log log n) (intermediate-complexity regime). We emphasize, that we work on bounded degree trees and all of our algorithms work in the sublinear MPC model, where local memory is O(n^δ) for δ < 1 and global memory is O(m). For the high-complexity regime, one key ingredient is a novel pointer-chain technique and analysis that allows us to solve any solvable LCL on trees with a sublinear MPC algorithm with complexity O(log n). For the intermediate-complexity regime, we adapt the approach by Chang and Pettie [FOCS'17], who gave a canonical algorithm for solving LCL problems on trees in the LOCAL model. For the special case of 3-coloring trees, which is a natural LCL problem, we provide a conditional Ω(log log n) lower bound, implying that solving LCL problems on trees with deterministic LOCAL complexity n^{o(1)} requires Θ(log log n) deterministic time in the sublinear MPC model when using a natural family of component-stable algorithms.
Description
Keywords
Other note
Citation
Brandt, S, Latypov, R & Uitto, J 2021, Brief Announcement: Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees. in S Gilbert (ed.), 35th International Symposium on Distributed Computing (DISC 2021)., 50, Leibniz International Proceedings in Informatics, LIPIcs, vol. 209, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, International Symposium on Distributed Computing, Freiburg, Germany, 04/10/2021. https://doi.org/10.4230/LIPIcs.DISC.2021.50