Brief announcement: Symmetry breaking in the \textsc{Congest} model: time- and message-efficient algorithms for ruling sets

DOI10.1145/3087801.3087865zbMATH Open1380.68433arXiv1705.07861OpenAlexW2737971506MaRDI QIDQ5368965FDOQ5368965

Authors: Shreyas Pai, Gopal Pandurangan, Talal Riaz, Peter Robinson, Sriram Pemmaraju 

Publication date: 11 October 2017

Published in: Proceedings of the ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Abstract: We study local symmetry breaking problems in the CONGEST model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. A $$-ruling set is an independent set such that every node in the graph is at most $$ hops from a node in the independent set. Our work is motivated by the following central question: can we break the $Theta(logn)$ time complexity barrier and the $Theta(m)$ message complexity barrier in the CONGEST model for MIS or closely-related symmetry breaking problems? We present the following results: - Time Complexity: We show that we can break the $O(logn)$ "barrier" for 2- and 3-ruling sets. We compute 3-ruling sets in $Oleft(fraclognloglognight)$ rounds with high probability (whp). More generally we show that 2-ruling sets can be computed in $Oleft(logDeltacdot(logn{)}^{1/2+varepsilon}+fraclognloglognight)$ rounds for any $varepsilon>0$, which is $o(logn)$ for a wide range of $Delta$ values (e.g., $Delta=2^{(logn{)}^{1/2-varepsilon}}$). These are the first 2- and 3-ruling set algorithms to improve over the $O(logn)$-round complexity of Luby's algorithm in the CONGEST model. - Message Complexity: We show an $Omega(n^2)$ lower bound on the message complexity of computing an MIS (i.e., 1-ruling set) which holds also for randomized algorithms and present a contrast to this by showing a randomized algorithm for 2-ruling sets that, whp, uses only $O(nlo{g}^{2}n)$ messages and runs in $O(Deltalogn)$ rounds. This is the first message-efficient algorithm known for ruling sets, which has message complexity nearly linear in $n$ (which is optimal up to a polylogarithmic factor).

Full work available at URL: https://arxiv.org/abs/1705.07861

Recommendations

• Symmetry breaking in the Congest model: time- and message-efficient algorithms for ruling sets
• The locality of distributed symmetry breaking
• The complexity of symmetry breaking in massive graphs
• Distributed Maximal Independent Set using Small Messages
• Super-fast 3-ruling sets

zbMATH Keywords

maximal independent setsymmetry breakinground complexitylocal modelmessage complexityruling setsCongest model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15) Distributed systems (68M14)

Cited In (7)

• The complexity of symmetry breaking in massive graphs
• Fooling views: a new lower bound technique for distributed computations under congestion
• Distributed symmetry-breaking algorithms for congested cliques
• Symmetry breaking in the Congest model: time- and message-efficient algorithms for ruling sets
• Distributed Lower Bounds for Ruling Sets
• The complexity of leader election in diameter-two networks
• Deterministic distributed ruling sets of line graphs

This page was built for publication: Brief announcement: Symmetry breaking in the \textsc{Congest} model: time- and message-efficient algorithms for ruling sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368965)