Brief Announcement: Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees

Sebastian Brandt, Rustam Latypov, Jara Uitto

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

6 Downloads (Pure)

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.
Original languageEnglish
Title of host publication35th International Symposium on Distributed Computing (DISC 2021)
EditorsSeth Gilbert
PublisherSchloss Dagstuhl-Leibniz-Zentrum fuer Informatik
Number of pages4
ISBN (Electronic)9783959772105
DOIs
Publication statusPublished - 2021
MoE publication typeA4 Article in a conference publication
EventInternational Symposium on Distributed Computing - Virtual, Online, Freiburg, Germany
Duration: 4 Oct 20218 Oct 2021
Conference number: 35

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik
Volume209
ISSN (Electronic)1868-8969

Conference

ConferenceInternational Symposium on Distributed Computing
Abbreviated titleDISC
Country/TerritoryGermany
CityFreiburg
Period04/10/202108/10/2021

Fingerprint

Dive into the research topics of 'Brief Announcement: Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees'. Together they form a unique fingerprint.

Cite this