Exponential Speedup over Locality in MPC with Optimal Memory

Authors Alkida Balliu , Sebastian Brandt , Manuela Fischer , Rustam Latypov , Yannic Maus , Dennis Olivetti , Jara Uitto



PDF
Thumbnail PDF

File

LIPIcs.DISC.2022.9.pdf
  • Filesize: 0.83 MB
  • 21 pages

Document Identifiers

Author Details

Alkida Balliu
  • Gran Sasso Science Institute, L'Aquila, Italy
Sebastian Brandt
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Manuela Fischer
  • ETH Zürich, Switzerland
Rustam Latypov
  • Aalto University, Espoo, Finland
Yannic Maus
  • TU Graz, Austria
Dennis Olivetti
  • Gran Sasso Science Institute, L'Aquila, Italy
Jara Uitto
  • Aalto University, Espoo, Finland

Cite AsGet BibTex

Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, and Jara Uitto. Exponential Speedup over Locality in MPC with Optimal Memory. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.DISC.2022.9

Abstract

Locally Checkable Labeling (LCL) problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example problems in this class include maximal matching, maximal independent set, and coloring problems. A successful line of research has been studying the complexities of LCL problems on paths/cycles, trees, and general graphs, providing many interesting results for the LOCAL model of distributed computing. In this work, we initiate the study of LCL problems in the low-space Massively Parallel Computation (MPC) model. In particular, on forests, we provide a method that, given the complexity of an LCL problem in the LOCAL model, automatically provides an exponentially faster algorithm for the low-space MPC setting that uses optimal global memory, that is, truly linear. While restricting to forests may seem to weaken the result, we emphasize that all known (conditional) lower bounds for the MPC setting are obtained by lifting lower bounds obtained in the distributed setting in tree-like networks (either forests or high girth graphs), and hence the problems that we study are challenging already on forests. Moreover, the most important technical feature of our algorithms is that they use optimal global memory, that is, memory linear in the number of edges of the graph. In contrast, most of the state-of-the-art algorithms use more than linear global memory. Further, they typically start with a dense graph, sparsify it, and then solve the problem on the residual graph, exploiting the relative increase in global memory. On forests, this is not possible, because the given graph is already as sparse as it can be, and using optimal memory requires new solutions.

Subject Classification

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

Metrics

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

References

  1. Noga Alon, László Babai, and Alon Itai. A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem. Journal of Algorithms, pages 567-583, 1986. URL: https://doi.org/10.1016/0196-6774(86)90019-2.
  2. Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. Parallel algorithms for geometric graph problems. In Proceedings of the Symposium on Theory of Computing (STOC), pages 574-583, 2014. URL: https://doi.org/10.1145/2591796.2591805.
  3. Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela. Classification of Distributed Binary Labeling Problems. In DISC, pages 17:1-17:17, 2020. URL: https://doi.org/10.1145/3382734.3405703.
  4. Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. Lower Bounds for Maximal Matchings and Maximal Independent Sets. In the Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pages 481-497, 2019. URL: https://doi.org/10.1109/FOCS.2019.00037.
  5. Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. Distributed Δ-Coloring Plays Hide-and-Seek. In Proceedings of the Symposium on Theory of Computing (STOC), 2022. URL: http://arxiv.org/abs/2110.00643.
  6. Alkida Balliu, Sebastian Brandt, and Dennis Olivetti. Distributed Lower Bounds for Ruling Sets. In the Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pages 365-376, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00042.
  7. Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studeny, Jukka Suomela, and Aleksandr Tereshchenko. Locally Checkable Problems in Rooted Trees. In the Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pages 263-272, 2021. URL: https://doi.org/10.1145/3465084.3467934.
  8. Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and J. Suomela. Almost Global Problems in the LOCAL Model. In Proceedings of the International Symposium on Distributed Computing (DISC), pages 9:1-9:16, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.9.
  9. Alkida Balliu, Keren Censor-Hillel, Yannic Maus, Dennis Olivetti, and Jukka Suomela. Locally Checkable Labelings with Small Messages. In Proceedings of the International Symposium on Distributed Computing (DISC), pages 8:1-8:18, 2021. URL: https://doi.org/10.4230/LIPIcs.DISC.2021.8.
  10. Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, and Jukka Suomela. New Classes of Distributed Time Complexity. In Proceedings of the Symposium on Theory of Computing (STOC), pages 1307-1318, 2018. URL: https://doi.org/10.1145/3188745.3188860.
  11. Alkida Balliu, Juho Hirvonen, Dennis Olivetti, and Jukka Suomela. Hardness of Minimal Symmetry Breaking in Distributed Computing. In the Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pages 369-378, 2019. URL: https://doi.org/10.1145/3293611.3331605.
  12. Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. Journal of the ACM (JACM), 64(6):40, 2017. URL: https://doi.org/10.1145/3125644.
  13. Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M. Karp, and Jara Uitto. Massively Parallel Computation of Matching and MIS in Sparse Graphs. In the Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pages 481-490, 2019. URL: https://doi.org/10.1145/3293611.3331609.
  14. Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Łącki, and Vahab Mirrokni. Near-Optimal Massively Parallel Graph Connectivity. In the Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pages 1615-1636, 2020. URL: https://doi.org/10.1109/FOCS.2019.00095.
  15. Sebastian Brandt, Manuela Fischer, and Jara Uitto. Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with Strongly Sublinear Memory. In the Proceedings of the International Colloquium on Structural Information and Communication Complexity, pages 124-138, 2019. URL: https://doi.org/10.1007/978-3-030-24922-9_9.
  16. Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto. A Lower Bound for the Distributed Lovász Local Lemma. In Proceedings of the Symposium on Theory of Computing (STOC), pages 479-488. ACM Press, 2016. URL: https://doi.org/10.1145/2897518.2897570.
  17. Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Patric R.J. Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, and Przemysław Uznański. LCL Problems on Grids. In the Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pages 101-110, 2017. URL: https://doi.org/10.1145/3087801.3087833.
  18. Yi-Jun Chang. The Complexity Landscape of Distributed Locally Checkable Problems on Trees. In Proceedings of the International Symposium on Distributed Computing (DISC), pages 18:1-18:17, 2020. URL: https://doi.org/10.4230/LIPIcs.DISC.2020.18.
  19. Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng. The Complexity of (Δ + 1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation. In the Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pages 471-480, 2019. Google Scholar
  20. Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto. Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma. ACM Transactions on Algorithms (TALG), pages 1-51, 2019. URL: https://doi.org/10.1145/3365004.
  21. Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model. SIAM Journal on Computing, 48(1):122-143, 2019. URL: https://doi.org/10.1137/17M1117537.
  22. Yi-Jun Chang and Seth Pettie. A Time Hierarchy Theorem for the LOCAL Model. SIAM Journal of Computing, 48(1):33-69, 2019. URL: https://doi.org/10.1137/17M1157957.
  23. Richard Cole and Uzi Vishkin. Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking. Inf. Control., 70(1):32-53, 1986. URL: https://doi.org/10.1016/S0019-9958(86)80023-7.
  24. Sam Coy and Artur Czumaj. Deterministic massively parallel connectivity. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, 2022. URL: https://doi.org/10.1145/3519935.3520055.
  25. Artur Czumaj, Peter Davies, and Merav Parter. Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space. In Proceedings of the Symposium on Parallel Algorithms and Architectures (SPAA), pages 175-185, 2020. URL: https://doi.org/10.1145/3350755.3400282.
  26. Artur Czumaj, Peter Davies, and Merav Parter. Component Stability in Low-Space Massively Parallel Computation. In the Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pages 481-491, 2021. URL: https://doi.org/10.1145/3465084.3467903.
  27. Artur Czumaj, Peter Davies, and Merav Parter. Improved Deterministic (Δ+1) Coloring in Low-Space MPC. In the Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pages 469-479, 2021. URL: https://doi.org/10.1145/3465084.3467937.
  28. Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified Data Processing on Large Clusters. In Communications of the ACM, pages 107-113, 2008. Google Scholar
  29. Michal Dory, Orr Fischer, Seri Khoury, and Dean Leitersdorf. Constant-Round Spanners and Shortest Paths in Congested Clique and MPC. In the Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pages 223-233, 2021. URL: https://doi.org/10.1145/3465084.3467928.
  30. Manuela Fischer and Mohsen Ghaffari. Sublogarithmic Distributed Algorithms for Lovász Local Lemma, and the Complexity Hierarchy. In Proceedings of the International Symposium on Distributed Computing (DISC), pages 18:1-18:16, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.18.
  31. Mohsen Ghaffari. An Improved Distributed Algorithm for Maximal Independent Set. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 270-277, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch20.
  32. Mohsen Ghaffari, Christoph Grunau, and Ce Jin. Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond. In Proceedings of the International Symposium on Distributed Computing (DISC), pages 34:1-34:18, 2020. URL: https://doi.org/10.4230/LIPIcs.DISC.2020.34.
  33. Mohsen Ghaffari, Christoph Grunau, and Václav Rozhon. Improved Deterministic Network Decomposition. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2904-2923, 2021. URL: https://doi.org/10.1137/1.9781611976465.173.
  34. Mohsen Ghaffari, David G. Harris, and Fabian Kuhn. On Derandomizing Local Distributed Algorithms. In the Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pages 662-673, 2018. URL: https://doi.org/10.1109/FOCS.2018.00069.
  35. Mohsen Ghaffari, Fabian Kuhn, and Jara Uitto. Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds. In the Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pages 1650-1663, 2019. URL: https://doi.org/10.1109/FOCS.2019.00097.
  36. Mohsen Ghaffari and Hsin-Hao Su. Distributed Degree Splitting, Edge Coloring, and Orientations. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2505-2523, 2017. URL: https://doi.org/10.1137/1.9781611974782.166.
  37. Mohsen Ghaffari and Jara Uitto. Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1636-1653, 2019. URL: https://doi.org/10.1137/1.9781611975482.99.
  38. Andrew V. Goldberg, Serge A. Plotkin, and Gregory E. Shannon. Parallel symmetry-breaking in sparse graphs. SIAM J. Discret. Math., 1(4):434-446, 1988. URL: https://doi.org/10.1137/0401044.
  39. Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, Searching, and Simulation in the Mapreduce Framework. In International Symposium on Algorithms and Computation (ISAAC), pages 374-383, 2011. URL: https://doi.org/10.1007/978-3-642-25591-5_39.
  40. Christoph Grunau, Václav Rozhon, and Sebastian Brandt. The landscape of distributed complexities on trees and beyond. In Alessia Milani and Philipp Woelfel, editors, PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022, pages 37-47. ACM, 2022. URL: https://doi.org/10.1145/3519270.3538452.
  41. Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks. In SIGOPS Operating Systems Review, pages 59-72, 2007. URL: https://doi.org/10.1145/1272996.1273005.
  42. Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A Model of Computation for MapReduce. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 938-948, 2010. URL: https://doi.org/10.1137/1.9781611973075.76.
  43. Raimondas Kiveris, Silvio Lattanzi, Vahab Mirrokni, Vibhor Rastogi, and Sergei Vassilvitskii. Connected Components in MapReduce and Beyond. In ACM Symposium on Cloud Computing, pages 18:1-18:13, 2014. URL: https://doi.org/10.1145/2670979.2670997.
  44. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower and upper bounds. Journal of the ACM (JACM), 63:17:1-17:44, 2016. URL: https://doi.org/10.1145/2742012.
  45. Christoph Lenzen and Roger Wattenhofer. Brief Announcement: Exponential Speed-Up of Local Algorithms Using Non-Local Communication. In the Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pages 295-296, 2010. URL: https://doi.org/10.1145/1835698.1835772.
  46. Nathan Linial. Distributive Graph Algorithms - Global Solutions from Local Data. In the Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pages 331-335, 1987. URL: https://doi.org/10.1109/SFCS.1987.20.
  47. Nathan Linial. Locality in Distributed Graph Algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. URL: https://doi.org/10.1137/0221015.
  48. Michael Luby. A Simple Parallel Algorithm for the Maximal Independent Set Problem. In Proceedings of the Symposium on Theory of Computing (STOC), pages 1-10, 1985. URL: https://doi.org/10.1145/22145.22146.
  49. Gary L. Miller and John H. Reif. Parallel Tree Contraction Part 1: Fundamentals. Adv. Comput. Res., 5:47-72, 1989. Google Scholar
  50. Moni Naor and Larry Stockmeyer. What Can Be Computed Locally? SIAM Journal on Computing, 24(6):1259-1277, 1995. URL: https://doi.org/10.1137/S0097539793254571.
  51. Alessandro Panconesi and Romeo Rizzi. Some Simple Distributed Algorithms for Sparse Networks. Distributed Computing, 14(2):97-100, 2001. URL: https://doi.org/10.1007/PL00008932.
  52. David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, 2000. URL: https://doi.org/10.1137/1.9780898719772.
  53. Tim Roughgarden, Sergei Vassilvitskii, and Joshua R. Wang. Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation). J. ACM, pages 1-12, 2018. URL: https://doi.org/10.1145/3232536.
  54. Václav Rozhon and Mohsen Ghaffari. Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization. In Proceedings of the Symposium on Theory of Computing (STOC), pages 350-363, 2020. URL: https://doi.org/10.1145/3357713.3384298.
  55. Tom White. Hadoop: The Definitive Guide. O'Reilly Media, Inc., 2012. URL: https://doi.org/10.5555/1717298.
  56. Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. Spark: Cluster Computing with Working Sets. In USENIX Workshop on Hot Topics in Cloud Computing (HotCloud), 2010. URL: https://doi.org/10.5555/1863103.1863113.
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