The goal of this paper is to understand the complexity of symmetry breaking problems, specifically maximal independent set (MIS) and the closely related $β$-ruling set problem, in two computational models suited for large-scale graph processing, namely the $k$-machine model and the graph streaming model. We present a number of results. For MIS in the $k$-machine model, we improve the $\tilde{O}(m/k^2 + Δ/k)$-round upper bound of Klauck et al. (SODA 2015) by presenting an $\tilde{O}(m/k^2)$-round algorithm. We also present an $\tildeΩ(n/k^2)$ round lower bound for MIS, the first lower bound for a symmetry breaking problem in the $k$-machine model. For $β$-ruling sets, we use hierarchical sampling to obtain more efficient algorithms in the $k$-machine model and also in the graph streaming model. More specifically, we obtain a $k$-machine algorithm that runs in $\tilde{O}(βnΔ^{1/β}/k^2)$ rounds and, by using a similar hierarchical sampling technique, we obtain one-pass algorithms for both insertion-only and insertion-deletion streams that use $O(β\cdot n^{1+1/2^{β-1}})$ space. The latter result establishes a clear separation between MIS, which is known to require $Ω(n^2)$ space (Cormode et al., ICALP 2019), and $β$-ruling sets, even for $β= 2$. Finally, we present an even faster 2-ruling set algorithm in the $k$-machine model, one that runs in $\tilde{O}(n/k^{2-ε} + k^{1-ε})$ rounds for any $ε$, $0 \le ε\le 1$.

We study local symmetry breaking problems in the Congest model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. Our work is motivated by the following central question: can we break the long-standing Θ(log n) time-complexity barrier and the Θ(m) message-complexity barrier in the Congest model for MIS or closely-related symmetry breaking problems?

We 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 Delta 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 Delta (i.e., for Delta = Omega(log n) and Delta = 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 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? This paper presents progress towards this question for the distributed ruling set problem in the Congest model. 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. 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 Delta (log n)^(1/2 + epsilon) + log n/log log n) rounds for any epsilon > 0, which is o(log n) for a wide range of Delta values (e.g., Delta = 2^(log n)^(1/2-epsilon)). 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).

Until recently, the fastest distributed MIS algorithm, even for simple graph classes such as unoriented trees that can contain large independent sets within neighborhoods, has been the simple randomized algorithm discovered independently by several researchers in the late 80s. This algorithm (commonly called Luby’s algorithm) computes an MIS of an n-node graph in O(log n) communication rounds (with high probability). This situation changed when Lenzen and Wattenhofer (PODC 2011) presented a distributed (randomized) MIS algorithm for unoriented treesrunning in O( sqrt (log n * log log n)) rounds. This algorithm was slightly improved by Barenboim et al. (FOCS 2012), resulting in an O( sqrt (log n * log log n))-round (randomized) MIS algorithm for trees. At their core, these algorithms still run Luby's algorithm, but only up to the point at which the graph has been "shattered" into small connected components that can be independently processed in parallel. The analyses of these tree MIS algorithms critically depends on "near independence" among probabilistic events, a feature that arises from the tree structure of the network. In their paper, Lenzen and Wattenhofer express hope that their algorithm and analysis could be extended to graphs with bounded arboricity. We show how to do this in the current paper. By using a new tail inequality for read-k families of random variables due to Gavinsky et al. (Random Struct Algorithms, 2015), we show how to deal with dependencies induced by the recent tree MIS algorithms when they are executed on bounded arboricity graphs. Specifically, we analyze a version of the tree MIS algorithm of Barenboim et al. and show that it runs in O(poly(a) * sqrt ( log n * log log n)) rounds in the CONGEST model for graphs with arboricity a. While the main thrust of this paper is the new probabilistic analysis via read-k inequalities, we point out that for small values of a, this algorithm is faster than the MIS algorithm of Barenboim et al. specifically designed for bounded arboricity graphs. In this context, it should be noted that recently (in SODA 2016) Ghaffari presented a novel distributed MIS algorithm for general graphs that runs in O (log d) + 2^O(sqrt(log log n)) rounds and a corollary of this algorithm is an O(log d + sqrt (log n))-round MIS algorithm on graphs with arboricity a.

Until recently, the fastest distributed MIS algorithm, even for simple graphs, e.g., unoriented trees, has been the simple randomized algorithm discovered in the 80s. This algorithm (commonly called Luby's algorithm) computes an MIS in O(log n) rounds (with high probability). This situation changed when Lenzen and Wattenhofer (PODC 2011) presented a randomized O(√log n} ⋅ log\log n)-round MIS algorithm for unoriented trees. This algorithm was improved by Barenboim et al. (FOCS 2012), resulting in an MIS algorithm running in O(√log n ⋅ log\log n) rounds.