%APai, S%APandurangan, G%APemmaraju, S.%ARiaz, T%ARobinson, P.%D2017%I
%K
%MOSTI ID: 10039442
%PMedium: X
%TSymmetry Breaking in the CONGEST Model: Time- and Message-Efficient Algorithms for Ruling Sets
%XWe study local symmetry breaking problems in the Congest model, focusing on ruling set
problems, which generalize the fundamental Maximal Independent Set (MIS) problem. The time
(round) complexity of MIS (and ruling sets) have attracted much attention in the Local model.
Indeed, recent results (Barenboim et al., FOCS 2012, Ghaffari SODA 2016) for the MIS problem
have tried to break the long-standing O(log n)-round “barrier” achieved by Luby’s algorithm,
but these yield o(log n)-round complexity only when the maximum degree is somewhat small
relative to n. More importantly, these results apply only in the Local model. In fact, the
best known time bound in the Congest model is still O(log n) (via Luby’s algorithm) even for
moderately small (i.e., for =
(log n) and = o(n)). Furthermore, message complexity has
been largely ignored in the context of local symmetry breaking. Luby’s algorithm takes O(m)
messages on m-edge graphs and this is the best known bound with respect to messages. Our
work is motivated by the following central question: can we break the (log n) time complexity
barrier and the (m) message complexity barrier in the Congest model for MIS or closelyrelated
symmetry breaking problems?
This paper presents progress towards this question for the distributed ruling set problem in
the Congest model. 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. We present the following results:
Time Complexity: We show that we can break the O(log n) “barrier” for 2- and 3-ruling sets.
We compute 3-ruling sets in O
log n
log log n
rounds with high probability (whp). More generally
we show that 2-ruling sets can be computed in O
log · (log n)1/2+" + log n
log log n
rounds for
any " > 0, which is o(log n) for a wide range of values (e.g., = 2(log n)1/2−" ). These
are the first 2- and 3-ruling set algorithms to improve over the O(log n)-round complexity of
Luby’s algorithm in the Congest model.
Message Complexity: We show an
(n2) 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(n log2 n)
messages and runs in O( log n) 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).
Country unknown/Code not availableOSTI-MSA