Brief Announcement: Deterministic Massively Parallel Algorithms for Ruling Sets

DOI10.1145/3519270.3538472MaRDI QIDQ6202182zbMATH OpenOpenAlexFDO

Authors Shreyas Pai, Sriram Pemmaraju

Publication date 26 March 2024

Published in Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2205.12686

zbMATH Keywords

congested cliquederandomizationdeterministic algorithmmassively parallel computingruling sets

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Abstract: In this paper we present a deterministic $O(loglogn)$-round algorithm for the 2-ruling set problem in the Massively Parallel Computation model with $ildeO(n)$ memory; this algorithm also runs in $O(loglogn)$ 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(logDelta)$-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).

Cited in

(1)

• Brief announcement: Massively parallel ruling set made deterministic

This page was built for publication: Brief Announcement: Deterministic Massively Parallel Algorithms for Ruling Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202182)