research-article

Open access

Fast Dynamic Programming in Trees in the MPC Model

Authors:

Rustam Latypov,

Hossein VahidiAuthors Info & Claims

SPAA '23: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures

Pages 443 - 453

https://doi.org/10.1145/3558481.3591098

Published: 17 June 2023 Publication History

Abstract

We present a deterministic algorithm for solving a wide range of dynamic programming problems in trees in O(log D) rounds in the massively parallel computation model (MPC), with O(nδ) words of local memory per machine, for any given constant 0 < δ < 1. Here D is the diameter of the tree and n is the number of nodes---we emphasize that our running time is independent of n.

Our algorithm can solve many classical graph optimization problems such as maximum weight independent set, maximum weight matching, minimum weight dominating set, and minimum weight vertex cover. It can also be used to solve many accumulation tasks in which some aggregate information is propagated upwards or downwards in the tree---this includes, for example, computing the sum, minimum, or maximum of the input labels in each subtree, as well as many inference tasks commonly solved with belief propagation. Our algorithm can also solve any locally checkable labeling problem (LCLs) in trees. Our algorithm works for any reasonable representation of the input tree; for example, the tree can be represented as a list of edges or as a string with nested parentheses or tags. The running time of O(log D) rounds is also known to be necessary, assuming the widely-believed 2-cycle conjecture.

Our algorithm strictly improves on two prior algorithms: Bateni, Behnezhad, Derakhshan, Hajiaghayi, and Mirrokni [ICALP'18] solve problems of these flavors in O(log n) rounds, while our algorithm is much faster in low-diameter trees. Furthermore, their algorithm also uses randomness, while our algorithm is deterministic. Balliu, Latypov, Maus, Olivetti, and Uitto [SODA'23] solve only locally checkable labeling problems in O(log D) rounds, while our algorithm can be applied to a much broader family of problems.

Supplemental Material

MP4 File

A full version of this paper is available on arXiv: https://arxiv.org/abs/2305.03693

Download
215.71 MB

References

[1]

Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, and Peilin Zhong. 2018. Parallel Graph Connectivity in Log Diameter Rounds. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, Mikkel Thorup (Ed.). IEEE Computer Society, 674--685. https://doi.org/10.1109/FOCS.2018.00070

[2]

Sepehr Assadi, Xiaorui Sun, and Omri Weinstein. 2019. Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, Peter Robinson and Faith Ellen (Eds.). ACM, 461--470. https://doi.org/10.1145/3293611.3331596

Digital Library

[3]

Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, and Jara Uitto. 2022. Exponential Speedup over Locality in MPC with Optimal Memory. In 36th International Symposium on Distributed Computing, DISC 2022, October 25-27, 2022, Augusta, Georgia, USA (LIPIcs, Vol. 246), Christian Scheideler (Ed.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 9:1--9:21. https://doi.org/10.4230/LIPIcs.DISC.2022.9

[4]

Alkida Balliu, Rustam Latypov, Yannic Maus, Dennis Olivetti, and Jara Uitto. 2023. Optimal Deterministic Massively Parallel Connectivity on Forests. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, Nikhil Bansal and Viswanath Nagarajan (Eds.). SIAM, 2589--2631. https://doi.org/10.1137/1.9781611977554.ch99

[5]

MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, and Vahab S. Mirrokni. 2018a. Brief Announcement: MapReduce Algorithms for Massive Trees. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic (LIPIcs, Vol. 107), Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 162:1--162:4. https://doi.org/10.4230/LIPIcs.ICALP.2018.162

[6]

MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, and Vahab S. Mirrokni. 2018b. Massively Parallel Dynamic Programming on Trees. CoRR, Vol. abs/1809.03685 (2018). showeprint[arXiv]1809.03685 http://arxiv.org/abs/1809.03685

[7]

Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, and Vahab S. Mirrokni. 2019. Near-Optimal Massively Parallel Graph Connectivity. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, David Zuckerman (Ed.). IEEE Computer Society, 1615--1636. https://doi.org/10.1109/FOCS.2019.00095

[8]

Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni, and Warren Schudy. 2021. Massively Parallel Computation via Remote Memory Access. ACM Trans. Parallel Comput., Vol. 8, 3 (2021), 13:1--13:25. https://doi.org/10.1145/3470631

Digital Library

[9]

Hans L. Bodlaender. 1988. Dynamic Programming on Graphs with Bounded Treewidth. In Automata, Languages and Programming, 15th International Colloquium, ICALP88, Tampere, Finland, July 11-15, 1988, Proceedings (Lecture Notes in Computer Science, Vol. 317), Timo Lepistö and Arto Salomaa (Eds.). Springer, 105--118. https://doi.org/10.1007/3-540-19488-6_110

[10]

Tim Bray, Jean Paoli, C. M. Sperberg-McQueen, Eve Maler, and François Yergeau (Eds.). 2008. Extensible Markup Language (XML) 1.0 (Fifth Edition). https://www.w3.org/TR/REC-xml/

[11]

Sam Coy and Artur Czumaj. 2022. Deterministic massively parallel connectivity. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, Stefano Leonardi and Anupam Gupta (Eds.). ACM, 162--175. https://doi.org/10.1145/3519935.3520055

Digital Library

[12]

Artur Czumaj, Peter Davies, and Merav Parter. 2021. Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space. ACM Trans. Algorithms, Vol. 17, 2 (2021), 16:1--16:27. https://doi.org/10.1145/3451992

Digital Library

[13]

Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani. 2008. Algorithms. McGraw-Hill.

[14]

Mohsen Ghaffari, Fabian Kuhn, and Jara Uitto. 2019. Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, David Zuckerman (Ed.). IEEE Computer Society, 1650--1663. https://doi.org/10.1109/FOCS.2019.00097

[15]

Jeremy Gibbons, Wentong Cai, and David B. Skillicorn. 1994. Efficient Parallel Algorithms for Tree Accumulations. Sci. Comput. Program., Vol. 23, 1 (1994), 1--18. https://doi.org/10.1016/0167-6423(94)00013-1

Digital Library

[16]

Michael T. Goodrich. 1999. Communication-Efficient Parallel Sorting. SIAM J. Comput., Vol. 29, 2 (1999), 416--432. https://doi.org/10.1137/S0097539795294141

Digital Library

[17]

Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. 2011. Sorting, Searching, and Simulation in the MapReduce Framework. In Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings (Lecture Notes in Computer Science, Vol. 7074), Takao Asano, Shin-Ichi Nakano, Yoshio Okamoto, and Osamu Watanabe (Eds.). Springer, 374--383. https://doi.org/10.1007/978-3-642-25591-5_39

Digital Library

[18]

Syeda Sakira Hassan, Simo Särkkä, and Ángel F. García-Fernández. 2021. Temporal Parallelization of Inference in Hidden Markov Models. IEEE Trans. Signal Process., Vol. 69 (2021), 4875--4887. https://doi.org/10.1109/TSP.2021.3103338

[19]

Sungjin Im, Benjamin Moseley, and Xiaorui Sun. 2017. Efficient massively parallel methods for dynamic programming. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, Hamed Hatami, Pierre McKenzie, and Valerie King (Eds.). ACM, 798--811. https://doi.org/10.1145/3055399.3055460

Digital Library

[20]

Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. 2010. A Model of Computation for MapReduce. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, Moses Charikar (Ed.). SIAM, 938--948. https://doi.org/10.1137/1.9781611973075.76

[21]

Daphne Koller and Nir Friedman. 2009. Probabilistic Graphical Models: Principles and Techniques. The MIT Press.

Digital Library

[22]

Richard E. Ladner and Michael J. Fischer. 1980. Parallel Prefix Computation. J. ACM, Vol. 27, 4 (1980), 831--838. https://doi.org/10.1145/322217.322232

Digital Library

[23]

Moni Naor and Larry J. Stockmeyer. 1995. What Can be Computed Locally? SIAM J. Comput., Vol. 24, 6 (1995), 1259--1277. https://doi.org/10.1137/S0097539793254571

Digital Library

[24]

Tim Roughgarden, Sergei Vassilvitskii, and Joshua R. Wang. 2018. Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation). J. ACM, Vol. 65, 6 (2018), 41:1--41:24. https://doi.org/10.1145/3232536

Digital Library

[25]

Simo Särkkä. 2013. Bayesian Filtering and Smoothing. Cambridge University Press.

[26]

Simo Särkkä and Ángel F. García-Fernández. 2021. Temporal Parallelization of Bayesian Smoothers. IEEE Trans. Autom. Control., Vol. 66, 1 (2021), 299--306. https://doi.org/10.1109/TAC.2020.2976316

Cited By

Coy SCzumaj AMishra GMukherjee AAgrawal KPetrank E(2024)Log Diameter Rounds MST Verification and Sensitivity in MPCProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659984(269-280)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659984

Index Terms

Fast Dynamic Programming in Trees in the MPC Model
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel algorithms
      1. Massively parallel algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming
  2. Models of computation
    1. Concurrency
      1. Distributed computing models
      2. Parallel computing models

Recommendations

Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems
PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing

Assume we have a graph problem that is locally checkable but not locally solvable---given a solution we can check that it is feasible by verifying all constant-radius neighborhoods, but to find a feasible solution each node needs to explore the input ...
Log Diameter Rounds MST Verification and Sensitivity in MPC
SPAA '24: Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures

We consider two natural variants of the problem of minimum spanning tree (MST) of a graph in the parallel setting: MST verification (verifying if a given tree is an MST) and the sensitivity analysis of an MST (finding the lowest cost replacement edge for ...
Succinct and I/O Efficient Data Structures for Traversal in Trees

We present two results for path traversal in trees, where the traversal is performed in an asymptotically optimal number of I/Os and the tree structure is represented succinctly. Our first result is for bottom-up traversal that starts with a node in a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '23: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures

June 2023

504 pages

ISBN:9781450395458

DOI:10.1145/3558481

General Chair:
Kunal Agrawal
Washington University in St. Louis, USA
,
Program Chair:
Julian Shun
MIT, USA

Copyright © 2023 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
EATCS: European Association for Theoretical Computer Science

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 June 2023

Check for updates

Author Tags

Qualifiers

Research-article

Data Availability

A full version of this paper is available on arXiv: https://arxiv.org/abs/2305.03693 https://dl.acm.org/doi/10.1145/3558481.3591098#SPAA23-fp174.mp4

Funding Sources

Academy of Finland
Academy of Finland

Conference

SPAA '23

Sponsor:

SPAA '23: 35th ACM Symposium on Parallelism in Algorithms and Architectures

June 17 - 19, 2023

FL, Orlando, USA

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
229
Total Downloads

Downloads (Last 12 months)160
Downloads (Last 6 weeks)20

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Coy SCzumaj AMishra GMukherjee AAgrawal KPetrank E(2024)Log Diameter Rounds MST Verification and Sensitivity in MPCProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659984(269-280)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659984

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents