Distributed Maximal Independent Set using Small Messages

Mohsen Ghaffari∗
Downloaded 11/22/21 to 86.121.161.178 Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/page/terms

Abstract Linial [23], defined as follows: the communication net-

Maximal Independent Set (MIS) is one of the central prob- work is abstracted as an n-node graph G = (V, E). We
lems in distributed graph algorithms. The celebrated works use ∆ to denote the maximum degree of G. There is
of Luby [STOC’85] and Alon, Babai, and Itai [JALG’86] one processor on each node of the network, who initially
provide O(log n)-round randomized distributed MIS algo- knows only its own O(log n)-bit identifier. Communica-
rithms, which work with O(log n)-bit messages. √
This round tion happens in synchronous rounds where per round,
2 O( log log n)
complexity was improved to O(log ∆) + 2 in a each node can send one message to each of its neighbors.
breakthrough of Barenboim, Elkin, Pettie, and√ Schneider The LOCAL model does not restrict the message sizes,
[FOCS’11; JACM’16] and then to O(log ∆)+2O( log log n) by but the variant where each message has size at most B
Ghaffari [SODA’16], where ∆ denotes the maximum degree.
bits is known as the CONGEST model [29], and usually
However, these improvements have one drawback: they re-
we assume B = O(log n). Notice that this is enough
quire much larger messages, up to poly(∆ log n) bits. Indeed,
the question of improving the O(log n) round complexity us- space to describe one element of the network, e.g., a
ing small messages has remained open for three decades, for node or an edge. At the end of the computation, each
essentially all values of ∆, except for ∆ = o(log n) where processor/node should know its own part of the output,
there are O(∆ + log∗ n)-round deterministic algorithms. e.g., whether it is in the MIS or not.
We present a randomized distributed MIS algorithm, The MIS problem and its significance: In the
with O(log n)-bit messages,√ that achieves a round com- MIS problem, the objective is to compute a set S of
plexity
√
of min{log ∆ · 2O( log log n) , O(log ∆ · log log n) + nodes such that no two neighboring nodes are in S,
O( log log n·log log log n)
2 }. This is the first algorithm with and moreover, for each node v, either v or at least
small messages that improves on the O(log n) round com- one of its neighbors should be in S. MIS is one
plexity of Luby and Alon et al. for a wide range of ∆, and of the central problems in the study of distributed
its complexity almost matches that of the best known al- graph algorithms1 . This is in part because several
gorithm using unbounded message sizes. As applications of other fundamental graph problems can be reduced to
this MIS algorithm or along the way to it, we obtain im- MIS with a constant round complexity overhead. This
proved distributed algorithms with small messages for some includes maximal matching, (∆ + 1)-vertex coloring,
other well-studied problems including network decomposi- (2∆−1) edge coloring, 2-approximation of vertex cover,
tions, (∆ + 1)-vertex coloring, and ruling sets. and (1+ε)-approximation of maximum matching for any
constant ε > 0 [23, 24, 26]. See the book of Barenboim
1 Introduction and Related Work and Elkin [3] for more.
We provide the first distributed algorithm with small State of the Art for MIS: The celebrated works of
messages that computes a Maximal Independent Set Luby [25] and Alon, Babai, and Itai [1] provide ran-
(MIS) faster than the celebrated O(log n)-round algo- domized distributed MIS algorithms in the CONGEST
rithms of Luby [25] and Alon, Babai, and Itai [1], with model (i.e., with O(log n)-bit message) that have round
a complexity that comes close to the best known al- complexity O(log n). That is, they compute an MIS
gorithm with unbounded message sizes. To state the in O(log n) rounds, with high probability, i.e., probabil-
precise result, we first review the distributed models of ity at least 1 − 1/nc for an arbitrary constant c ≥ 2.
computation, the MIS problem and its significance, and Given the centrality of MIS, obtaining a fast and ide-
the related state of the art. Then, we present our results ally optimal-time algorithm for it has been a question
and its implications. of significant interest, and there has been some progress
on both lower and upper bounds.
1.1 Model, Problem, and State of the Art Dis-
tributed Models: A standard model in the study 1 The citation of the Dijkstra prize in 2016, awarded to [1, 25],
of distributed graph algorithm is the LOCAL model of calls MIS a crown jewel of distributed symmetry breaking prob-
lems and a central problem in the area of locality in distributed
∗ ETH Zurich, ghaffari@inf.ethz.ch computing.

Copyright © 2019 by SIAM

805 Unauthorized reproduction of this article is prohibited
 On the lower bound side, Linial [23] proved that u ∈ S within distance 2 of v (instead of distance 1 in
any distributed MIS algorithm needs Ω(log∗ n) rounds, MIS). This problem is considerably more relaxed than
even on an n-node cycle. Kuhn, Wattenhofer, and MIS2 : e.g., if unbounded √ size messages
√ are allowed, it
Moscibroda [21, 22] proved thatqany distributed MIS can be computed in O( log ∆) + 2O( log log n) rounds.
algorithm needs Ω(min{ logloglog∆∆ , logloglogn n }) rounds. The bound of Pai et al. [27] improves the complex-
ity of 2-ruling set from O(log n) to O( logloglogn n ), when
Progress on the upper bound side was scarse, until a
Downloaded 11/22/21 to 86.121.161.178 Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/page/terms

1/2−ε
breakthrough of Barenboim, Elkin, Pettie, and Schnei- log ∆ = (log n) .
der [5]. They √ gave an algorithm with round complexity
O(log ∆ · log n), which improves over the celebrated √
O(log n) round complexity whenever log ∆ = o( log n). 1.2 Our Results MIS: We present a CONGEST-
Shortly after, and as presented in their journal ver- model MIS algorithm that breaks the O(log n) barrier
sion√ [6], they improved this bound to O(log2 ∆) + for a wide range of degrees. Particularly, it has a round
complexity that comes close to that of the best known
2O( log log n) . The bound was √ then improved by Ghaf- algorithm with unbounded message sizes:
fari [14] to O(log ∆) + 2O( log log n) . The latter is a
nearly optimal complexity, in the following sense: (A) Theorem 1.1. There is a randomized distributed
The dependency on ∆ cannot be improved significantly, algorithm, with O(log n)-bit messages, that com-
as Ω( logloglog∆∆ ) is a lower bound [21, 22], (B) By a beau- putes an MIS in min{O(log ∆ · log log n) +
√ √
tiful result of Chang, √
Kopelowitz, and Pettie [10], we 2O( log log n·log log log n) , log ∆ · 2O( log log n) } rounds,
know that the 2O( log log n)√ term cannot be improved w.h.p.
unless we improve the 2O( log n) complexity of deter-
ministic MIS algorithms. The latter has resisted any Network Decomposition: On the way to this
improvement since 1992 [28] and improving it would be MIS algorithm, we present the first deterministic
considered a major breakthrough in distributed graph CONGEST-model algorithm for network decomposition
algorithms. In particular, improving it to poly(log n) that matches the bounds of the celebrated algorithm
would answer one of the most well-known open ques- of Panconesi and Srinivasan [28], which works with un-
tions of the area, first asked by Linial [23]. See [3] for bounded message sizes. See Theorem 1.2 for the formal
more on this question, and also [15, 16] which provide a statement. In fact, our algorithm is considerably sim-
complexity-theoretic study of it. pler than that of [28]. Therefore, and especially due to
However, all the algorithmic improvements men- the extensive applications of network decompositions,
tioned in the previous paragraph suffer from one known we hope that this contribution will be of interest on its
drawback: they all need large messages. Concretely, own.
while the algorithms of [1, 25] work in the CONGEST Another aspect of the improvement that is crucial
model — i.e., with O(log n)-bit messages — the algo- for our application and might prove useful elsewhere is
rithms of [5, 6, 14] require much larger messages, up to that our network decomposition can handle much larger
poly(∆ log n) bits. Indeed, in the CONGEST model, the identifiers (so long as the message size is large enough
O(log n) bound of [1, 25] remains the state of the art, to fit one identifier). This is formalized in Theorem 1.2.
for more than three decades, for essentially the whole Previous algorithms [2, 28] did not have this property,
range of maximum degrees. The only exception is when due to their reliance on a ruling set subroutine that
∆ = o(log n) in which case deterministic algorithms depends on the ID space size. Indeed, this was one
with complexity O(∆+log∗ n) suffice [4]. To summarize, of the key obstacles toward o(log n)-round CONGEST-
this state of the art exhibits one clear question: model randomized MIS algorithms. See the discussion
in Section 1.4.
Can we obtain an o(log n)-round randomized Before stating the theorem, let us recall the defini-
MIS algorithm, with O(log n)-bit messages, tion. An (α, β)-network decomposition of graph G =
when log ∆ = o(log n)? (V, E) is a partition of V into sets V1 , . . . , Vα such that
for each i, each connected component of the subgraph
G[Vi ] induced by Vi has diameter at most β. The sub-
As a side remark, we comment that even minor im- graph G[V ] is known as the ith color class or block of
i
provements over this O(log n) barrier have been of in-
terest: Pai et al. [27] gave a CONGEST-model algorithm 2 Our MIS algorithm leads to a much faster algorithm for 2-
with complexity O(log ∆ · (log n)1/2+ε + logloglogn n ) for 2- ruling set with small messages. Particularly, for the log ∆ =
ruling set. This problem asks for an independent set (log n)1/2−ε range discussed above, our complexity is at most
√
S which for every node v ∈ / S, has at least one node o( log n). See Theorem 1.4.

Copyright © 2019 by SIAM

806 Unauthorized reproduction of this article is prohibited
 the decomposition. Each connected component of G[Vi ] complexity O(log ∆ · (log n)1/2+ε + logloglogn n ) for 2-ruling
is known as one cluster of the decomposition, and it is set, an algorithm with complexity O( log n ) for 3-
log log n √
assigned color i.
ruling set, and an algorithm with complexity O( log n)
Theorem 1.2. There is a deterministic distributed al- for 5-ruling set.
gorithm that in any N -node network, which has S-bit Our MIS algorithm, combined with the recursive
identifiers and supports O(S)-bit messages for some ar- sparsification method of [8, 20], leads to the following
Downloaded 11/22/21 to 86.121.161.178 Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/page/terms

bitrary S, computes a (g(N ), g(N )) network decomposi- significant improvement for the CONGEST model:
√
tion in g(N ) · log∗ S rounds, for g(N ) = 2O( log N )
.
Theorem 1.4. There are randomized distributed algo-
rithms with O(log n)-bit messages that, w.h.p., compute
1.3 Implications on Other Problems Given that a β-ruling set, for any β ≥ 2, with the following asymp-
many other problems reduce to MIS, we obtain improve- totic round complexities:
ments also for other problems.
1/β
Vertex Coloring: Computing a (∆ + 1)-vertex color- • β log√ ∆ + log1/β ∆ log log n +
O( log log n·log log log n)
ing is one of the other central and well-studied prob- 2 .
√
lems in distributed graph algorithms; cf. [3]. As men- • β log1/β ∆ + log1/β ∆ · 2O( log log n) .
tioned above, this problem reduces to MIS and thus √
admits O(log n)-round CONGEST-model algorithms [1, • β log1/(β−1) ∆ + 2O( log log n) .
25]. Similar to MIS, there have improvements using
larger messages: Barenboim et al.√[5] gave an algorithm 1.4 Large Message in the Shattering Tech-
with complexity O(log ∆) + 2O( log log n) , which uses nique, and Our Method in a Nutshell We review
poly(log n)-bit messages. This round complexity was the shattering technique used in many of the recent de-
√ √
then improved to O( log ∆) + 2O( log log n) by Harris, velopments [5, 6, 11, 14, 18] and briefly mention why ba-
Schneider,
√
and Su [18] and then, very recently, to just sically all of these algorithms needed large messages.
2 O( log log n)
by Chang, Li, and Pettie [11]. Though, We then explain how we obtain our MIS algorithm with
there is no clear upper bound on message size in these small messages.
two algorithms and it seems that they can be up to The Shattering Method: The shattering technique is
polynomially large. We obtain the first improvement for inspired by Beck’s breakthrough [7], which provided the
(∆ + 1)-vertex coloring over the classic O(log n) round first algorithmic version of the Lovasz Local Lemma. It
complexity, in the CONGEST-model: was first used by Barenboim et al. [5] in the distributed
setting and it has played a significant role since then
Theorem 1.3. There is a randomized distributed algo-
in many other developments in distributed graph al-
rithm with O(log n)-bit messages that, w.h.p., computes
√ gorithms for local problems [6, 11, 14, 18]. In its dis-
a (∆ + 1) vertex coloring in O(log ∆) + 2O( log log n) tributed version, this method works in two phases: (A)
rounds. a so-called pre-shattering phase that is randomized and
solves the problem for “most” of the graph except for
Ruling Set: Another well-studied problem closely leaving some (potentially large) number of “small” com-
related to MIS is that of computing a β-ruling set. ponents, and (B) a so-called post-shattering phase that
This problem asks for an independent set S which solves the problem on these remaining components, us-
for every node v ∈ / S, has at least one node u ∈ S ing a deterministic algorithm that is run concurrently
within distance β of v. Since it is a relaxation of MIS, and independently in each of the remaining components.
this problem clearly admits O(log n)-round CONGEST- Almost all shattering-based algorithms [5, 6, 11, 14,
model algorithms [1, 25]. 18] for MIS and (∆ + 1)-vertex coloring3 suffer from the
There have improvements using large messages: need for large messages in the post-shattering phase,
Schneider and Wattenhofer [30] gave a random-
ized β-ruling set algorithm with complexity O(2β/2 ·
3 For maximal matching, [5] gave an O(log ∆ + log4 log n)-
log2/(β−1) n), which was improved
√
by Bisht et al. [8]
round algorithm. That algorithm works in the CONGEST model
to O(β log1/(β−1) ∆) + 2O( log log√n) , by Barenboim et because (1) the pre-shattering phase leaves components of size
al. [6] to O(β log1/(β−0.5)∆ ) + 2O( log√log n) , and then by N = poly(log n) and (B) for the post-shattering phase, the deter-
Ghaffari [14] to O(β log1/β ∆) + 2O( log log n) . ministic O(log4 N )-round maximal matching algorithm of Hanck-
owiak et al. [17] for N -node networks can tolerate large identifiers,
For the CONGEST-model variant of the problem, e.g, poly(N )-bit identifiers. The randomized complexity was im-
the only o(log n)-time algorithms that we are aware of proved to O(log ∆ + log3 log n) by Fischer [12], via improving the
is that of Pai et al. [27]. They gave an algorithm with deterministic complexity.

Copyright © 2019 by SIAM

807 Unauthorized reproduction of this article is prohibited
 and in a seemingly inherent way. We next briefly explain distance k and it is not clear how to perform such a
two main issues which give rise to the need for large coloring with small messages, without significantly in-
messages in [5, 6, 14]. There is also a third issue, which creasing the round complexity.
we will discard from our general discussion here: that
related to computing a certain ruling set after shattering Our algorithm, in a Nutshell: We follow the out-
and before network decomposition, which with previous line of the shattering method and in particular use the
algorithms needed large messages.
Downloaded 11/22/21 to 86.121.161.178 Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/page/terms

O(log ∆)-round randomized algorithm of [14] for the

Large Messages in Post-Shattering: Typically pre-shattering phase, which works with single bit mes-
(though not always4 ), the pre-shattering phase is a sim- sages. This leaves components of size poly(∆) log n,
ple randomized process and it works with small mes- with some other nice properties. It is the post-
sages. After this pre-shattering, each component is of shattering phase where we depart from the old algo-
size O(∆4 log n) in the case of MIS algorithms [5, 6, 14], rithms [5, 6, 14]. In particular, unlike previous work
and of size poly(log n) in the case (∆+1)-vertex coloring where the post-shattering was deterministic, in our al-
algorithm of [5,6]. Then, the post-shattering phase deals gorithm, this phase will be a mixture of randomized and
with these remaining components by running a deter- deterministic algorithms.
ministic algorithm in each component, independently. Below, we outline the post-shattering √ algorithm
Typically, this post-shattering phase is complex and that leads to complexity log ∆ · 2O( log log n) . We
particularly, after computing a certain network decom- note that our other algorithm
√ that has complexity
position [28], it resorts to gathering the full topology in O(log ∆ · log log n) + 2O( log log n·log log log n) also has a
some neighborhood of super-constant radius and solving similar overall structure but for that we obtain a more
the problem locally. The gathered topology can be of refined network decomposition (which has fewer color
size poly(∆ log n) in the MIS case and of size poly(log n) classes). Our first post-shattering
√
algorithm, which has
in the coloring case. This topology gathering step is one round complexity log ∆ · 2O( log log n) , has three steps,
of the main parts where we inherently need large mes- as follows:
sages (and where one can argue that we are stretching In the first step, we use a new randomized
the definition of “distributed computation”). (O(1), O(log log n)) ruling set algorithm. We recall that
Large Identifiers in Post-Shattering: Another crit- an (α, β) ruling set of a set P means a set P ∗ ⊆ P
ical issue in the post-shattering phase that leads to large where each two vertices of P ∗ have distance at least α
messages in [5,6,11,14,18] has to do with identifiers. In from each other and moreover, each node of P has at
the post-shattering, the remaining nodes live in com- least one node of P ∗ within its distance β. Thanks to
ponents that are “small”, in the sense explained above, the properties of the pre-shattering phase, this ruling
but they still inherit their identifiers from the original set can be used to partition the vertices in each con-
graph. Thus, we cannot apply standard deterministic nected component into at most log n clusters, each of
algorithms on each component of size N and hope that diameter O(log log n). To the best of our knowledge,
they run as if the network size is N . This is because our ruling set algorithm is the first such algorithm that
the identifiers are much larger than the O(log N ) bound works in the CONGEST model in O(log log n) rounds.
that the deterministic algorithm assumes. Indeed, as In contrast, for this part, [14] relied on the randomized
explained by [5, 6, 14], if we run the deterministic al- ruling set algorithm of Gfeller and Vicari [13], which
gorithm with the inherited O(log n)-bit identifiers, the needs large messages.
complexity will be Ω(log n). To go around this issue, In the second step, we start with these low-diameter
the algorithms of [5,6,11,14,18] compute an N -coloring clusters and continue to compute a network decomposi-
of the k th power of the each component, for a suitable tion of each component, i.e., each of these low-diameter
√
value k which is usually at least 2Θ( log log n) . This col- clusters around a ruling set will be fully contained in
oring can be described using log N bits. These colors are one of the clusters of network decomposition. To com-
then fed to the deterministic algorithms as (fake) iden- pute the desired network decomposition, we present a
tifiers. Since these colors are unique within distance k, new deterministic CONGEST-model network decompo-
the deterministic algorithm gets fooled and works fine. sition algorithm (as claimed in Theorem 1.2). This algo-
Unfortunately, the methods used in [5, 6, 14] for com- rithm matches the bounds of the celebrated algorithm of
puting such colorings rely on topology gathering up to Panconesi and Srinivasan [28], which needed large mes-
sages. Besides having small messages, our algorithm
4 The exceptions are the (∆ + 1) vertex coloring algorithms in is considerably simpler than the recursive structure of
[11,18], which use large message to obtain certain decompositions, Panconesi and Srinivasan [28]. Thus, we are hopeful
in the pre-shattering phase. that this module will be of interest on its own and may

Copyright © 2019 by SIAM

808 Unauthorized reproduction of this article is prohibited
 find applications elsewhere, when designing determin- Lemma 2.1. [Implicit in [14]] For any n-node network
istic distributed algorithms for the CONGEST model. G = (V, E) with maximum degree at most ∆, there
More crucially for us, this network decomposition algo- is an O(log ∆)-round randomized distributed algorithm
rithm can handle identifiers that are much larger than in the CONGEST model — in fact, using just single-
the logarithm of the graph size. This is necessary for bit messages — that computes two independent sets
us, as discussed above in the issue of large identifiers in S, S 0 ⊆ V , where S ⊆ S 0 , with the following guarantees:
shattering, and may be useful also elsewhere when using
Downloaded 11/22/21 to 86.121.161.178 Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/page/terms

(A) For each node v ∈ V , we have Pr[v ∈

/ (S ∪N (S))] ≤
the shattering technique.
1/∆10 .
In the third and final step, we solve MIS on the re-
maining components, using the computed network de- (B) With high probability, each connected component C
composition. As usual, we work on the colors of net- of the graph HB induced by vertices B = V \ (S ∪
work decomposition one by one, each time computing N (S)) has at most O(∆4 log n) vertices.
an MIS of the new color, in a way that it is compatible
with the computed MIS of the previous colors. When (C) With high probability, for each connected compo-
working on one color, we just need an MIS algorithm nent C of the graph HB , any set of vertices in S 0 ∩C
for low-diameter graphs, which will be run on differ- that is 5-independent in C — that is, any two of its
ent clusters of this color concurrently. The standard vertices have distance greater than 5 in C — has
way for this was a deterministic local topology gather- cardinality at most log n.
ing [5,6,14], which needs large messages. Instead, we use
General Outline of the Post-Shattering: In the
a randomized algorithm for this step. In particular, we
post-shattering part, the remaining task is to augment
run O(log n) independent copies of Ghaffari’s random-
this set S 0 , by adding some more vertices to it from
ized MIS algorithm [14], all in parallel. This is possible
B 0 = V \ (S 0 ∪ N (S 0 )), to reach maximality. For that,
in the CONGEST model thanks to the fact that the lat-
we have three main steps, which we outline here and
ter algorithm uses single-bit messages. Then, we know
then discuss one by one, in the following subsections:
that, with high probability (we emphasize that this is a
(I) We first compute a (5, O(log log n)) ruling set B ∗
probability of at least 1 − 1/poly(n) where n is the size
of B 0 = V \ (S 0 ∪ N (S 0 )) in O(log log n) rounds, with
of the whole network), at least one of these independent
respect to distances in the graph induced by vertices
copies of the algorithm succeeds in computing an MIS
B = V \ (S ∪ N (S)). Then we cluster vertices of each
of the cluster. We then use time proportional to the
component C of HB , by defining one cluster centered
diameter of the cluster to pick such a successful run of
at each node of B ∗ ∩ C and making each node join the
the algorithm, among the O(log n) copies. After that,
cluster of the closest center. Thanks to Lemma 2.1, this
we can proceed to the next color class of the network
will mean that we have O(log n) clusters in component
decomposition.
C. This will allow us to think that we are now dealing
with a graph that has O(log n) nodes, roughly speaking.
2 MIS, First Algorithm
This is not precisley correct because each of these is a
In this section, we explain a randomized MIS algo- cluster instead of a single node, and also because we
rithm,
√
with O(log n)-bit messages that runs in log ∆ · have large identifiers. (II) Then, we deterministically
2O( log log n) rounds. In the next section, we explain compute a network decomposition for each connected
how by changing some parts of this algorithm, we component C of HB independently. This will be with
can√obtained round complexity O(log ∆ · log log n) + the initial clustering provided by the ruling set, which
2O( log log n·log log log n) . has O(log n) clusters per component. The network
decomposition algorithm we provide for this step is
2.1 Pre-Shattering and the Outline of Post- the main contribution of this paper, especially as it is
Shattering We use the nearly-maximal independent simpler than [28] and still it can handle small messages
set algorithm of Ghaffari [14] for the pre-shattering and also large identifiers. (III) Finally, we use a
phase. To make the paper self-contained, we included a randomized procedure to solve MIS by working through
pseudo-code of this algorithm in Appendix A. This near- the color classes of network decomposition one by one:
maximality roughly means that the algorithm produces each time we essentially compute an MIS of the clusters
an independent set such that, if we remove it along with of this color in parallel, after removing vertices that
its neighbors from the graph, the remaining components are adjacent to MIS nodes of previous color classes.
are “small”. The remaining graph has a few additional For this last part, the main procedure we need is
properties, as we formalize next. a very fast CONGEST-model MIS algorithm for low-
diameter graphs, which will be run on the clusters of

Copyright © 2019 by SIAM

809 Unauthorized reproduction of this article is prohibited
 network decomposition. Although we use a randomized grained part, which primarily intends to sparsify the
approach for this step (which is unusual for post- set, and a fine-grained part. We next explain these two
shattering), this randomized algorithm will compute an parts, separately.
MIS with probability 1 − 1/poly(n) in each component, Coarse-Grained Part: The coarse-grained part has
despite the fact that it runs in sublogarithmic time, and log3/2 log n phases. Initially, set B ∗ = B 0 . In the
that allows us to union bound over all the components
ith phase, we mark each (remaining) node of B ∗ with
of HB .
Downloaded 11/22/21 to 86.121.161.178 Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/page/terms

We next discuss these three steps, in three different probability n−(1/2)(2/3) . Then, we remove from B ∗ any
subsections. unmarked node that has a marked node within distance
2k. This can be done in 2k rounds of the CONGEST
2.2 Post-Shattering: Ruling Set First, we com- model, in fact with single-bit messages. Notice that
pute a (5, O(log log n)) ruling set B ∗ of B 0 = V \ (S 0 ∪ some unmarked nodes may remain in B ∗ . We next
N (S 0 )) in O(log log n) rounds, with respect to distances discuss the properties provided by this procedure.
in the graph induced by vertices B = V \ (S ∪ N (S)). Let us now argue about the domination property of
The algorithm’s behavior in each connected component the obtained set B ∗ : Notice that we are working only
C of HB is independent of the other components, but with B ∗ and in each phase, we remove some more nodes
we guarantee that the ruling set algorithm succeeds in of it; in particular, we remove any unmarked node of B ∗
the whole graph HB , w.h.p. We present a formal state- that has a marked node within distance 2k. Thus, the
ment of our algorithm’s guarantee in Lemma 2.2, which distance of each original node of B 0 from the remaining
we will apply with parameter k = 5. B ∗ increases by at most 2k hops, per phase. This means
We comment that [14] also did this, in order to that after log3/2 log n phases, the remaining set B ∗ must
be able to enjoy the properties provided by Lemma be a (2k log3/2 log n)-dominating set of B 0 . That is,
2.1. However, the procedure in [14] is not suitable for each node in B 0 has a node of B ∗ within its distance
small messages. In particular, [14] used the randomized 2k log3/2 log n. However, this set B ∗ is not necessarily
algorithm of Gfeller and Vicari [13] for this step. That our desired ruling set because it might not be a k-
algorithm is not suitable for the CONGEST model: even independent set. We next argue that B ∗ has certain
some of its most basic steps may need large messages, local-sparseness properties: particularly, each node of
e.g., knowing the degree in the 5-power of the graph, B ∗ has O(log2 n) other nodes of B ∗ within its distance
where two nodes are adjacent if they have distance k. We use this property in the fine-grained part.
at most 5. In fact, even in the special case where For each node v ∈ B ∗ , let its ultra-degree be the
this 5-th power of the graph has small poly(log n) number of nodes of B ∗ within k hops of v, with respect
degrees, which is treated as a simpler case by Gfeller to the distances in H. We argue inductively that at
and Vicari [13] and where they resort to deterministic the end of phase i, the ultra-degree of each node is at
i

algorithms, the coloring part of those deterministic most max{n(2/3) , O(log2 n)}, w.h.p. By this invariant
algorithms cannot be implemented with O(log n)-bit applied to the previous phase, we have that at the
messages of the CONGEST model. beginning of phase i, the ultra-degree of each node v is
i−1

We next provide a new randomized ruling set algo- at most max{n(2/3) , O(log2 n)}. For phase i, if ultra-
i
rithm which is suitable for the CONGEST model. This degree of v is at most max{n(2/3) , O(log2 n)}, we have
algorithm performs a degree reduction in its initial part, nothing to prove for v. Suppose that the ultra-degree
i i−1 i
which is as fast as that of Gfeller and Vicari [13] in its of v is in (n(2/3) , n(2/3) ] and n(2/3) = Ω(log2 n).
initial part, without reading degrees in G5 . In its fi- Then, in phase i, when we mark each node of B ∗ with
i i
nal part, it departs completely from the (deterministic) probability n−(1/2)(2/3) , we expect n(1/2)(2/3) marked
(1/2)(2/3)i
method of Gfeller and Vicari [13] and uses a special ran- nodes within k hops of v. Notice that n =
domized coloring to complete the ruling set computation Ω(log n). Hence, with high probability, the number of
in the remaining graph. marked nodes within k hops of v is at least 1 and also
i
at most max{n(2/3) , O(log2 n)}. On the other hand,
Lemma 2.2. There is a randomized distributed algo- all unmarked nodes within k hops of v will be removed
rithm in the CONGEST model that, in any network from B ∗ , because v has at least one marked node within
H = (V, E) with at most n vertices, and for any set its k hops. Hence, not only the number of marked
B 0 ⊂ V and any integer k ≥ 1, with high probability, nodes within k-hops of v, but also the ultra-degree of
i
computes a (k, 10k 2 log log n) ruling set B ∗ ⊆ B 0 , with v is at most max{n(2/3) , O(log2 n)}. Recall that the
respect to the distances in H, in O(k 2 log log n) rounds. ultra-degree is the total number of nodes in B ∗ that
are within k hops of v, regardless of whether marked or
Proof. The algorithm is made of two parts, a coarse-

Copyright © 2019 by SIAM

810 Unauthorized reproduction of this article is prohibited
 not. This proves the invariant for the ith phase. Thus, Θ(log n) bits. This fits the message sizes allowed by
after log3/2 log n phases, the maximum ultra-degree is the CONGEST model.
at most d = O(log2 n). For each node b ∈ B ∗ , define its territory to be the
set of all nodes v ∈ H such that dist(v, b) ≤ i and any
Fine-Grained Part: At this point, we are left with
other node b0 ∈ B ∗ has distH (v, b0 ) ≥ distH (v, b). We
a set B ∗ that is a k log3/2 log n-dominating set of B 0
emphasize that the inequality is not strict. That is, if
and where each node of B ∗ has at most O(log2 n) other there is a different node b0 ∈ B ∗ at exactly same distance
Downloaded 11/22/21 to 86.121.161.178 Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/page/terms

nodes of B ∗ within its k hops. We now perform k distH (v, b0 ) = distH (v, b), then v still belongs to the
epochs, to attain k independence. In the ith epoch, we territory of b. Hence, the territories are not necessarily
remove some vertices from B ∗ in a manner that ensures vertex-disjoint. However, each node in the territory of b
that B ∗ is an i-independent set (i.e., any two vertices has an edge to a node that is only in the territory of b.
of it have distance greater than i in H) and moreover, Because of this, we can deliver the message describing
the distance of any B 0 node to B ∗ increases by at most all the color choices of b to all nodes in its territory,
10i log log n during this epoch. Thus, after k epochs, we in O(i) rounds. Now consider two nodes b, b0 ∈ B ∗
have a k-independent set B ∗ such that any vertex of B 0 which are at distance exactly i. If i is even, on the
has at least one vertex of B ∗ within its 10k 2 log log n shortest path connecting b and b0 , there will be one node
hops. w exactly in the middle of the path which belongs to the
In the ith epoch, we first compute a coloring of B ∗ territories of both, and hence receives the color choices
vertices with χ = O(log5 n) colors such that any two of both of them. See the right side of the Figure 1, as
vertices that are at distance i from each other have an illustration. If i is odd, as depicted on the left side
different colors. Then, we use this coloring to perform a of Figure 1, then on the shortest path connecting b and
ruling set update of this phase. We next explain these b0 , there are two consecutive nodes w and w0 with the
two steps, separately. following properties: (A) node w is at distance (i − 1)/2
Computing the coloring for one phase: For i = 1, from b and belongs exclusively00 to the∗ territory of b. This
the coloring can be done easily by applying Linial’s is because any other node b ∈ B cannot be within
(single-round) algorithm [23]. However, for i ≥ 2, distance (i − 1)/2 of b, as that0 would be a node within
computing such a coloring for a general set B ∗ does i − 1 hops 0
of b. (B) node w is at distance (i − 1)/2
not seem possible, in sublogarithmic-time. Almost any from b and belongs exclusively to the territory of b0 ,
standard method would require each node of B ∗ to know with a similar reason as before. In this case that i is
the identifiers of the other B ∗ neighbors within distance odd, we can make all nodes that belong exclusively to
i. Since there can be up to O(log n) such nodes, learning one territory send the color-choice message that they
their identifiers could take Θ(log n) rounds, which is received from their 0
own territory to all their neighbors.
more than our desired run time. We now explain how Hence, w and w are now both aware of the color choices
0
we compute a coloring of B ∗ vertices with χ = O(log5 ) of b and b . In either case of i being odd or even, node w
colors such that any two vertices that have distance at that belongs to the territory of b gets informed whether
least i have different colors, for i ≥ 2. Here, we make any of the color choices of b is blocked or not through
use of the inductive invariant that at the beginning of connections to other territories incident on w. It can
epoch i, any two vertices of B ∗ have distance at least i. thus mark each blocked color with a single bit on the
Each node b ∈ B ∗ picks Θ(log n/ log log n) colors message that carries the color choices. Once we send
uniformly at random, independently and with replace- back these marked color-choice messages from all nodes
ment, from {1, . . . , χ}. The probability that at least of the territory to b, node b learns ∗
which of its colors
one of these colors in not chosen by any of the at most is blocked by other nodes of B at distance exactly i.
2 ∗
O(log n) other B -nodes within i hops of b is at least Hence, it can pick one color that is not blocked by any
of them. This completes the coloring procedure of this
epoch.
log2 n · log n/ log log n Θ(log n/ log log n)
1−( ) = 1−1/poly(n).
log5 n Using the coloring to update the ruling set, in one
phase: Given this χ = O(log5 n)-coloring where any two
That is, b has at least one color that is not blocked vertices of B ∗ at distance at most i have different colors,
by any of the other B ∗ -nodes within its i-hops. It we can compute a ruling set B ∗∗ such that any two
just remains for b to find one such color, which we vertices of B ∗∗ have distance at least i+1 and any vertex
explain in the next paragraph. Also, notice that the of B ∗ is within 5(i + 1)(log log n) hops of some vertex of
Θ(log n/ log log n) color choices of each node b0 ∈ B ∗ B ∗∗ . For that, we find a (i + 1, (i + 1) log χ) ruling set of
can be described using Θ(log n/ log log n) · log χ = B ∗ by applying the algorithm of Awerbuch, Goldberg,

Copyright © 2019 by SIAM

811 Unauthorized reproduction of this article is prohibited
 b w w’ b’ b w b’
Downloaded 11/22/21 to 86.121.161.178 Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/page/terms

Figure 1: Territories of two nodes b, b0 ∈ B ∗ at distance i, presented for the odd case f i on the left and for the even case on the
right. Blue nodes depict those of B ∗ and the white ones are those of H \ B ∗ . In epoch i, we are given the inductive invariant that
any two vertices of B ∗ have distance at least i.

Luby, and Plotkin [2, Figure 1], using the colors as vasan [28]. We note that the latter does not work in
the identifiers. This algorithm runs in O(i log χ) = the CONGEST model.
O(i log log n) rounds of the CONGEST model. We recall The algorithm that we present deviates consider-
that an (α, β) ruling set of B ∗ means a set B ∗∗ where ably from the complex recursive structure of Panconesi
each two vertices of B ∗∗ have distance at least α from and Srinivasan [28]. In fact, our algorithm can be
each other and moreover, each node of B ∗ has at least seen as going back to an outline similar to that of
one node of B ∗∗ within its distance β. We then update the earlier network decomposition algorithm by Awer-
B ∗ ← B ∗∗ . As a consequence, the maximum distance buch, Luby, Goldberg, and Plotkin [2]. We make certain
of any vertices in B 0 from B ∗ increases by additive changes in the approach of Awerbuch et al. [2] which im-
(i + 1) log χ ≤ 10i(log log n). This achieves the invariant proves their produced network decomposition and also
of the ith epoch, ensuring that at the beginning of epoch the round complexity of the construction to match those
i + 1, any two vertices of B ∗ have distance at least i + 1. of Panconesi and Srinivasan [28], while also fitting in the
The algorithm then moves to the next epoch. CONGEST model.
There is one more difference, our network decom-
position can handle much larger identifiers. This prop-
After Ruling Set, Preparation for Network De- erty is very crucial for us in our MIS algorithm, because
composition: As mentioned before, we apply this rul- of what we have after the pre-shattering phase, as we
ing set algorithm on the whole graph HB induced by ver- briefly mentioned in Section 1.4. Let us elaborate. Af-
tices B = V \ (S ∪ N (S)) to compute a (5, O(log log n))- ter the ruling set computation performed above and the
ruling set B ∗ of B 0 = V \ (S 0 ∪ N (S 0 )) vertices. For each clustering around the ruling set vertices, we now have
component C of HB , the computed ruling set B ∗ ∩C has at most log n clusters in each component. These will be
at most log n vertices, by the third property of Lemma treated as initial clusters by the network decomposition,
2.1. We now cluster the nodes of B 0 around vertices thus allowing us to think that we start with N = log n
of B ∗ , where each node b ∈ B 0 joins the cluster of the clusters, essentially as if the network decomposition al-
closest B ∗ node according to distances in C, breaking gorithm is working on a graph with N = log n vertices.
ties by IDs. This is easy to implement in the CONGEST However, as we explained in Section 1.4, the identifiers
model by simply flooding the IDs of the B ∗ nodes for of these initial clusters (i.e., cluster centers) are inher-
O(log log n) rounds, where each node b ∈ B 0 joins the ited from the original graph and thus have Θ(log n) bits.
cluster of the first B ∗ -node whose ID it receives. These This is much larger than logarithmic in N . Hence, the
clusters will be used as the initial clusters, in the com- network decomposition algorithm that we want should
putation of the network decomposition, as we describe work for ID length linear in the network size.
next. Our network decomposition algorithm provides
this, and works even when √nodes have much larger iden-
2.3 Post-Shattering: Network Decomposition tifiers, up to S = 2 ↑↑ 2O( log N ) bits, so long as O(S)-
Next, we present a deterministic distributed algo- bit messages are admitted. The algorithms of Awerbuch
rithm for constructing network decompositions in the et al. [2] and Panconesi and Srinivasan [28] do not work
CONGEST model, which matches the bounds obtained when identifiers have length linear or even a small poly-
by the celebrated algorithm of Panconesi and Srini-

Copyright © 2019 by SIAM

812 Unauthorized reproduction of this article is prohibited
 √
i O( log N )
nomial in the network size. Put more precisely, one can √ hi = (O(1)) ≤ 2
cluster is at most . The for-
run those algorithms also in this setting but the round mer shows that log N phases suffice to reach at most
complexity would increase by an S factor, due to the rul- one cluster, at which point the algorithm colors it with
ing set component in both algorithms. This would be one color and stops. The latter
√ shows that the cluster
an O(log n) round complexity overhead in our final ran- radii remain below √the 2O( log N ) bound, which means
domized MIS algorithm5 , which is well-above our target that within the 2O( log N ) · log∗√S rounds allocated for
complexity. one phase, we can perform 2O( log N ) log∗ S iterations
Downloaded 11/22/21 to 86.121.161.178 Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/page/terms

Finally, we comment that our network decompo- of broadcasts and convergecasts in each cluster.
sition algorithm is short, simple, and self-contained, We next focus on one phase and explain how we
except for one well-known algorithmic tool: it makes merge old clusters into much fewer new clusters, with
use of Linial’s algorithm [23] that colors any network at most a constant factor larger diameter. During
of maximum degree ∆ which has S-bit identifiers with this process, we will permanently discard some old
O(∆2 ) colors, in O(log∗ S) rounds and using O(S)-bit clusters, making them clusters of the output network
messages. decomposition, after coloring them.
Building a small in-degree virtual graph H: Call
Theorem 2.1. There is a deterministic distributed al-
two clusters C and C 0 neighboring if they contain vertices
gorithm that in any N -node network, which has S-bit
v ∈ C and v 0 ∈ C such that v and v 0 are adjacent. First,
identifiers and supports O(S)-bit messages for some ar-
we make each cluster send its cluster identifier to all
bitrary S, computes a (g(N ), g(N )) network decompo-
√ neighboring clusters. Then, each cluster C convergecasts
sition in g(N ) · log∗ S rounds, for g(N ) = 2O( log N ) .
all of the identifiers that it has received, up to at most
Moreover, if initially we have N clusters, each with an
2d many
√
of them, to the cluster center, in O(d + hi ) =
S-bit center identifier and with radius at most r, the
2O( log N ) rounds. When there are more than 2d
algorithm computes a (g(N ), rg(N )) network decompo-
identifiers, the selection is arbitrary; we just need to
sition in rg(N ) · log∗ S rounds.
make sure that 2d different identifiers reach the center
Proof. We describe the algorithm for the setting where of C. This creates a directed virtual graph H among
initially each node is its own cluster. The description the clusters, where an edge C → C 0 indicates that the
is such that it easily extends to the second part of center of C 0 received the identifier of C. We call a cluster
the theorem statement, where we initially have a given high-degree if it has at least 2d neighboring clusters, and
clustering. low-degree otherwise. Notice that any low-degree cluster
√ will have all of its neighboring clusters in the base graph
Overall Structure: The algorithm √ consists of log N as incoming neighbors in H. It might have some of them
phases, each of which runs in 2O( log N ) · log∗ S rounds. as outgoing neighbors as well (though, not necessarily).
During each phase, the (remaining) vertices are parti- Moreover, each high-degree cluster will have at least 2d
tioned into vertex-disjoint clusters. Each cluster has incoming edges.
one center node, as well as a tree rooted at the center
that contains only vertices of this cluster and spans to Making H undirected with small degrees: One
all of the vertices of the cluster. As mentioned above, problem is that H is a directed graph but we would
we start with the initial setting where each node is its like to have an undirected graph (while ensuring that
own cluster. Throughout the phases, some clusters join all neighbors of a low-degree cluster are neighbors of it
each other to form a new cluster, that is, each cluster in in this virtual graph as well). For that, we first mark
phase i + 1 is formed by merging a few clusters in phase clusters of extremely high out-degree (which we define
i. Moreover, some clusters get discarded permanently, to be out-degree higher than 4d2 ), as follows: we reverse
√
after receiving a color. Let d = 2 log N
. Throughout, the communication direction where each cluster C sends
we maintain two invariants: (A) In the ith phase, we one message to each of its up to 2d many incoming
have at most N/di clusters, and (B) the radius of each neighboring clusters. We pass these messages to the
neighboring clusters, essentially traversing in reverse of
the direction of the virtual edge. Now, each cluster C 0
5 An alternative way would allow us to replace this log S factor
may have a large number of different messages that are
in the ruling set complexity with log χ, if we can compute a χ- sent to C 0 by its supposed out-neighbors in the virtual
coloring of G3 . For instance, G3 certainly a O(∆3 ) coloring,
existentially. However, it is unclear how to compute such a
cluster graph. Cluster C 0 accepts all up to 4d2 of these
coloring in the CONGEST model with O(S)-bit messages, without messages. If cluster C 0 detects that it has more than 4d2
incurring a round complexity overhead linearly proportional to the different messages directed to C 0 , we call C 0 a marked
degree of G. In fact, even the simpler task of knowing the number cluster. There are at most 2dNi+1 many marked clusters.
of neighbors in G3 seems to require a large round complexity.

Copyright © 2019 by SIAM

813 Unauthorized reproduction of this article is prohibited
 This is because each cluster has in-degree at most 2d, that each new cluster that we form is made of some
which means at most 1/(2d) fraction of clusters can of the previous clusters, all of which were within O(1)
have out-degree exceeding 4d2 . This is at most dNi · 2d
1
cluster hops of the center of the merge (either in C ∗ or
many clusters, by induction. We temporarily remove a marked cluster). Hence, the maximum cluster radius
marked clusters from H; we later discuss how we deal grows by at most a factor of O(1), which shows that the
with them. We now have an undirected virtual graph each cluster radius in phase i + 1 is at most (O(1))i+1 .
on the clusters, which has degree at most 4d2 .
Downloaded 11/22/21 to 86.121.161.178 Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/page/terms

Coloring low-degree old clusters that remain:

Computing a Maximal 2-Independent Set in H: Finally, notice that we have ensured that each high-
Since H has now degree at most 4d2 , we can simulate degree cluster is included in one of the new clusters.
one√round of CONGEST model on it in O(d2 + hi ) = There might be some old clusters that are not contained
2O( log N ) rounds of the base graph: these are simple in any of the new clusters. These must be necessarily
broadcast and convergecast in the trees of the clusters. low-degree clusters, i.e, each of them has at most 2d
In particular, each node of H broadcasts the at most many neighboring clusters. We color all these clusters
4d2 message that it wants to deliver to its H-neighbors using O(d2 ) colors, which are used only in this phase, by
to all nodes of its clusters, and on the other hand, applying Linial’s algorithm [23] which runs in O(log∗ S)
we perform a convergecast to bring together all the at rounds√of CONGEST on top of the cluster graph, that is,
most 4d2 messages coming from neighboring H-nodes in 2O( log N ) log∗ S rounds of the base graph. We note
to the root of the cluster. Using this simulation of the that we√use different colors
√ in different phases. Overall,
CONGEST model, we first compute a coloring of H 2 , that is log N · d2 = 2O( log N ) colors.
hence ensuring that any two clusters that are within 2
hops in H have different colors. That can be done in 2.4 Post-Shattering: MIS atop Network De-
O(d8 log∗ S · (d4 + hi )) rounds, using Linial’s algorithm composition The algorithm described√ in the√ previous
[23]. This algorithm takes O((d0 )2 log∗ S) rounds of the subsection computes a (2O( log log n) , 2O( log log n) )-
CONGEST model to color a graph with maximum degree network
√ decomposition of each component, in
d0 and S-bit ids. Since we are working on coloring H 2 , 2O( log log n) rounds. Given this network decom-
our maximum degree is d0 = O(d4 ). Moreover, each position, we now just need an algorithm that solves
CONGEST round of H 2 can be simulated in O(d4 + hi ) MIS in low-diameter graphs: given that, we would
rounds of the base graph. Given this coloring, we process the colors of network decomposition one by
compute a maximal 2-independent set C ∗ of high-degree one, and for each color, we would invoke the algorithm
clusters (this is the definition of high-degree mentioned for low-diameter graphs in each cluster of this color
above, which is with respect to the original graph among of the decomposition, all in parallel. Thus, the main
clusters), by greedily processing the colors one by one. missing piece is this MIS algorithm for low-diameter
Here, 2-independent set means that no two clusters in graphs, which is what we discuss next. In particular,
C ∗ should share a common neighboring cluster in H. in Theorem 2.2, we present a randomized algorithm
Any cluster C that has a cluster C 0 ∈ C ∗ within its 2 that computes an MIS in O(D + log N ) rounds, in any
cluster-hops joins the new cluster that is being formed network of size N ≤ n and diameter D, with probability
at the center of C 0 . at least 1 − 1/poly(n). In our application, when we run
this MIS on each cluster of the network decomposition,
Forming new clusters: Each high-degree cluster C 0 ∈ √
we have D = 2O( log log n) and N = O(∆4 log n).
C ∗ has two cases: (A) either none of the neighboring
Thus, we would get an algorithm with complexity
clusters of C 0 were marked, in which case all of them √
log ∆ + 2O( log log n) for processing each color of the
will join the cluster of C 0 and that cluster has at least √
decomposition. Since we have 2O( log log n) colors,
2d many of the old clusters. Thus, there are at most
N 1 which are processed
√ one by one, the overall complexity
di · 2d many such new clusters. (B) at least one of the is log ∆ · 2O( log log n) for computing an MIS of each
neighboring clusters of C 0 was marked. In this case,
component of the graph HB .
after C 0 accepts the clusters that want to join with it,
We note that using a randomized algorithm at this
it picks one of its marked neighbors and joins a new
point might seem unusual, because the post-shattering
cluster centered on that marked cluster. Since there
phase of the recent algorithms [5, 6, 11, 14, 18] and espe-
are at most 2dNi+1 many marked clusters, the number
cially the part of computing MIS or coloring after having
of the new clusters of this kind is also at most 2dNi+1 .
N
the network decomposition has been deterministic and
Therefore, overall, we have at most di+1 new clusters. worked by gathering certain local topologies. The use of
This proves the invariant about the number of clusters deterministic algorithms was so that we can argue that
in each phase. Regarding the other invariant, notice all components finish at the same time. Notice that

Copyright © 2019 by SIAM

814 Unauthorized reproduction of this article is prohibited
 the typical guarantees of randomized algorithms, which main change is in the network decomposition √ part: we
would upper bound the failure probability in the com- spend more time—particularly 2O( log log n·log log log n)
ponent to 1/poly(N ) where N denotes the component rounds—and as a result, we obtain a form of network
size, would not suffice to admit a union bound over alldecomposition (though, with a more subtle definition)
which
components. In our case, the failure probability will be √
has only O(log log n) colors, and radius at most
upper bounded to 1/poly(n), which allows us to union O( log log n·log log log n)
2 . Then, the MIS algorithm is run
bound over all components. To ensure such a low fail-
Downloaded 11/22/21 to 86.121.161.178 Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/page/terms

on each of the clusters of this network decomposition as

ure probability (despite the small component size and in the previous section. Since we have to work through
small running time), we also resort to deterministic al-
only O(log log n) colors one by one, the overall complex-
√
gorithms in some steps of the process. But we also use ity becomes O(log ∆ · log log n) + 2O( log log n·log log log n) .
some randomness along the way to massage the prob- The next lemma describes the network decompo-
lem into cases that can be handled more efficiently using
sition that we compute for the purpose outlined above,
deterministic algorithms. after having the clusters centered at the ruling set nodes,
Theorem 2.2. Consider an N -node network with di- as computed in Section 2.2.
ameter D, which supports O(log n)-bit messages and for Lemma 3.1. Consider a network with at most n nodes,
n ≥ N . There is a randomized distributed algorithm which supports O(log n)-bit messages. Suppose that we
that computes an MIS of this network in O(D + log N ) are given a partition of the network into N = O(log n)
rounds, with probability at least 1 − 1/poly(n). clusters, each with an O(log n)-bit center identifier and
Proof. We perform O(logN n) runs of the O(log N )- with radius at most r = O(log log n). Let G be the vir-
round randomized MIS algorithm of Ghaffari [14], all tual graph resulting from contracting each cluster into
at the same time, i.e., in O(log N ) rounds. Notice one meta-node, where two clusters are connected if
that the algorithm of [14], as recapped in Appendix they contain two adjacent nodes. There is a deter-
A, works with 1-bit messages per round. Hence, we ministic distributed algorithm, with O(log n)-bit mes-
can run O(logN n) independent copies of this algorithm, sages, that computes a network decomposition of these
all at the same time, by putting the related single-bit N meta-nodes into super-clusters labeled with log N =
messages all together in one message of size O(logN n) ≤ O(log log n) colors, with the following property: no two
O(log n). Each algorithm succeeds in finding an MIS super-clusters of the same color are adjacent in the
with probability 1−1/poly(N ). Since we have O(logN n) G, (B) for each color, we can deliver one O(log n)-bit
independent runs of the algorithm, with probability message from the center of each super-cluster of this
1−1/poly(n), at least one of them succeeds in finding an color to all of the nodes in its super-cluster, for all
MIS. We just need to identify one successful run which the √super-clusters of this color at the same time, in
produced a correct MIS. We do that in O(D) rounds, as 2O( log log n·log log log n) rounds.
follows: For each run, we first do a local test: each node
v sends a single bit to each of its neighbors indicating
whether v is in the MIS or not. Then, each node u can Proof. First, √we use a deterministic algorithm
determine if a local constraint of MIS around u is not that in 2O( log log n·log log log n) rounds, computes
satisfied, that is, if u is in the MIS and a neighbor of it an √intermediate network decomposition of G into
v is also in the MIS, or if u is not in the MIS and it has 2O( log log n·log log log n) colors, with the following prop-
no neighbor in the MIS. Notice that the single bits of erties: (I) each cluster of this√ intermediate network
the local tests of all the O(logN n) independent runs fit decomposition has radius 2O( log log n·log log log n) and
in one O(logN n)-bit message. Once we have the results (II) each two clusters of the same color have distance
of these local tests, we do an O(D) round aggregation, at least K = Θ(log log n) in G.
so that for each run, each node v knows whether any For this part, the procedure is very similar to the
local constraint is left unsatisfied in that run or not proof of Theorem 2.1, except for one change, which we
(anywhere in the whole graph). At the end, all nodes outline next: We√ change the threshold parameter d =
√ √
pick the first run that satisfies all the constraints. 2O( log N ) = 2O( log log n) to d =p2O( log log n·log log log n) .
Because of this, we will have O( log log n/ log log log n)
3 MIS, Second Algorithm phases. In each phase, instead of working on the virtual
In this section, we explain how to obtain an MIS algo- graph resulting from contracting each cluster, we work
rithm with O(log n)-bit messages that√
has round com- on the K-th power of it, that is, we think of any
plexity of O(log ∆ · log log n) + 2O( log log n·log log log n) , two clusters C and C 0 as connected (which means we
which is an improvement for higher degree graphs. The want them to have different colors, if they get colored

Copyright © 2019 by SIAM

815 Unauthorized reproduction of this article is prohibited
 in this phase) if we can go from C to C 0 by passing are joined together as one super-cluster of the output
through at most K clusters. The rest of the procedure decomposition.
is similar to Theorem 2.1. For instance, each cluster We note that the balls that start from different clus-
learns up to 2d of its neighbors on this K-th power as its ters of color 1 of the intermediate network decomposi-
incoming edges and then we mark any cluster that has tion can grow simultaneously. This is because they will
more than 4d2 outgoing√ edges. Notice that this can be never reach each other, since originally they had dis-
done in O(Kd2 ) = 2O( log log n·log log log n) rounds. The tance at least C log log n hops in G and each ball grows
Downloaded 11/22/21 to 86.121.161.178 Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/page/terms

arguments are similar to Theorem 2.1 except that now, at most log N hops.
each new cluster is formed by putting together some Then, we proceed to the next iteration. In the
clusters that were within O(1) hops in the K-th power ith iteration, we perform a similar ball growing process
graph. Hence, here, the diameter of the new clusters from the clusters of color i of the intermediate network
can be an O(K) = O(log log n) factor larger than the decomposition (while ignoring meta-nodes that were
maximum p diameter of the old clusters. This means deactivated in previous iterations). After going through
after O( log log n/ log log log n), the√ maximum cluster all the iterations and all the colors, we have managed to
diameter can become at most 2O( log log n·log log log n) . put at least 1/2 of the meta-nodes in super-clusters and
Since the last coloring step in each phase is run on the at most N/2 meta-nodes remain for the next phases.
K-th power of the cluster graph, any two clusters that The next phases repeat the same process by reac-
receive the same color must have distance at least K in tivating all the deactivated meta-nodes and then per-
G. forming a similar iterative ball carving on them. Since
We now compute the log log n colors of the output each time the number of remaining meta-nodes reduces
network decomposition, in log log n phases, using the by a 2 factor, we are done after log N = O(log log n)
intermediate network decomposition computed above. phases. By the construction, and since in each phase,
Let us describe the first phase; the other phases are we deactivated the boundary meta-nodes of each ball,
similar. √
it is clear that no two super-clusters of the same color
For the first phase, we have √ 2O( log log n·log log log n) are adjacent. This gives property (A) of the lemma.
iterations, each made of 2O( log log n·log log log n) rounds. Property (B) is follows directly from the construc-
In the first iteration, we start a deterministic ball tion of the super-clusters in the phase. This is because
growing process centered at the clusters of color 1 of we managed to deliver one message√from each super-
the intermediate network decomposition. Let us start cluster center to all of its nodes in 2O( log log n·log log log n)
with the description for one ball; we then explain that rounds when carving the related ball. We can repeat the
different balls that grow at the same time can work in same schedule of communications to satisfy (B) and de-
parallel and independently. liver any other O(log n)-bit message from the center of
Consider one ball which initially is just all the a super-cluster to all of the nodes in its super-cluster,
meta-nodes in one cluster of color 1 of the intermediate all at the same time.
network decomposition. We Call a meta-node of G a
boundary for this ball if at least one of its neighbors in MIS atop Network Decomposition: Given the de-
G is not in the ball. We call the ball good if the size composition provided by Lemma 3.1, we can now eas-
of its boundary is at most equal to the non-boundary ily solve MIS on the remaining components, using a
nodes of it. If the ball is not good, we grow it by one style similar to Theorem 2.2. In particular, we work on
hop in G. In that case, by definition of a good ball, the O(log log n) color classes of this network decompo-
this ball grows by at least a 2 factor in terms of its sition one by one. Per color class, we spend O(log ∆) +
√
number of meta-nodes. We repeat this until we reach 2 O( log log n·log log log n)
rounds. In one color class, we
a good ball. That happens within log N = O(log log n) just need to solve MIS in each super-cluster, which is
steps of growth as otherwise the ball would have more disconnected from the other super-clusters of the same
√
than 2log N meta-nodes of G, which is a contradiction. color and has radius at most 2O( log log n·log log log n) .
Notice
√ that each step of growth can be performed in We simply run O(log n) parallel randomized MIS al-
2O( log log n·log log log n) rounds, because we simply need gorithms, similar to Theorem 2.2, and then use time
to aggregate at the center the number of meta-nodes in proportional to this radius to pick the first successful
the ball as well as the number of boundary meta-nodes, run, by leveraging property (B) of Lemma 3.1 which al-
after which we can determine whether the boundaries lows us to deliver one O(log n) bit from the center of
are more than half or not. Once a ball is good, we super-cluster to all its nodes (and also the reverse of
take its boundary meta-nodes and deactivate them for that, simply by reversing the timing of the communica-
this phase. The non-boundary meta-nodes of one ball tions).

Copyright © 2019 by SIAM

816 Unauthorized reproduction of this article is prohibited
 4 Implications on Other Problems O(log n) parallel coloring algorithms, we would like to
be able to write O(log n) independent color choices of
Coloring: We now discuss how our first MIS algorithm node v in poly(log log n) messages, i.e., using O(log n ·
leads to a coloring
√ of vertices with ∆ + 1 colors, in poly(log log n)) bits. However, that is not immedi-
O(log ∆)+2O( log log n) rounds of the CONGEST model, ately possible, as the colors come from the remaining
thus proving Theorem 1.3. palette Lv , which is left over from the original palette
{1, 2, . . . , ∆ + 1}. That is, even though |Lv | ≤ N , it is
Downloaded 11/22/21 to 86.121.161.178 Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/page/terms

Proof. [Proof Sketch of Theorem 1.3] Barenboim et al.

[5, 6] provide a pre-shattering algorithm for (∆ + 1)- not clear if Lv is such that one can encode one color
vertex-coloring, which runs in O(log ∆) rounds of the choice from Lv using log(|Lv )|) or even poly(log(|Lv )|))
CONGEST model. As before, the need for large mes- bits.
sages was in the post-shattering phase, which we per- We use a hashing idea to go around this issue. In
form differently. In the case of coloring, the remaining particular, we use the universal hash family of Carter
graph after these O(log ∆) rounds of pre-shattering is and Wegman [9]: Pick a prime number p ∈ [N 4 , 2N 4 ]
made of components of size N = poly(log n) [5, 6]. We and then, for the ith run, define a random hash function
note that the problem remaining in each component is a hi : 1, . . . , ∆ + 1 → {0, . . . , p − 1} as follows: choose two
list-coloring problem: each remaining node v has a list random numbers ai , bi ∈ {0, . . . , p−1} where ai 6= 0 and
Lv of remaining colors, which are not taken by its al- define hi (x) = (ai x + bi ) mod p. Notice that it takes
ready colored neighbors, and we have the promise that only O(log N ) bits to describe ai and bi , and thus all
|Lv | ≥ deg(v) + 1, where deg(v) denotes the degree of hash functions of all the O(log n) runs can be described
v among uncolored nodes. Without loss of generality, in O(log n log log n) bits, i.e., O(log log n) messages of
by discarding some colors when needed, we can assume the CONGEST model. These message can be delivered √
that |Lv | ≤ N . to all nodes of the cluster in O(log log n) + 2O( log log n)
There is a simple O(log N ) round randomized algo- rounds, which means we can assume that all nodes of
rithm to solve the aforementioned list-coloring problem the cluster know the hash functions. Now, if we apply
(see [19] and also [5]): per round, each node picks a ran- these hash functions to the palette of each node, we get
dom color of its remaining list and keeps it permanently new palettes in the range {0, . . . , p − 1}.
if it is not picked by any of the neighbors; nodes who do For each run, we have the property that the prob-
not receive a color update their list by removing the col- ability of two colors in the original palette of any node
ors taken by permanently colored neighbors. However, in the cluster hashing to the same new color is at
since we run for only O(log N ) rounds, the success prob- most N · N 2 · 1/N 4 ≤ 1/N . Thus, with probabil-
ability of this algorithm is only 1−1/poly(N ). Formally, ity at least 1 − 1/N , each node v gets a new palette
this algorithm computes a coloring of some of the nodes L0v ⊆ {0, . . . , p − 1} with |L0v | ≥ deg(v) + 1. If in a run,
(potentially, leaving some uncolored) which is guaran- a node v has a collision in its hash, we call node v badly
teed to have no two adjacent nodes with the same color, hashed for this run, and we stop v from the run; more-
and moreover, with probability 1 − 1/poly(N ), all nodes over, we call that run badly hashed and we will discard
are colored. This success probability is not good enough this run at the end, once we detect it.
to admit a union bound over all components. We boost Let us examine runs that are not badly hashed. In
this success probability using a network decomposition. each such run, the color choice in this new palette can
We apply the network decomposition of Theorem be described using O(log N ) = O(log log n) bits. Since
2.1 directly, on each√of these components, thus obtaining the CONGEST model allows O(log n)-bit messages, this
√
a (2O( log log n) , 2O( √
log log n)
) network decomposition of give us room to perform all the O(log n) independent
O( log log n) runs of the coloring algorithm in parallel, with just
each of them in 2 rounds. Then, we solve
an O(log log n) factor slow down. Each run needs
this instance of list coloring by working through the
O(log N ) = O(log log n) rounds and computes a coloring
color classes of the network decomposition, one by one,
that is proper, and with probability 1 − 1/poly(N ), all
similar to what we did in Theorem 2.2.
nodes are colored. Since the run of each algorithm
Let us discuss one color class of the network decom-
takes O(log N ) = O(log log n) rounds, performing them
position. We run O(log n) many independent instance
all together takes at most O((log log n)2 ) rounds of the
of the O(log N )-round basic random coloring algorithm,
CONGEST model—this is because the messages of each
described above, independently in each of the clusters
round, for all the parallel runs, fit in O(log n log log n)
of this color class, and at the end we pick one successful
bits.
coloring run for this cluster, among the O(log n), which
Once the runs are complete, for each run i, each
we show to exist with probability at least 1 − 1/poly(n).
node v that is colored maps back the color y ∈ L0v ⊆
Let us focus on one cluster. To be able to run

Copyright © 2019 by SIAM

817 Unauthorized reproduction of this article is prohibited
 {0, . . . , p − 1} that it obtained to h−1 (v) ∈ Lv ⊆ The final output is a (2, β)-ruling set. The indepen-
{1, . . . , ∆ + 1}. Notice that if the node v was not badly dence of it holds trivially because of the last step being
hashed, there is exactly one color q in its palette Lv that an MIS computation. Moreover, each node v of G has
matches this satisfies hi (q) = y. Moreover, this must be a node in the finally chosen set within its distance β,
a proper coloring: if two neighbors v, u get the same because in each of the steps, the distance from the v to
color q ∈ {1, . . . , ∆ + 1} as a result of this method, they the output set grows by at most one.
would be both colored with hi (q) ∈ {0, . . . , p−1}, which Given the round complexity of each sparsify call and
Downloaded 11/22/21 to 86.121.161.178 Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/page/terms

contradicts the properness of the coloring computed by that of the MIS algorithm, the overall round complexity
the algorithm with palettes from {0, . . . , p − 1}. is
Each run that is not badly hashed succeeds in log ∆ log(f1 log n) log(fβ−2 log n)
coloring all nodes of each cluster of with probability + +· · ·+ +Tfβ−1 log n .
log f1 log f2 log fβ−1
1 − 1/poly(N ). The probability of being badly hashed
in 1/N , in which case the run is detected and discarded. Here, Td denotes the complexity of solving MIS in the
Hence, each run produced a proper coloring with proba- CONGEST model in a graph with maximum degree
bility at least 1 − 2/N , and unsuccessful runs can be de- at most d, which√
we know is at most min{O(log √
d·
tected. Since we have O(log n) independent runs, with log log n) + 2O( log log n·log log log n) , log d · 2O( log log n) }.
probability 1 − √
1/poly(n), at least one run succeeds. By setting fi properly, we can obtain the following three
i
O( log log n)
We spend 2 rounds in each cluster to iden- complexities. By setting fi = √(log ∆)1− β and using
tify one such successful run (by a simple convergecast Td = O(log d · log log n) + 2O( log log n·log log log n) , we
and broadcast, similar to what we did for MIS) and we obtain asymptotic complexity
keep its colors. We then proceed to the next color class √
of the network decomposition. Before doing that, we β(log ∆)1/β +(log ∆)1/β log log n+2O( log log n·log log log n)
.
need to update the lists of the remaining colors, in one
single round, by removing colors that are already taken i
By √setting fi = (log ∆)1− β and using Td = log d ·
by permanently colored neighbors. Then, we are ready
2O( log log n) , we obtain asymptotic complexity
for the next color √ class of the network decomposition. √
Over all the 2O( log log n) color classes of the network de- β log1/β ∆ + log1/β ∆ · 2O( log log n) .
composition, the round complexity√complexity for this
post-shattering phase becomes 2O( log log n) . i
By setting fi = (log ∆)1− β−1 and using TO(log n) =
√
O( log log n)
Ruling Set: We next explain how one can use our 2 , we obtain asymptotic complexity
√
MIS algorithms, in combination with a recursive spar- β log1/(β−1) ∆ + 2O( log log n) .
sification of Kothapalli an Pemmaraju [20] and Bisht
et al. [8], to obtain the ruling set algorithm claimed in
Theorem 1.4.

Proof. [Proof Sketch of Theorem 1.4] We will make use Acknowledgment

of the sparsify procedure of Kothapalli an Pemmaraju I am thankful to a number of people with whom we
[20], which works in the CONGEST model. This pro- have discussed the issue of needing large messages in
cedure receives a parameter f , and when called on a the MIS algorithms of [5,6,14] over the past three years,
graph H = (VH , EH ) with maximum degree ∆H , in in some cases including (unsuccessful) attempts toward
O(logf ∆H ) rounds, it computes a subset VH0 ⊆ VH with resolving it: Yi-Jun Chang, Manuela Fischer, Stephan
the following two properties with high probability: (1) Holzer, Fabian Kuhn, Nancy Lynch, Daan Nilis, Merav
each node v ∈ VH is either in VH0 or has a neighbor in Parter, Seth Pettie, and Hsin-Hao Su. I am also
VH0 , and (2) each node v 0 ∈ VH0 has at most O(f log n) thankful to Keren Censor-Hillel, Fabian Kuhn, Merav
neighbors in VH0 . To compute a β-ruling set, we have Parter, and Aravind Srinivasan for discussions about
β − 1 recursive calls to the sparsify subroutine and then the message sizes in network decomposition algorithms
one MIS call. The (i + 1)th call to sparsify works on the of [2, 28]. Finally, I am very grateful to an anonymous
subgraph induced by the output of the ith call and uses reviewer of SODA’19, who provided the hashing idea
a parameter fi , to be fixed later. The call to the MIS used in Theorem 1.3. This is used to deal with the
algorithm runs on the graph induced by the output of bit complexity of representing colors from the original
the last call to the sparsify subroutine. We use our MIS palette.
algorithm for this last step.

Copyright © 2019 by SIAM

818 Unauthorized reproduction of this article is prohibited
 References Symp. on Theory of Comp. (STOC), pages 784–797,
2017.
[1] N. Alon, L. Babai, and A. Itai. A fast and simple ran- [17] M. Hańćkowiak, M. Karoński, and A. Panconesi.
domized parallel algorithm for the maximal indepen- On the distributed complexity of computing maximal
dent set problem. Journal of algorithms, 7(4):567–583, matchings. In Pro. of ACM-SIAM Symp. on Disc. Alg.
1986. (SODA), pages 219–225, 1998.
[2] B. Awerbuch, M. Luby, A. V. Goldberg, and S. A. [18] D. G. Harris, J. Schneider, and H.-H. Su. Distributed
Downloaded 11/22/21 to 86.121.161.178 Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/page/terms

Plotkin. Network decomposition and locality in dis- (∆+ 1)-coloring in sublogarithmic rounds. In Proc. of
tributed computation. In Proc. of the Symp. on Found. the Symp. on Theory of Comp. (STOC), pages 465–
of Comp. Sci. (FOCS), pages 364–369. IEEE, 1989. 478, 2016.
[3] L. Barenboim and M. Elkin. Distributed graph color- [19] Ö. Johansson. Simple distributed ∆+ 1-coloring of
ing: Fundamentals and recent developments. Synthesis graphs. Information Processing Letters, 70(5):229–232,
Lectures on Distributed Computing Theory, 4(1):1–171, 1999.
2013. [20] K. Kothapalli and S. Pemmaraju. Super-fast 3-
[4] L. Barenboim, M. Elkin, and F. Kuhn. Distributed ruling sets. In LIPIcs-Leibniz International Proceed-
(∆+1)-coloring in linear (in ∆) time. SIAM Journal ings in Informatics, volume 18. Schloss Dagstuhl-
on Computing (SICOMP), 43(1):72–95, 2014. Leibniz-Zentrum fuer Informatik, 2012.
[5] L. Barenboim, M. Elkin, S. Pettie, and J. Schneider. [21] F. Kuhn, T. Moscibroda, and R. Wattenhofer. What
The locality of distributed symmetry breaking. In cannot be computed locally! In Proc. of the Symp. on
Proc. of the Symp. on Found. of Comp. Sci. (FOCS), Princ. of Dist. Comp. (PODC), pages 300–309. ACM,
pages 321–330, 2012. 2004.
[6] L. Barenboim, M. Elkin, S. Pettie, and J. Schneider. [22] F. Kuhn, T. Moscibroda, and R. Wattenhofer. Local
The locality of distributed symmetry breaking. Jour- computation: Lower and upper bounds. Journal of the
nal of the ACM (JACM), 63(3):20, 2016. ACM (JACM), 63(2):17, 2016.
[7] J. Beck. An algorithmic approach to the Lovász local [23] N. Linial. Distributive graph algorithms – global
lemma. I. Random Structures & Algorithms, 2(4):343– solutions from local data. In Proc. of the Symp. on
365, 1991. Found. of Comp. Sci. (FOCS), pages 331–335, 1987.
[8] T. Bisht, K. Kothapalli, and S. Pemmaraju. Brief [24] Z. Lotker, B. Patt-Shamir, and S. Pettie. Improved
announcement: Super-fast t-ruling sets. In Proc. of distributed approximate matching. In Pro. of Symp.
the Symp. on Princ. of Dist. Comp. (PODC), pages on Parallel Alg. and Arch. (SPAA), pages 129–136,
379–381. ACM, 2014. 2008.
[9] J. L. Carter and M. N. Wegman. Universal classes [25] M. Luby. A simple parallel algorithm for the maximal
of hash functions. Journal of computer and system independent set problem. In Proc. of the Symp. on
sciences, 18(2):143–154, 1979. Theory of Comp. (STOC), pages 1–10, 1985.
[10] Y.-J. Chang, T. Kopelowitz, and S. Pettie. An expo- [26] M. Luby. A simple parallel algorithm for the maximal
nential separation between randomized and determin- independent set problem. SIAM journal on computing
istic complexity in the local model. In Proc. of the (SICOMP), 15(4):1036–1053, 1986.
Symp. on Found. of Comp. Sci. (FOCS), pages 615– [27] S. Pai, G. Pandurangan, S. V. Pemmaraju, T. Riaz,
624, 2016. and P. Robinson. Symmetry breaking in the congest
[11] Y.-J. Chang, W. Li, and S. Pettie. An optimal model: Time-and message-efficient algorithms for rul-
distributed (∆+ 1)-coloring algorithm? In Proc. of ing sets. In Proc. of the Int’l Symp. on Dist. Comp.
the Symp. on Theory of Comp. (STOC), pages 445– (DISC), 2017.
456, 2018. [28] A. Panconesi and A. Srinivasan. Improved distributed
[12] M. Fischer. Improved deterministic distributed match- algorithms for coloring and network decomposition
ing via rounding. In Proc. of the Int’l Symp. on Dist. problems. In Proc. of the Symp. on Theory of Comp.
Comp. (DISC), 2017. (STOC), pages 581–592. ACM, 1992.
[13] B. Gfeller and E. Vicari. A randomized distributed [29] D. Peleg. Distributed Computing: A Locality-sensitive
algorithm for the maximal independent set problem Approach. Society for Industrial and Applied Mathe-
in growth-bounded graphs. In Proc. of the Symp. on matics, Philadelphia, PA, USA, 2000.
Princ. of Dist. Comp. (PODC), pages 53–60, 2007. [30] J. Schneider and R. Wattenhofer. A new technique
[14] M. Ghaffari. An improved distributed algorithm for for distributed symmetry breaking. In Proc. of the
maximal independent set. In Pro. of ACM-SIAM Symp. on Princ. of Dist. Comp. (PODC), pages 257–
Symp. on Disc. Alg. (SODA), pages 270–277, 2016. 266, 2010.
[15] M. Ghaffari, D. G. Harris, and F. Kuhn. On deran-
domizing local distributed algorithms. In Proc. of the
Symp. on Found. of Comp. Sci. (FOCS), 2018.
[16] M. Ghaffari, F. Kuhn, and Y. Maus. On the complexity
of local distributed graph problems. In Proc. of the

Copyright © 2019 by SIAM

819 Unauthorized reproduction of this article is prohibited
 A The Nearly Maximal Independent Set sages6 . The only place in above code where we use larger
Algorithm of [14] messages is to send the pt (v) value to the neighbors.
To have a near-maximal independent set, we run T = However, notice that each node v starts at p0 (v) = 1/2
Θ(log ∆) iterations of the following algorithm, which is and per iteration, it updates its probability as either
described here from the viewpoint of each node v: pt (v) = pt−1 (v)/2 or pt (v) = min{2pt−1 (v), 1/2}. This
choice can be reported to the neighbors with just a sin-
gle bit, which allows them to keep track of the pt (v)
Downloaded 11/22/21 to 86.121.161.178 Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/page/terms

The algorithm for node v: The algorithm is value of v.

divided into iterations, each of which consists of
three consecutive rounds. In each iteration t ≥ 1,
node v has a probability parameter pt (v). Initially,
we set p0 (v) = 1/2.

For each iteration t ∈ {1, 2, . . . , T }, we have three

rounds, as follows:

(R1) At the beginning of the round, node v sends

its probability pt−1 (v) of the previous iteration
to its neighbors. By the end of the round,
node v receives the probability pt−1 (u) of each
neighbor
P u ∈ N (v). It then sets dt−1 (v) =
u∈N (v) t−1 (u) and updates its probability
p
using the following deterministic rule.
(
pt−1 (v)/2, if dt−1 (v) ≥ 2
pt (v) =
min{2pt−1 (v), 1/2}, if dt−1 (v) < 2.

At the end, node v marks itself with probabil-

ity pt (v), and remains unmarked otherwise.
(R2) At the beginning of the round, node v sends
a message to its neighbors indicating whether
it is marked or not. By the end of the round, it
receives those messages of its neighbors, hence
learning whether any neighbor is marked. If
node v is marked and none of its neighbors is
marked, then node v joins the MIS.
(R3) At the beginning of the round, node v sends
a message to its neighbors indicating whether
v joined the MIS in the previous round or
not. By the end of the round, it receives
those messages of its neighbors, hence learning
whether any neighbor joined the MIS. Then,
if node v joined the MIS, or if it received a
message from a neighbor u indicating that u
joined the MIS, then v terminates. In that
case, node v gets removed from the problem.

Remark: We comment that the code of the algorithm 6 Though, we decided not to present it that way, in the interest

can be changed slightly to work with just single-bit mes- of keeping it more understandable.

Copyright © 2019 by SIAM

820 Unauthorized reproduction of this article is prohibited