Fast Deterministic Massively Parallel Ruling Sets Algorithms

Hongyan Ji; Kishore Kothapalli; Sriram V Pemmaraju; Ajitanshu Singh

doi:10.1145/3700838.3700872

Back

Fast Deterministic Massively Parallel Ruling Sets Algorithms

Conference proceeding

Open access

Fast Deterministic Massively Parallel Ruling Sets Algorithms

Hongyan Ji, Kishore Kothapalli, Sriram V Pemmaraju and Ajitanshu Singh

Proceedings of the 26th International Conference on Distributed Computing and Networking, pp.152-160

ACM Other Conferences

ICDCN 2025: 26th International Conference on Distributed Computing and Networking

01/04/2025

DOI: 10.1145/3700838.3700872

Appears in UI Libraries Support Open Access

Files and links (1)

url

https://doi.org/10.1145/3700838.3700872View

Published (Version of record) Open Access

Abstract

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 for this model, which is the \(\tilde{O}(\sqrt {\log n}) \)-round algorithm by Giliberti and Parsaeian (PODC 2024). Our result is obtained by derandomizing the “sample-and-gather” approach of Kothapalli, Pai, and Pemmaraju (FSTTCS 2020). The “sample-and-gather” approach involves making random sampling decisions, not just for the current iteration, but a batch of future iterations. Thus, derandomizing this approach requires the “fixing” of randomness for a batch of future iterations. We further extend our results to show that a β -ruling set for β ≥ 2 can be obtained in \(\tilde{O}(\log ^{1/2^{\beta }-1} \Delta) \) deterministic rounds in the sublinear MPC model. Additionally, we present a deterministic β -ruling set algorithms for sparse graphs (i.e., bounded arboricity graphs) where β ≥ 2, which runs in \(\tilde{O}(\log ^{1/2^\beta - 1} \lambda) \) rounds for arboricity-λ graphs in the sublinear MPC model.

Theory of computation -- Distributed algorithms

Theory of computation -- Massively parallel algorithms

Theory of computation -- Models of computation

UIOWA OA Agreement

Details

Title: Subtitle: Fast Deterministic Massively Parallel Ruling Sets Algorithms
Creators: Hongyan Ji - University of Iowa
Kishore Kothapalli - International Institute of Information Technology, Hyderabad
Sriram V Pemmaraju - University of Iowa
Ajitanshu Singh - International Institute of Information Technology, Hyderabad
Contributors: Amos Korman (Editor)
Sandip Chakraborty (Editor)
Sathya Peri (Editor)
Chiara Boldrini (Editor)
Peter Robinson (Editor)
Resource Type: Conference proceeding
Publication Details: Proceedings of the 26th International Conference on Distributed Computing and Networking, pp.152-160
Conference: ICDCN 2025: 26th International Conference on Distributed Computing and Networking
Series: ACM Other Conferences
DOI: 10.1145/3700838.3700872
Publisher: Association for Computing Machinery
Grant note: NSF: 1955939 Ministry of Education, Govt. of India, under the National Mission on Education through Information and Communication Technology: F.16-13/2017-TEL/2022/29
Hongyan Ji and Sriram V. Pemmaraju were partially supported during this project by NSF grant 1955939. The work of Ajitanshu Singh and Kishore Kothapalli is partially supported by a grant from the Ministry of Education, Govt. of India, under the National Mission on Education through Information and Communication Technology, Project titled Virtual Labs (Ph III) vide Ref. No: F.16-13/2017-TEL/2022/29.
Language: English
Date published: 01/04/2025
Academic Unit: Computer Science
Record Identifier: 9984769723502771

Metrics

15 Record Views