extended-abstract

Brief Announcement: Deterministic Massively Parallel Algorithms for Ruling Sets

Authors:

Shreyas Pai,

Sriram V. PemmarajuAuthors Info & Claims

PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing

Pages 366 - 368

https://doi.org/10.1145/3519270.3538472

Published: 21 July 2022 Publication History

Get Access

Abstract

In this paper we present a deterministic O(log log n)-round algorithm for the 2-ruling set problem in the Massively Parallel Computation model with Õ(n) memory; this algorithm also runs in O(log log n) rounds in the Congested Clique model. This is exponentially faster than the fastest known deterministic 2-ruling set algorithm for these models, which is simply the O(log Δ)-round deterministic Maximal Independent Set algorithm due to Czumaj, Davies, and Parter (SPAA 2020). Our result is obtained by derandomizing the 2-ruling set algorithm of Kothapalli and Pemmaraju (FSTTCS 2012).

Supplementary Material

MP4 File (S7-T5-BA.mp4)

BA presentation video

Download
286.42 MB

References

[1]

Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. 2017. Derandomizing Local Distributed Algorithms under Bandwidth Restrictions. In 31st International Symposium on Distributed Computing, DISC 2017, October 16--20, 2017, Vienna, Austria (LIPIcs, Vol. 91). https://doi.org/10.4230/LIPIcs.DISC.2017.11

Crossref

Google Scholar

[2]

Artur Czumaj, Peter Davies, and Merav Parter. 2020. Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '20). New York, NY, USA, 175--185. https://doi.org/10.1145/3350755.3400282

Digital Library

Google Scholar

[3]

James W. Hegeman, Sriram V. Pemmaraju, and Vivek Sardeshmukh. 2014. Near-Constant-Time Distributed Algorithms on a Congested Clique. In Distributed Computing - 28th International Symposium, DISC 2014, Austin, TX, USA, October 12--15, 2014. Proceedings (Lecture Notes in Computer Science, Vol. 8784), Fabian Kuhn (Ed.). Springer, 514--530. https://doi.org/10.1007/978--3--662--45174--8_35

Crossref

Google Scholar

[4]

James W. Hegeman, Sriram V. Pemmaraju, and Vivek Sardeshmukh. 2014. Near-Constant-Time Distributed Algorithms on a Congested Clique. CoRR abs/1408.2071 (2014). arXiv:1408.2071 http://arxiv.org/abs/1408.2071

Google Scholar

[5]

Howard 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. Society for Industrial and Applied Mathematics, Philadelphia, PA, 938--948. https://doi.org/10.1137/1.9781611973075.76

Crossref

Google Scholar

[6]

Kishore Kothapalli and Sriram V. Pemmaraju. 2012. Super-Fast 3-Ruling Sets. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, December 15--17, 2012, Hyderabad, India. 136--147. https://doi.org/10.4230/LIPIcs.FSTTCS.2012.136

Crossref

Google Scholar

[7]

Christoph Lenzen. 2013. Optimal Deterministic Routing and Sorting on the Congested Clique. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (PODC '13). ACM, New York, NY, USA, 42--50.

Digital Library

Google Scholar

[8]

Nathan Linial. 1992. Locality in Distributed Graph Algorithms. SIAM J. Comput. 21, 1 (1992), 193--201. https://doi.org/10.1137/0221015

Digital Library

Google Scholar

[9]

Zvi Lotker, Elan Pavlov, Boaz Patt-Shamir, and David Peleg. 2003. MST Construction in O(log log n) Communication Rounds. In Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '03). Association for Computing Machinery, New York, NY, USA, 94--100. https://doi.org/10.1145/777412.777428

Digital Library

Google Scholar

[10]

Michael Luby. 1986. A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM J. Comput. 15, 4 (1986), 1036--1053. https://doi.org/10.1137/0215074

Digital Library

Google Scholar

[11]

Shreyas Pai and Sriram V. Pemmaraju. 2022. Deterministic Massively Parallel Algorithms for Ruling Sets. https://doi.org/10.48550/ARXIV.2205.12686

Crossref

Google Scholar

[12]

J. Rompel and M. Bellare. 1994. Randomness-efficient Oblivious Sampling. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, CA, USA, 276--287. https://doi.org/10.1109/SFCS.1994.365687

Digital Library

Google Scholar

[13]

Salil P. Vadhan. 2012. Pseudorandomness. Foundations and Trends in Theoretical Computer Science 7, 1--3 (2012), 1--336. https://doi.org/10.1561/0400000010

Digital Library

Google Scholar

[14]

Grigory Yaroslavtsev and Adithya Vadapalli. 2018. Massively Parallel Algorithms and Hardness for Single-Linkage Clustering under lp Distances. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Vol. 80. PMLR, 5596--5605. http://proceedings.mlr.press/v80/yaroslavtsev18a.html

Google Scholar

Cited By

View all

Ji HKothapalli KPemmaraju SSingh A(2025)Fast Deterministic Massively Parallel Ruling Sets AlgorithmsProceedings of the 26th International Conference on Distributed Computing and Networking10.1145/3700838.3700872(152-160)Online publication date: 4-Jan-2025
https://dl.acm.org/doi/10.1145/3700838.3700872
Giliberti JParsaeian ZKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Massively Parallel Ruling Set Made DeterministicProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662816(523-526)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662816

Index Terms

Brief Announcement: Deterministic Massively Parallel Algorithms for Ruling Sets
1. Theory of computation
  1. Design and analysis of algorithms
    1. Distributed algorithms
    2. Parallel algorithms
      1. Massively parallel algorithms

Recommendations

Brief Announcement: Massively Parallel Ruling Set Made Deterministic
PODC '24: Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing

We study the deterministic complexity of the 2-Ruling Set problem in the model of Massively Parallel Computation (MPC) with linear and strongly sublinear local memory.

Linear MPC: We present a constant-round deterministic algorithm for the 2-Ruling Set ...
Fast Deterministic Massively Parallel Ruling Sets Algorithms
ICDCN '25: Proceedings of the 26th International Conference on Distributed Computing and Networking
In this paper, we present a deterministic \(\tilde{O}(\log ^{1/3}\Delta) \)-round algorithm for the 2-ruling set problem in the sublinear Massively Parallel Computation (MPC) model. This improves upon the fastest known deterministic 2-ruling set algorithm ...
Brief Announcement: Symmetry Breaking in the CONGEST Model: Time- and Message-Efficient Algorithms for Ruling Sets
PODC '17: Proceedings of the ACM Symposium on Principles of Distributed Computing

We study local symmetry breaking problems in the Congest model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. Our work is motivated by the following central question: can we break the long-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing

July 2022

509 pages

ISBN:9781450392624

DOI:10.1145/3519270

General Chair:
Alessia Milani
Aix-Marseille University, France
,
Program Chair:
Philipp Woelfel
University of Calgary, Canada

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 July 2022

Check for updates

Author Tags

Qualifiers

Extended-abstract

Conference

PODC '22

Sponsor:

PODC '22: ACM Symposium on Principles of Distributed Computing

July 25 - 29, 2022

Salerno, Italy

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
82
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)1

Reflects downloads up to 09 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ji HKothapalli KPemmaraju SSingh A(2025)Fast Deterministic Massively Parallel Ruling Sets AlgorithmsProceedings of the 26th International Conference on Distributed Computing and Networking10.1145/3700838.3700872(152-160)Online publication date: 4-Jan-2025
https://dl.acm.org/doi/10.1145/3700838.3700872
Giliberti JParsaeian ZKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Massively Parallel Ruling Set Made DeterministicProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662816(523-526)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662816

View Options

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

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

Supplementary Material

References

Cited By

Index Terms

Recommendations

Brief Announcement: Massively Parallel Ruling Set Made Deterministic

Fast Deterministic Massively Parallel Ruling Sets Algorithms

Brief Announcement: Symmetry Breaking in the CONGEST Model: Time- and Message-Efficient Algorithms for Ruling Sets

Comments

Information

Published In

Sponsors

Publisher

Publication History

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations