2026-07-24T10:14:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14852 2024-03-06T10:55:00Z ddc:004 open_access

Brief Announcement: Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees Brandt, Sebastian Latypov, Rustam Uitto, Jara Distributed computing Locally checkable labeling problems Trees Massively Parallel Computation Sublinear memory 3-coloring 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sebastian Brandt and Rustam Latypov and Jara Uitto 2021 Is Part Of LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2021.50 urn:nbn:de:0030-drops-148521 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.50 eng https://creativecommons.org/licenses/by/4.0/legalcode