Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2023-10
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
37th International Symposium on Distributed Computing, DISC 2023, Leibniz International Proceedings in Informatics, LIPIcs ; Volume 281
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.Description
Funding Information: Academy of Finland, Grant 334238. Publisher Copyright: © Mélanie Cambus, Fabian Kuhn, Shreyas Pai, and Jara Uitto; licensed under Creative Commons License CC-BY 4.0.
Keywords
Congested Clique, Massively Parallel Computing, Parallel Algorithms, Ruling Sets, Semi-Streaming
Other note
Citation
Cambus, M, Kuhn, F, Pai, S & Uitto, J 2023, Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem . in R Oshman (ed.), 37th International Symposium on Distributed Computing, DISC 2023 ., 11, Leibniz International Proceedings in Informatics, LIPIcs, vol. 281, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, International Symposium on Distributed Computing, L'Aquila, Italy, 10/10/2023 . https://doi.org/10.4230/LIPIcs.DISC.2023.11