DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2020.28

Sample-And-Gather: Fast Ruling Set Algorithms in the Low-Memory MPC Model

Authors: Kishore Kothapalli, Shreyas Pai, and Sriram V. Pemmaraju

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract

Motivated by recent progress on symmetry breaking problems such as maximal independent set (MIS) and maximal matching in the low-memory Massively Parallel Computation (MPC) model (e.g., Behnezhad et al. PODC 2019; Ghaffari-Uitto SODA 2019), we investigate the complexity of ruling set problems in this model. The MPC model has become very popular as a model for large-scale distributed computing and it comes with the constraint that the memory-per-machine is strongly sublinear in the input size. For graph problems, extremely fast MPC algorithms have been designed assuming Ω̃(n) memory-per-machine, 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 low-memory MPC model, where the memory-per-machine 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 2-ruling set problem, running in Õ(log^{1/6} Δ) rounds whp, in the low-memory 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 low-memory MPC model with O(n^ε) memory-per-machine in Õ(β ⋅ 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 Õ(m + n^{1+ε}). We also present algorithms for β-ruling sets in the low-memory MPC model assuming that the total memory over all machines is restricted to Õ(m). For β > 1, these algorithms are all substantially faster than the Ghaffari-Uitto Õ(√{log Δ})-round MIS algorithm in the low-memory MPC model. All our results follow from a Sample-and-Gather Simulation Theorem that shows how random-sampling-based Congest algorithms can be efficiently simulated in the low-memory MPC model. We expect this simulation theorem to be of independent interest beyond the ruling set algorithms derived here.

Cite as

Kishore Kothapalli, Shreyas Pai, and Sriram V. Pemmaraju. Sample-And-Gather: Fast Ruling Set Algorithms in the Low-Memory MPC Model. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kothapalli_et_al:LIPIcs.FSTTCS.2020.28,
  author =	{Kothapalli, Kishore and Pai, Shreyas and Pemmaraju, Sriram V.},
  title =	{{Sample-And-Gather: Fast Ruling Set Algorithms in the Low-Memory MPC Model}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{28:1--28:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.28},
  URN =		{urn:nbn:de:0030-drops-132690},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.28},
  annote =	{Keywords: Massively Parallel Computation, Ruling Set, Simulation Theorems}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2012.136

Super-Fast 3-Ruling Sets

Authors: Kishore Kothapalli and Sriram Pemmaraju

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract

A t-ruling set of a graph G = (V, E) is a vertex-subset S that is independent and satisfies the property that every vertex v in V is at a distance of at most t from some vertex in S. A maximal independent set (MIS) is a 1-ruling set. The problem of computing an MIS on a network is a fundamental problem in distributed algorithms and the fastest algorithm for this problem is the O(log n)-round algorithm due to Luby (SICOMP 1986) and Alon et al. (J. Algorithms 1986) from more than 25 years ago. Since then the problem has resisted all efforts to yield to a sub-logarithmic round algorithm. There has been recent progress on this problem, most importantly an O(log Delta . sqrt(log n))-round algorithm on graphs with n vertices and maximum degree Delta, due to Barenboim et al. (to appear FOCS 2012). The time complexity of this algorithm is sub-logarithmic for Delta =2^{o(sqrt{log n})}. We approach the MIS problem from a different angle and ask if O(1)-ruling sets can be computed faster than the currently known fastest algorithm for an MIS? As an answer to this question, we show how to compute a 2-ruling set of an n-vertex graph in O((log n)^{3/4}) rounds. We also show that the above result can be improved for special classes of graphs. For instance, on high girth graphs (girth 6 or more), trees, and graphs of bounded arboricity, we show how to compute 3-ruling sets in exp(O({sqrt{loglog n}})) rounds, O((log log n)^2 .logloglog n) rounds, and O((loglog n)^3) rounds, respectively. Our main technique involves randomized sparsification that rapidly reduces the graph degree while ensuring that every deleted vertex is close to some vertex that remains. This technique may have further applications in other contexts, e.g., in designing sub-logarithmic distributed approximation algorithms. Our results raise intriguing questions about how quickly an MIS (or 1-ruling sets) can be computed, given that 2-ruling sets can be computed in sub-logarithmic rounds.

Cite as

Kishore Kothapalli and Sriram Pemmaraju. Super-Fast 3-Ruling Sets. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 136-147, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{kothapalli_et_al:LIPIcs.FSTTCS.2012.136,
  author =	{Kothapalli, Kishore and Pemmaraju, Sriram},
  title =	{{Super-Fast 3-Ruling Sets}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{136--147},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.136},
  URN =		{urn:nbn:de:0030-drops-38549},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.136},
  annote =	{Keywords: MIS, ruling sets, graph sparsification, distributed algorithms}
}

Search Results

Documents authored by Kothapalli, Kishore

Sample-And-Gather: Fast Ruling Set Algorithms in the Low-Memory MPC Model

Abstract

Cite as

Super-Fast 3-Ruling Sets

Abstract

Cite as

Thanks for your feedback!

Could not send message