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
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 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
 Award ID(s):
 1717075
 NSFPAR ID:
 10058638
 Date Published:
 Journal Name:
 31st International Symposium on Distributed Computing (DISC)
 ISSN:
 18688969
 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

We study the problem of testing identity against a given distribution with a focus on the high confidence regime. More precisely, given samples from an unknown distribution p over n elements, an explicitly given distribution q, and parameters 0< epsilon, delta < 1, we wish to distinguish, with probability at least 1delta, whether the distributions are identical versus epsilonfar in total variation distance. Most prior work focused on the case that delta = Omega(1), for which the sample complexity of identity testing is known to be Theta(sqrt{n}/epsilon^2). Given such an algorithm, one can achieve arbitrarily small values of delta via blackbox amplification, which multiplies the required number of samples by Theta(log(1/delta)). We show that blackbox amplification is suboptimal for any delta = o(1), and give a new identity tester that achieves the optimal sample complexity. Our new upper and lower bounds show that the optimal sample complexity of identity testing is Theta((1/epsilon^2) (sqrt{n log(1/delta)} + log(1/delta))) for any n, epsilon, and delta. For the special case of uniformity testing, where the given distribution is the uniform distribution U_n over the domain, our new tester is surprisingly simple: to test whether p = U_n versus d_{TV} (p, U_n) >= epsilon, we simply threshold d_{TV}({p^}, U_n), where {p^} is the empirical probability distribution. The fact that this simple "plugin" estimator is sampleoptimal is surprising, even in the constant delta case. Indeed, it was believed that such a tester would not attain sublinear sample complexity even for constant values of epsilon and delta. An important contribution of this work lies in the analysis techniques that we introduce in this context. First, we exploit an underlying strong convexity property to bound from below the expectation gap in the completeness and soundness cases. Second, we give a new, fast method for obtaining provably correct empirical estimates of the true worstcase failure probability for a broad class of uniformity testing statistics over all possible input distributions  including all previously studied statistics for this problem. We believe that our novel analysis techniques will be useful for other distribution testing problems as well.more » « less