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

DOI10.1145/3087801.3087865MaRDI QIDQ5368965zbMATH OpenOpenAlexFDO

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)

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

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)

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

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

Cited in

(7)

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

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)