Conference proceeding
Brief Announcement: Deterministic Massively Parallel Algorithms for Ruling Sets
Proceedings Of The 2022 ACM Symposium On Principles Of Distributed Computing, PODC 2022, pp.366-368
01/01/2022
DOI: 10.1145/3519270.3538472
Abstract
In this paper we present a deterministic O( log logn)-round algorithm for the 2-ruling set problem in the Massively Parallel Computation (MPC) model with O-similar to (n) memory; this algorithm also runs in O( log logn) 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 Omicron(log Delta)-round deterministic Maximal Independent Set (MIS) 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).
Details
- Title: Subtitle
- Brief Announcement: Deterministic Massively Parallel Algorithms for Ruling Sets
- Creators
- Shreyas Pai - Aalto UniversitySriram V. Pemmaraju - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings Of The 2022 ACM Symposium On Principles Of Distributed Computing, PODC 2022, pp.366-368
- Publisher
- Assoc Computing Machinery
- DOI
- 10.1145/3519270.3538472
- Number of pages
- 3
- Language
- English
- Date published
- 01/01/2022
- Academic Unit
- Computer Science
- Record Identifier
- 9984455859602771
Metrics
5 Record Views