Projects per year
Abstract
In this work, we present a constantround algorithm for the 2ruling set problem in the Congested Clique model. As a direct consequence, we obtain a constant round algorithm in the MPC model with linear spacepermachine 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 semistreaming 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 2ruling 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 2ruling 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  LeibnizZentrum für Informatik 
ISBN (Electronic)  9783959773010 
DOIs  
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)  18688969 
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
 SemiStreaming
Fingerprint
Dive into the research topics of 'Time and Space Optimal Massively Parallel Algorithm for the 2Ruling Set Problem'. Together they form a unique fingerprint.Projects
 1 Active

: Massively Parallel Algorithms for LargeScale Graph Problems
Uitto, J., Cambus, M., Latypov, R. & Pai, S.
01/09/2020 → 31/08/2024
Project: Academy of Finland: Other research funding