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

Authors Sebastian Brandt , Rustam Latypov , Jara Uitto



PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.50.pdf
  • Filesize: 0.55 MB
  • 4 pages

Document Identifiers

Author Details

Sebastian Brandt
  • ETH Zürich, Switzerland
Rustam Latypov
  • Aalto University, Finland
Jara Uitto
  • Aalto University, Finland

Cite AsGet BibTex

Sebastian Brandt, Rustam Latypov, and Jara Uitto. Brief Announcement: Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 50:1-50:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.DISC.2021.50

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Distributed computing
  • Locally checkable labeling problems
  • Trees
  • Massively Parallel Computation
  • Sublinear memory
  • 3-coloring

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studeny, Jukka Suomela, and Aleksandr Tereshchenko. Locally checkable problems in rooted trees. In PODC, 2021. URL: http://arxiv.org/abs/2102.09277.
  2. Alkida Balliu, Keren Censor-Hillel, Yannic Maus, Dennis Olivetti, and Jukka Suomela. Locally checkable labelings with small messages. In DISC, 2021. URL: http://arxiv.org/abs/2105.05574.
  3. Sebastian Brandt, Manuela Fischer, and Jara Uitto. Matching and MIS for uniformly sparse graphs in the low-memory MPC model. Theorerical Computer Science, 2018. URL: http://arxiv.org/abs/1807.05374.
  4. Sebastian Brandt, Manuela Fischer, and Jara Uitto. Breaking the linear-memory barrier in MPC: Fast MIS on trees with strongly sublinear memory. In SIROCCO, 2019. URL: https://doi.org/10.1007/978-3-030-24922-9_9.
  5. Yi-Jun Chang and Seth Pettie. A time hierarchy theorem for the LOCAL model. In FOCS, 2017. URL: https://doi.org/10.1109/FOCS.2017.23.
  6. Artur Czumaj, Peter Davies, and Merav Parter. Component stability in low-space massively parallel computation. In PODC, 2021. URL: http://arxiv.org/abs/2106.01880.
  7. Artur Czumaj, Peter Davies, and Merav Parter. Improved deterministic (Δ+1) coloring in low-space MPC. In PODC, 2021. URL: https://doi.org/10.1145/3465084.3467937.
  8. Michal Dory, Orr Fischer, Seri Khoury, and Dean Leitersdorf. Constant-round spanners and shortest paths in Congested Clique and MPC. In PODC, 2021. URL: https://doi.org/10.1145/3465084.3467928.
  9. Mohsen Ghaffari, Christoph Grunau, and Ce Jin. Improved MPC algorithms for MIS, matching, and coloring on trees and beyond. In DISC, 2020. URL: http://arxiv.org/abs/2002.09610.
  10. Mohsen Ghaffari, Fabian Kuhn, and Jara Uitto. Conditional hardness results for massively parallel computation from distributed lower bounds. In FOCS, 2019. URL: https://doi.org/10.1109/FOCS.2019.00097.
  11. Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for MapReduce. In SODA, 2010. URL: https://doi.org/10.1137/1.9781611973075.76.
  12. Christoph Lenzen and Roger Wattenhofer. Brief announcement: Exponential speed-up of local algorithms using non-local communication. In PODC, 2010. URL: https://doi.org/10.1145/1835698.1835772.
  13. Simon Marshall. Another simple proof of the high girth, high chromatic number theorem. The American Mathematical Monthly, 2008. URL: https://doi.org/10.1080/00029890.2008.11920498.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail