Document Open Access Logo

Improved Deterministic Connectivity in Massively Parallel Computation

Authors Manuela Fischer , Jeff Giliberti , Christoph Grunau

PDF
Thumbnail PDF

File

LIPIcs.DISC.2022.22.pdf
  • Filesize: 0.8 MB
  • 17 pages

Document Identifiers

Author Details

Manuela Fischer
  • ETH Zürich, Switzerland
Jeff Giliberti
  • ETH Zürich, Switzerland
Christoph Grunau
  • ETH Zürich, Switzerland

Funding

  • Grunau, Christoph: Supported by the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No. 853109).

Cite As Get BibTex

Manuela Fischer, Jeff Giliberti, and Christoph Grunau. Improved Deterministic Connectivity in Massively Parallel Computation. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.DISC.2022.22

Abstract

A long line of research about connectivity in the Massively Parallel Computation model has culminated in the seminal works of Andoni et al. [FOCS'18] and Behnezhad et al. [FOCS'19]. They provide a randomized algorithm for low-space MPC with conjectured to be optimal round complexity O(log D + log log_{m/n} n) and O(m) space, for graphs on n vertices with m edges and diameter D. Surprisingly, a recent result of Coy and Czumaj [STOC'22] shows how to achieve the same deterministically. Unfortunately, however, their algorithm suffers from large local computation time. 
We present a deterministic connectivity algorithm that matches all the parameters of the randomized algorithm and, in addition, significantly reduces the local computation time to nearly linear. 
Our derandomization method is based on reducing the amount of randomness needed to allow for a simpler efficient search. While similar randomness reduction approaches have been used before, our result is not only strikingly simpler, but it is the first to have efficient local computation. This is why we believe it to serve as a starting point for the systematic development of computation-efficient derandomization approaches in low-memory MPC.

Subject Classification

ACM Subject Classification
  • Theory of computation → Massively parallel algorithms
  • Theory of computation → MapReduce algorithms
Keywords
  • Massively Parallel Computation
  • MPC
  • MapReduce
  • Deterministic Algorithms
  • Connectivity
  • Hitting Set
  • Maximum Matching
  • Derandomization

Metrics

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

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, 7(4):567-583, 1986. URL: https://doi.org/10.1016/0196-6774(86)90019-2.
  2. Noga Alon and Joel H Spencer. The probabilistic method. John Wiley & Sons, 2016. Google Scholar
  3. Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, and Peilin Zhong. Parallel graph connectivity in log diameter rounds. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 674-685, 2018. URL: https://doi.org/10.1109/FOCS.2018.00070.
  4. Sepehr Assadi, Xiaorui Sun, and Omri Weinstein. Massively parallel algorithms for finding well-connected components in sparse graphs. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 461-470, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3293611.3331596.
  5. Philipp Bamberger, Fabian Kuhn, and Yannic Maus. Efficient deterministic distributed coloring with small bandwidth. In Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC '20, pages 243-252, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3382734.3404504.
  6. 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 Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 481-490, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3293611.3331609.
  7. Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, and Vahab Mirrokni. Near-optimal massively parallel graph connectivity. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1615-1636, 2019. URL: https://doi.org/10.1109/FOCS.2019.00095.
  8. J.Lawrence Carter and Mark N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143-154, 1979. URL: https://doi.org/10.1016/0022-0000(79)90044-8.
  9. Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. Derandomizing local distributed algorithms under bandwidth restrictions. Distributed Computing, 33(3):349-366, June 2020. URL: https://doi.org/10.1007/s00446-020-00376-1.
  10. Moses Charikar, Weiyun Ma, and Li-Yang Tan. Brief announcement: A randomness-efficient massively parallel algorithm for connectivity. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC'21, pages 431-433, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3465084.3467951.
  11. Benny Chor and Oded Goldreich. On the power of two-point based sampling. Journal of Complexity, 5(1):96-106, 1989. URL: https://doi.org/10.1016/0885-064X(89)90015-0.
  12. Sam Coy and Artur Czumaj. Deterministic massively parallel connectivity. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pages 162-175, New York, NY, USA, 2022. Association for Computing Machinery. URL: https://doi.org/10.1145/3519935.3520055.
  13. Artur Czumaj, Peter Davies, and Merav Parter. Simple, deterministic, constant-round coloring in the congested clique. In Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC '20, pages 309-318, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3382734.3405751.
  14. Artur Czumaj, Peter Davies, and Merav Parter. Component stability in low-space massively parallel computation. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC'21, pages 481-491, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3465084.3467903.
  15. Artur Czumaj, Peter Davies, and Merav Parter. Graph sparsification for derandomizing massively parallel computation with low space. ACM Trans. Algorithms, 17(2), May 2021. URL: https://doi.org/10.1145/3451992.
  16. Artur Czumaj, Peter Davies, and Merav Parter. Improved deterministic (delta+1) coloring in low-space mpc. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC'21, pages 469-479, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3465084.3467937.
  17. Jeffrey Dean and Sanjay Ghemawat. Mapreduce: Simplified data processing on large clusters. Commun. ACM, 51(1):107-113, January 2008. URL: https://doi.org/10.1145/1327452.1327492.
  18. Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, and Boban Veličković. Efficient approximation of product distributions. Random Structures & Algorithms, 13(1):1-16, 1998. URL: https://doi.org/10.1002/(SICI)1098-2418(199808)13:1<1::AID-RSA1>3.0.CO;2-W.
  19. Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein, and Zoya Svitkina. On distributing symmetric streaming computations. ACM Trans. Algorithms, 6(4), September 2010. URL: https://doi.org/10.1145/1824777.1824786.
  20. Mohsen Ghaffari, Christoph Grunau, and Ce Jin. Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond. In Hagit Attiya, editor, 34th International Symposium on Distributed Computing (DISC 2020), volume 179 of Leibniz International Proceedings in Informatics (LIPIcs), pages 34:1-34:18, Dagstuhl, Germany, 2020. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.DISC.2020.34.
  21. Mohsen Ghaffari and Fabian Kuhn. Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set. In Ulrich Schmid and Josef Widder, editors, 32nd International Symposium on Distributed Computing (DISC 2018), volume 121 of Leibniz International Proceedings in Informatics (LIPIcs), pages 29:1-29:17, Dagstuhl, Germany, 2018. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.29.
  22. Mohsen Ghaffari, Fabian Kuhn, and Jara Uitto. Conditional hardness results for massively parallel computation from distributed lower bounds. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1650-1663, 2019. URL: https://doi.org/10.1109/FOCS.2019.00097.
  23. Mohsen Ghaffari and Jara Uitto. Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation. In Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1636-1653, 2019. URL: https://doi.org/10.1137/1.9781611975482.99.
  24. Michael T. Goodrich. Communication-efficient parallel sorting. SIAM Journal on Computing, 29(2):416-432, 1999. URL: https://doi.org/10.1137/S0097539795294141.
  25. Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation in the mapreduce framework. In Takao Asano, Shin-ichi Nakano, Yoshio Okamoto, and Osamu Watanabe, editors, Algorithms and Computation, pages 374-383, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-642-25591-5_39.
  26. Tomasz Jurdziński and Krzysztof Nowicki. MST in O(1) Rounds of Congested Clique. In Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2620-2632, 2018. URL: https://doi.org/10.1137/1.9781611975031.167.
  27. Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for mapreduce. In Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 938-948, 2010. URL: https://doi.org/10.1137/1.9781611973075.76.
  28. Fabian Kuhn. Weak graph colorings: Distributed algorithms and applications. In Proceedings of the Twenty-First Annual Symposium on Parallelism in Algorithms and Architectures, SPAA '09, pages 138-144, New York, NY, USA, 2009. Association for Computing Machinery. URL: https://doi.org/10.1145/1583991.1584032.
  29. Jakub Lacki, Vahab S. Mirrokni, and Michal Wlodarczyk. Connected components at scale via local contractions. CoRR, abs/1807.10727, 2018. URL: http://arxiv.org/abs/1807.10727.
  30. Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. Filtering: A method for solving graph problems in mapreduce. In Proceedings of the Twenty-Third Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '11, pages 85-94, New York, NY, USA, 2011. Association for Computing Machinery. URL: https://doi.org/10.1145/1989493.1989505.
  31. Christoph Lenzen and Roger Wattenhofer. Brief announcement: Exponential speed-up of local algorithms using non-local communication. In Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC '10, pages 295-296, New York, NY, USA, 2010. Association for Computing Machinery. URL: https://doi.org/10.1145/1835698.1835772.
  32. Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. URL: https://doi.org/10.1137/0221015.
  33. Sixue Cliff Liu, Robert E. Tarjan, and Peilin Zhong. Connected Components on a PRAM in Log Diameter Time, pages 359-369. Association for Computing Machinery, New York, NY, USA, 2020. URL: https://doi.org/10.1145/3350755.3400249.
  34. Michael Luby. Removing randomness in parallel computation without a processor penalty. Journal of Computer and System Sciences, 47(2):250-286, 1993. URL: https://doi.org/10.1016/0022-0000(93)90033-S.
  35. Michael Luby and Avi Wigderson. Pairwise independence and derandomization. Foundations and Trends in Theoretical Computer Science, 1(4):237-301, 2006. URL: https://doi.org/10.1561/0400000009.
  36. Rajeev Motwani and Prabhakar Raghavan. Randomized algorithms. Cambridge university press, 1995. Google Scholar
  37. Danupon Nanongkai and Michele Scquizzato. Equivalence classes and conditional hardness in massively parallel computations. Distributed Computing, 35(2):165-183, 2022. URL: https://doi.org/10.1007/s00446-021-00418-2.
  38. Krzysztof Nowicki. A deterministic algorithm for the mst problem in constant rounds of congested clique. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1154-1165, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3406325.3451136.
  39. Merav Parter and Eylon Yogev. Congested Clique Algorithms for Graph Spanners. In Ulrich Schmid and Josef Widder, editors, 32nd International Symposium on Distributed Computing (DISC 2018), volume 121 of Leibniz International Proceedings in Informatics (LIPIcs), pages 40:1-40:18, Dagstuhl, Germany, 2018. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.40.
  40. Prabhakar Raghavan. Probabilistic construction of deterministic algorithms: Approximating packing integer programs. Journal of Computer and System Sciences, 37(2):130-143, 1988. URL: https://doi.org/10.1016/0022-0000(88)90003-7.
  41. Tim Roughgarden, Sergei Vassilvitskii, and Joshua R. Wang. Shuffles and circuits (on lower bounds for modern parallel computation). J. ACM, 65(6), November 2018. URL: https://doi.org/10.1145/3232536.
  42. Mark N. Wegman and J. Lawrence Carter. New classes and applications of hash functions. In 20th Annual Symposium on Foundations of Computer Science (sfcs 1979), pages 175-182, 1979. URL: https://doi.org/10.1109/SFCS.1979.26.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact