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 longstanding 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 medge 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 closelyrelated symmetry breaking problems? This paper presents progress towards this question for the distributed ruling set problem in the Congest model. A betaruling 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 3ruling sets. We compute 3ruling sets in O(log n/log log n) rounds with high probability (whp). More generally we show that 2ruling 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/2epsilon)). These are the first 2 and 3ruling 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., 1ruling set) which holds also for randomized algorithms and present a contrast to this by showing a randomized algorithm for 2ruling sets that, whp, uses only O(n log^2 n) messages and runs in O(Delta log n) rounds. This is the first messageefficient algorithm known for ruling sets, which has message complexity nearly linear in n (which is optimal up to a polylogarithmic factor).
more »
« less
Symmetry Breaking in the CONGEST Model: Time and MessageEfficient Algorithms for Ruling Sets
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 longstanding 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 medge 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 3ruling sets.
We compute 3ruling sets in O
log n
log log n
rounds with high probability (whp). More generally
we show that 2ruling 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 3ruling 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., 1ruling set) which holds also for randomized algorithms and present a contrast
to this by showing a randomized algorithm for 2ruling sets that, whp, uses only O(n log2 n)
messages and runs in O( log n) rounds. This is the first messageefficient algorithm known
for ruling sets, which has message complexity nearly linear in n (which is optimal up to a
polylogarithmic factor).
more »
« less
 Award ID(s):
 1633720
 NSFPAR ID:
 10039442
 Date Published:
 Journal Name:
 31st International Symposium on Distributed Computing (DISC), 2017
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


null (Ed.)We study the communication cost (or message complexity) of fundamental distributed symmetry breaking problems, namely, coloring and MIS. While significant progress has been made in understanding and improving the running time of such problems, much less is known about the message complexity of these problems. In fact, all known algorithms need at least Ω(m) communication for these problems, where m is the number of edges in the graph. We addressthe following question in this paper: can we solve problems such as coloring and MIS using sublinear, i.e., o(m) communication, and if sounder what conditions? In a classical result, Awerbuch, Goldreich, Peleg, and Vainish [JACM 1990] showed that fundamental global problems such asbroadcast and spanning tree construction require at least o(m) messages in the KT1 Congest model (i.e., Congest model in which nodes have initial knowledge of the neighbors' ID's) when algorithms are restricted to be comparisonbased (i.e., algorithms inwhich node ID's can only be compared). Thirty five years after this result, King, Kutten, and Thorup [PODC 2015] showed that onecan solve the above problems using Õ(n) messages (n is the number of nodes in the graph) in Õ(n) rounds in the KT1 Congest model if noncomparisonbased algorithms are permitted. An important implication of this result is that one can use the synchronous nature of the KT1 Congest model, using silence to convey information,and solve any graph problem using noncomparisonbased algorithms with Õ(n) messages, but this takes an exponential number of rounds. In the asynchronous model, even this is not possible. In contrast, much less is known about the message complexity of local symmetry breaking problems such as coloring and MIS. Our paper fills this gap by presenting the following results. Lower bounds: In the KT1 CONGEST model, we show that any comparisonbased algorithm, even a randomized Monte Carlo algorithm with constant success probability, requires Ω(n 2) messages in the worst case to solve either (△ + 1)coloring or MIS, regardless of the number of rounds. We also show that Ω(n) is a lower bound on the number ofmessages for any (△ + 1)coloring or MIS algorithm, even noncomparisonbased, and even with nodes having initial knowledge of up to a constant radius. Upper bounds: In the KT1 CONGEST model, we present the following randomized noncomparisonbased algorithms for coloring that, with high probability, use o(m) messages and run in polynomially many rounds.(a) A (△ + 1)coloring algorithm that uses Õ(n1.5) messages, while running in Õ(D + √ n) rounds, where D is the graph diameter. Our result also implies an asynchronous algorithm for (△ + 1)coloring with the same message bound but running in Õ(n) rounds. (b) For any constantε > 0, a (1+ε)△coloring algorithm that uses Õ(n/ε 2 ) messages, while running in Õ(n) rounds. If we increase our input knowledge slightly to radius 2, i.e.,in the KT2 CONGEST model, we obtain:(c) A randomized comparisonbased MIS algorithm that uses Õ(n 1.5) messages. while running in Õ( √n) rounds. While our lower bound results can be viewed as counterparts to the classical result of Awerbuch, Goldreich, Peleg, and Vainish [JACM 90], but for local problems, our algorithms are the firstknown algorithms for coloring and MIS that take o(m) messages and run in polynomially many rounds.more » « less

null (Ed.)Maximal Independent Set (MIS) is one of the fundamental problems in distributed computing. The round (time) complexity of distributed MIS has traditionally focused on the worstcase time for all nodes to finish. The bestknown (randomized) MIS algorithms take O(log n) worstcase rounds on general graphs (where n is the number of nodes). Breaking the O(log n) worstcase bound has been a longstanding open problem, while currently the bestknown lower bound is [EQUATION] rounds. Motivated by the goal to reduce total energy consumption in energyconstrained networks such as sensor and ad hoc wireless networks, we take an alternative approach to measuring performance. We focus on minimizing the total (or equivalently, the average) time for all nodes to finish. It is not clear whether the currently bestknown algorithms yield constantround (or even o(log n)) nodeaveraged round complexity for MIS in general graphs. We posit the sleeping model, a generalization of the traditional model, that allows nodes to enter either "sleep" or "waking" states at any round. While waking state corresponds to the default state in the traditional model, in sleeping state a node is "offline", i.e., it does not send or receive messages (and messages sent to it are dropped as well) and does not incur any time, communication, or local computation cost. Hence, in this model, only rounds in which a node is awake are counted and we are interested in minimizing the average as well as the worstcase number of rounds a node spends in the awake state, besides the traditional worstcase round complexity (i.e., the rounds for all nodes to finish including both the awake and sleeping rounds). Our main result is that we show that MIS can be solved in (expected) O(1) rounds under nodeaveraged awake complexity measure in the sleeping model. In particular, we present a randomized distributed algorithm for MIS that has expected O(1)rounds nodeaveraged awake complexity and, with high probability1 has O(log n)rounds worstcase awake complexity and O(log3.41 n)rounds worstcase complexity. Our work is a step towards understanding the nodeaveraged complexity of MIS both in the traditional and sleeping models, as well as designing energyefficient distributed algorithms for energyconstrained networks.more » « less

This paper focuses on showing timemessage tradeoffs in distributed algorithms for fundamental problems such as leader election, broadcast, spanning tree (ST), minimum spanning tree (MST), minimum cut, and many graph verification problems. We consider the synchronous CONGEST distributed computing model and assume that each node has initial knowledge of itself and the identifiers of its neighbors  the socalled KT_1 model  a wellstudied model that also naturally arises in many applications. Recently, it has been established that one can obtain (almost) singularly optimal algorithms, i.e., algorithms that have simultaneously optimal time and message complexity (up to polylogarithmic factors), for many fundamental problems in the standard KT_0 model (where nodes have only local knowledge of themselves and not their neighbors). The situation is less clear in the KT_1 model. In this paper, we present several new distributed algorithms in the KT_1 model that trade off between time and message complexity. Our distributed algorithms are based on a uniform and general approach which involves constructing a sparsified spanning subgraph of the original graph  called a danner  that trades off the number of edges with the diameter of the sparsifier. In particular, a key ingredient of our approach is a distributed randomized algorithm that, given a graph G and any delta in [0,1], with high probability constructs a danner that has diameter O~(D + n^{1delta}) and O~(min{m,n^{1+delta}}) edges in O~(n^{1delta}) rounds while using O~(min{m,n^{1+delta}}) messages, where n, m, and D are the number of nodes, edges, and the diameter of G, respectively. Using our danner construction, we present a family of distributed randomized algorithms for various fundamental problems that exhibit a tradeoff between message and time complexity and that improve over previous results. Specifically, we show the following results (all hold with high probability) in the KT_1 model, which subsume and improve over prior bounds in the KT_1 model (King et al., PODC 2014 and Awerbuch et al., JACM 1990) and the KT_0 model (Kutten et al., JACM 2015, Pandurangan et al., STOC 2017 and Elkin, PODC 2017): 1) Leader Election, Broadcast, and ST. These problems can be solved in O~(D+n^{1delta}) rounds using O~(min{m,n^{1+delta}}) messages for any delta in [0,1]. 2) MST and Connectivity. These problems can be solved in O~(D+n^{1delta}) rounds using O~(min{m,n^{1+delta}}) messages for any delta in [0,0.5]. In particular, for delta = 0.5 we obtain a distributed MST algorithm that runs in optimal O~(D+sqrt{n}) rounds and uses O~(min{m,n^{3/2}}) messages. We note that this improves over the singularly optimal algorithm in the KT_0 model that uses O~(D+sqrt{n}) rounds and O~(m) messages. 3) Minimum Cut. O(log n)approximate minimum cut can be solved in O~(D+n^{1delta}) rounds using O~(min{m,n^{1+delta}}) messages for any delta in [0,0.5]. 4) Graph Verification Problems such as Bipartiteness, Spanning Subgraph etc. These can be solved in O~(D+n^{1delta}) rounds using O~(min{m,n^{1+delta}}) messages for any delta in [0,0.5].more » « less

The best known solutions for kmessage broadcast in dynamic networks of size n require Ω(nk) rounds. In this paper, we see if these bounds can be improved by smoothed analysis. To do so, we study perhaps the most natural randomized algorithm for disseminating tokens in this setting: at every time step, choose a token to broadcast randomly from the set of tokens you know. We show that with even a small amount of smoothing (i.e., one random edge added per round), this natural strategy solves kmessage broadcast in Õ(n+k³) rounds, with high probability, beating the best known bounds for k = o(√n) and matching the Ω(n+k) lower bound for static networks for k = O(n^{1/3}) (ignoring logarithmic factors). In fact, the main result we show is even stronger and more general: given 𝓁smoothing (i.e., 𝓁 random edges added per round), this simple strategy terminates in O(kn^{2/3}log^{1/3}(n)𝓁^{1/3}) rounds. We then prove this analysis close to tight with an almostmatching lower bound. To better understand the impact of smoothing on information spreading, we next turn our attention to static networks, proving a tight bound of Õ(k√n) rounds to solve kmessage broadcast, which is better than what our strategy can achieve in the dynamic setting. This confirms the intuition that although smoothed analysis reduces the difficulties induced by changing graph structures, it does not eliminate them altogether. Finally, we apply tools developed to support our smoothed analysis to prove an optimal result for kmessage broadcast in socalled wellmixed networks in the absence of smoothing. By comparing this result to an existing lower bound for wellmixed networks, we establish a formal separation between oblivious and strongly adaptive adversaries with respect to wellmixed token spreading, partially resolving an open question on the impact of adversary strength on the kmessage broadcast problem.more » « less