Document Open Access Logo

Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem

Authors Mélanie Cambus , Fabian Kuhn , Shreyas Pai , Jara Uitto

PDF
Thumbnail PDF

File

LIPIcs.DISC.2023.11.pdf
  • Filesize: 0.68 MB
  • 12 pages

Document Identifiers

Author Details

Mélanie Cambus
  • Aalto University, Finland
Fabian Kuhn
  • University of Freiburg, Germany
Shreyas Pai
  • Aalto University, Finland
Jara Uitto
  • Aalto University, Finland

Funding

  • Cambus, Mélanie: Academy of Finland, Grant 334238.
  • Pai, Shreyas: Academy of Finland, Grant 334238.

Cite As Get BibTex

Mélanie Cambus, Fabian Kuhn, Shreyas Pai, and Jara Uitto. Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 11:1-11:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.DISC.2023.11

Abstract

In this work, we present a constant-round algorithm for the 2-ruling set problem in the Congested Clique model. As a direct consequence, we obtain a constant round algorithm in the MPC model with linear space-per-machine and optimal total space. Our results improve on the O(log log log n)-round algorithm by [HPS, DISC'14] and the O(log log Δ)-round algorithm by [GGKMR, PODC'18]. Our techniques can also be applied to the semi-streaming model to obtain an O(1)-pass algorithm.
Our main technical contribution is a novel sampling procedure that returns a small subgraph such that almost all nodes in the input graph are adjacent to the sampled subgraph. An MIS on the sampled subgraph provides a 2-ruling set for a large fraction of the input graph. As a technical challenge, we must handle the remaining part of the graph, which might still be relatively large. We overcome this challenge by showing useful structural properties of the remaining graph and show that running our process twice yields a 2-ruling set of the original input graph with high probability.

Subject Classification

ACM Subject Classification
  • Theory of computation → Massively parallel algorithms
  • Theory of computation → Streaming models
Keywords
  • Ruling Sets
  • Parallel Algorithms
  • Congested Clique
  • Massively Parallel Computing
  • Semi-Streaming

Metrics

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

Related Versions

References

  1. Kook Jin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, and Anthony Wirth. Correlation Clustering in Data Streams. In International Conference on Machine Learning (ICML), pages 2237-2246, 2015. Google Scholar
  2. Noga Alon, Lásló 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. Google Scholar
  3. Sepehr Assadi and Aditi Dudeja. Ruling Sets in Random Order and Adversarial Streams. In Seth Gilbert, editor, 35th International Symposium on Distributed Computing (DISC 2021), volume 209 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1-6:18, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.DISC.2021.6.
  4. Sepehr Assadi, Gillat Kol, and Zhijun Zhang. Rounds vs communication tradeoffs for maximal independent sets. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 1193-1204. IEEE, 2022. Google Scholar
  5. Paul Beame, Paraschos Koutris, and Dan Suciu. Communication Steps for Parallel Query Processing. J. ACM, 64(6), 2017. URL: https://doi.org/10.1145/3125644.
  6. Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi. Semi-mapreduce meets congested clique, 2018. URL: https://doi.org/10.48550/ARXIV.1802.10297.
  7. Andrew Berns, James Hegeman, and Sriram V. Pemmaraju. Super-Fast Distributed Algorithms for Metric Facility Location. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), pages 428-439, 2012. Google Scholar
  8. Graham Cormode, Jacques Dark, and Christian Konrad. Independent Sets in Vertex-Arrival Streams. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 45:1-45:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.45.
  9. Artur Czumaj, Peter Davies, and Merav Parter. Simple, deterministic, constant-round coloring in the congested clique. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), PODC '20, pages 309-318, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3382734.3405751.
  10. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. Graph Distances in the Streaming Model: The Value of Space. In the Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 745-754, 2005. Google Scholar
  11. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On Graph Problems in a Semi-Streaming Model. Theor. Comput. Sci., 348(2):207-216, 2005. URL: https://doi.org/10.1016/j.tcs.2005.09.013.
  12. Mohsen Ghaffari. An improved distributed algorithm for maximal independent set. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 270-277. SIAM, 2016. Google Scholar
  13. Mohsen Ghaffari. Distributed MIS via All-to-All Communication. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 141-149, 2017. URL: https://doi.org/10.1145/3087801.3087830.
  14. Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrović, and Ronitt Rubinfeld. Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover. In the Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 129-138, 2018. Google Scholar
  15. Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, Searching, and Simulation in the Mapreduce Framework. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC), pages 374-383, 2011. URL: https://doi.org/10.1007/978-3-642-25591-5_39.
  16. James Hegeman, Sriram Pemmaraju, and Vivek Sardeshmukh. Near-Constant-Time Distributed Algorithms on a Congested Clique. In Proceedings of the International Symposium on Distributed Computing (DISC), pages 514-530, 2014. URL: https://doi.org/10.1007/978-3-662-45174-8_35.
  17. James W. Hegeman and Sriram V. Pemmaraju. Lessons from the congested clique applied to mapreduce. Theoretical Computer Science, 608:268-281, 2015. Structural Information and Communication Complexity. URL: https://doi.org/10.1016/j.tcs.2015.09.029.
  18. Tanmay Inamdar, Shreyas Pai, and Sriram V. Pemmaraju. Large-Scale Distributed Algorithms for Facility Location with Outliers. In Jiannong Cao, Faith Ellen, Luis Rodrigues, and Bernardo Ferreira, editors, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018), volume 125 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1-5:16, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2018.5.
  19. Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. A Model of Computation for MapReduce. In the Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 938-948, 2010. Google Scholar
  20. Christian Konrad, Sriram V Pemmaraju, Talal Riaz, and Peter Robinson. The complexity of symmetry breaking in massive graphs. In 33rd International Symposium on Distributed Computing (DISC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  21. Christoph Lenzen. Optimal deterministic routing and sorting on the congested clique. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, pages 42-50. Association for Computing Machinery, 2013. URL: https://doi.org/10.1145/2484239.2501983.
  22. Zvi Lotker, Elan Pavlov, Boaz Patt-Shamir, and David Peleg. Mst construction in o(log log n) communication rounds. In Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures, pages 94-100. Association for Computing Machinery, 2003. URL: https://doi.org/10.1145/777412.777428.
  23. M. Luby. A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM Journal on Computing, 15:1036-1053, 1986. Google Scholar
  24. Colin McDiarmid. Concentration, pages 195-248. Springer Berlin Heidelberg, Berlin, Heidelberg, 1998. URL: https://doi.org/10.1007/978-3-662-12788-9_6.
  25. Colin McDiarmid et al. On the method of bounded differences. Surveys in combinatorics, 141(1):148-188, 1989. Google Scholar
  26. S. Muthukrishnan. Data Streams: Algorithms and Applications. Theoretical Computer Science, 1(2):117-236, 2005. URL: https://doi.org/10.1561/0400000002.
  27. Krzysztof Nowicki. A deterministic algorithm for the mst problem in constant rounds of congested clique. In Proceedings of the ACM Symposium on Theory of Computing (STOC), STOC 2021, pages 1154-1165, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3406325.3451136.
  28. Shreyas Pai and Sriram V. Pemmaraju. Brief Announcement: Deterministic Massively Parallel Algorithms for Ruling Sets. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 366-368, 2022. URL: https://doi.org/10.1145/3519270.3538472.
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