Abstract
Motivated by recent progress on symmetry breaking problems such as maximal independent set (MIS) and maximal matching in the lowmemory Massively Parallel Computation (MPC) model (e.g., Behnezhad et al. PODC 2019; GhaffariUitto SODA 2019), we investigate the complexity of ruling set problems in this model. The MPC model has become very popular as a model for largescale distributed computing and it comes with the constraint that the memorypermachine is strongly sublinear in the input size. For graph problems, extremely fast MPC algorithms have been designed assuming Ω̃(n) memorypermachine, where n is the number of nodes in the graph (e.g., the O(log log n) MIS algorithm of Ghaffari et al., PODC 2018). However, it has proven much more difficult to design fast MPC algorithms for graph problems in the lowmemory MPC model, where the memorypermachine is restricted to being strongly sublinear in the number of nodes, i.e., O(n^ε) for constant 0 < ε < 1.
In this paper, we present an algorithm for the 2ruling set problem, running in Õ(log^{1/6} Δ) rounds whp, in the lowmemory MPC model. Here Δ is the maximum degree of the graph. We then extend this result to βruling sets for any integer β > 1. Specifically, we show that a βruling set can be computed in the lowmemory MPC model with O(n^ε) memorypermachine in Õ(β ⋅ log^{1/(2^{β+1}2)} Δ) rounds, whp. From this it immediately follows that a βruling set for β = Ω(log log log Δ)ruling set can be computed in in just O(β log log n) rounds whp. The above results assume a total memory of Õ(m + n^{1+ε}). We also present algorithms for βruling sets in the lowmemory MPC model assuming that the total memory over all machines is restricted to Õ(m). For β > 1, these algorithms are all substantially faster than the GhaffariUitto Õ(√{log Δ})round MIS algorithm in the lowmemory MPC model.
All our results follow from a SampleandGather Simulation Theorem that shows how randomsamplingbased Congest algorithms can be efficiently simulated in the lowmemory MPC model. We expect this simulation theorem to be of independent interest beyond the ruling set algorithms derived here.
BibTeX  Entry
@InProceedings{kothapalli_et_al:LIPIcs:2020:13269,
author = {Kishore Kothapalli and Shreyas Pai and Sriram V. Pemmaraju},
title = {{SampleAndGather: Fast Ruling Set Algorithms in the LowMemory MPC Model}},
booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
pages = {28:128:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771740},
ISSN = {18688969},
year = {2020},
volume = {182},
editor = {Nitin Saxena and Sunil Simon},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13269},
URN = {urn:nbn:de:0030drops132690},
doi = {10.4230/LIPIcs.FSTTCS.2020.28},
annote = {Keywords: Massively Parallel Computation, Ruling Set, Simulation Theorems}
}
Keywords: 

Massively Parallel Computation, Ruling Set, Simulation Theorems 
Collection: 

40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) 
Issue Date: 

2020 
Date of publication: 

04.12.2020 