Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem

Mélanie Cambus; Fabian Kuhn; Shreyas Pai; Jara Uitto

doi:10.4230/LIPIcs.DISC.2023.11

Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem

Mélanie Cambus^*, Fabian Kuhn^*, Shreyas Pai^*, Jara Uitto^*

^*Corresponding author for this work

University of Freiburg

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

4 Citations (Scopus)

37 Downloads (Pure)

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.

Original language	English
Title of host publication	37th International Symposium on Distributed Computing, DISC 2023
Editors	Rotem Oshman
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)	978-3-95977-301-0
DOIs	https://doi.org/10.4230/LIPIcs.DISC.2023.11
Publication status	Published - Oct 2023
MoE publication type	A4 Conference publication
Event	International Symposium on Distributed Computing - L'Aquila, Italy Duration: 10 Oct 2023 → 12 Oct 2023 Conference number: 37

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	281
ISSN (Print)	1868-8969

Conference

Conference	International Symposium on Distributed Computing
Abbreviated title	DISC
Country/Territory	Italy
City	L'Aquila
Period	10/10/2023 → 12/10/2023

Keywords

Congested Clique
Massively Parallel Computing
Parallel Algorithms
Ruling Sets
Semi-Streaming

Access to Document

10.4230/LIPIcs.DISC.2023.11Licence: CC BY

SCI_Cambus_etal_DISC_2023Final published version, 385 KBLicence: CC BY

Cite this

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 Article 11 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 281). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2023.11

@inproceedings{ef0c50450759459e8f44773833deef83,

title = "Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem",

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.",

keywords = "Congested Clique, Massively Parallel Computing, Parallel Algorithms, Ruling Sets, Semi-Streaming",

author = "M{\'e}lanie Cambus and Fabian Kuhn and Shreyas Pai and Jara Uitto",

note = "Funding Information: Academy of Finland, Grant 334238. Publisher Copyright: {\textcopyright} M{\'e}lanie Cambus, Fabian Kuhn, Shreyas Pai, and Jara Uitto; licensed under Creative Commons License CC-BY 4.0.; International Symposium on Distributed Computing, DISC ; Conference date: 10-10-2023 Through 12-10-2023",

year = "2023",

month = oct,

doi = "10.4230/LIPIcs.DISC.2023.11",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Rotem Oshman",

booktitle = "37th International Symposium on Distributed Computing, DISC 2023",

address = "Germany",

}

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

Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem. / Cambus, Mélanie; Kuhn, Fabian; Pai, Shreyas et al.
37th International Symposium on Distributed Computing, DISC 2023. ed. / Rotem Oshman. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. 11 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 281).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem

AU - Cambus, Mélanie

AU - Kuhn, Fabian

AU - Pai, Shreyas

AU - Uitto, Jara

N1 - Conference code: 37

PY - 2023/10

Y1 - 2023/10

N2 - 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.

AB - 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.

KW - Congested Clique

KW - Massively Parallel Computing

KW - Parallel Algorithms

KW - Ruling Sets

KW - Semi-Streaming

UR - http://www.scopus.com/inward/record.url?scp=85175317530&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.DISC.2023.11

DO - 10.4230/LIPIcs.DISC.2023.11

M3 - Conference article in proceedings

AN - SCOPUS:85175317530

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 37th International Symposium on Distributed Computing, DISC 2023

A2 - Oshman, Rotem

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - International Symposium on Distributed Computing

Y2 - 10 October 2023 through 12 October 2023

ER -

Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Massively Parallel Algorithms for Large-Scale Graph Problems

Cite this

Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Projects

Massively Parallel Algorithms for Large-Scale Graph Problems

Cite this