  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 $\beta$-ruling set is an independent set such that every node
in the graph is at most $\beta$ hops from a node in the independent set. Our
work is motivated by the following central question: can we break the
$\Theta(\log n)$ 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(\log n)$ "barrier" for 2-
and 3-ruling sets. We compute 3-ruling sets in $O\left(\frac{\log n}{\log \log
n}\right)$ rounds with high probability (whp). More generally we show that
2-ruling sets can be computed in $O\left(\log \Delta \cdot (\log n)^{1/2 +
\varepsilon} + \frac{\log n}{\log\log n}\right)$ rounds for any $\varepsilon >
0$, which is $o(\log n)$ for a wide range of $\Delta$ values (e.g., $\Delta =
2^{(\log n)^{1/2-\varepsilon}}$). 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 $\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(n \log^2 n)$ messages and
runs in $O(\Delta \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).
