# Can We Break Symmetry with $o(m)$ Communication?

Shreyas Pai<EMAIL_ADDRESS>The University of IowaIowa CityIAUSA ,
Gopal Pandurangan<EMAIL_ADDRESS>University of
HoustonHoustonTXUSA ,  Sriram V. Pemmaraju<EMAIL_ADDRESS>The
University of IowaIowa CityIAUSA and  Peter Robinson
<EMAIL_ADDRESS>City University of Hong KongHong Kong SAR, China

###### Abstract.

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 $\Omega(m)$
communication for these problems, where $m$ is the number of edges in the
graph. We address the following question in this paper: _can we solve problems
such as coloring and MIS using sublinear, i.e., $o(m)$ communication, and if
so under what conditions?_

In a classical result, Awerbuch, Goldreich, Peleg, and Vainish [JACM 1990]
showed that fundamental _global_ problems such as broadcast and spanning tree
construction require at least $\Omega(m)$ messages in the KT-$1$ Congest model
(i.e., Congest model in which nodes have initial knowledge of the neighbors’
ID’s) when algorithms are restricted to be comparison-based (i.e., algorithms
in which node ID’s can only be compared). Thirty five years after this result,
King, Kutten, and Thorup [PODC 2015] showed that one can solve the above
problems using $\tilde{O}(n)$ messages ($n$ is the number of nodes in the
graph) in $\tilde{O}(n)$ rounds in the KT-$1$ Congest model if _non-
comparison-based_ algorithms are permitted. An important implication of this
result is that one can use the synchronous nature of the KT-$1$ Congest model,
using silence to convey information, and solve _any_ graph problem using non-
comparison-based algorithms with $\tilde{O}(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 KT-$1$ CONGEST model, we show that any comparison-based algorithm, even
a randomized Monte-Carlo algorithm with constant success probability, requires
$\Omega(n^{2})$ messages in the worst case to solve either
$(\Delta+1)$-coloring or MIS, _regardless_ of the number of rounds. We also
show that $\Omega(n)$ is a lower bound on the number of messages for any
$(\Delta+1)$-coloring or MIS algorithm, even non-comparison-based, and even
with nodes having initial knowledge of up to a constant radius.

Upper bounds::

In the KT-$1$ CONGEST model, we present the following randomized non-
comparison-based algorithms for coloring that, with high probability, use
$o(m)$ messages and run in polynomially many rounds.

(a):

A $(\Delta+1)$-coloring algorithm that uses $\tilde{O}(n^{1.5})$ messages,
while running in $\tilde{O}(D+\sqrt{n})$ rounds, where $D$ is the graph
diameter. Our result also implies an _asynchronous_ algorithm for
$(\Delta+1)$-coloring with the same message bound but running in
$\tilde{O}(n)$ rounds.

(b):

For any constant $\varepsilon>0$, a $(1+\varepsilon)\Delta$-coloring algorithm
that uses $\tilde{O}(n/\varepsilon^{2})$ messages, while running in
$\tilde{O}(n)$ rounds.

If we increase our input knowledge slightly to radius 2, i.e., in the KT-$2$
CONGEST model, we obtain:

(c):

A randomized comparison-based MIS algorithm that uses $\tilde{O}(n^{1.5})$
messages. while running in $\tilde{O}(\sqrt{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 first-known algorithms for coloring and MIS
that take $o(m)$ messages and run in polynomially many rounds.

††copyright: none

##  1\. Introduction

There has been significant interest over the last decade in obtaining
communication-efficient algorithms for fundamental problems in distributed
computing. In the Congest model, which is a message-passing model with small-
sized messages (typically $O(\log n)$-sized, where $n$ is the number of nodes
in the network), communication cost is usually measured by the number of
messages. In the so-called _clean network_ model, a.k.a. the KT-$0$ (Knowledge
Till radius 0) model, where nodes have intial knowledge of only themselves and
don’t even know the ID’s of neighbors, Kutten et al. (Kutten et al., 2015)
showed that $\Omega(m)$ ($m$ is the number of edges in the network) is a lower
bound for the message complexity for fundamental _global_ problems such as
leader election, broadcast, spanning tree, and mimimum spanning tree (MST)
construction. This lower bound applies even for randomized Monte Carlo
algorithms. For all these problems, there exist algorithms that (essentially)
match this message lower bound; in fact, these also have optimal time
complexity (of $D$, the network diameter) in the Congest model (see e.g.,
(Kutten et al., 2015; Pandurangan et al., 2017; Elkin, 2020)).

The clean network model does not capture many real world networks such as the
Internet and peer-to-peer networks where nodes typically have knowledge of
identities (i.e., IP addresses) of other nodes. Also, there has been a lot of
recent interest in “all-to-all” communication models such as the congested
clique (Lotker et al., 2005), Massively Parallel Computing (MPC) (Karloff et
al., 2010), and $k$-machine model (Klauck et al., 2015), where each machine is
assumed to have knowledge of ID’s of all other machines. Motivated by these
applications and models, there has been a lot of recent interest in studying
message-efficient algorithms under the so-called KT-$1$ version of the Congest
model, where nodes have initial knowledge of the IDs of their neighbors, but
no other knowledge of their neighbors. An immediate question that arises is
whether the $\Omega(m)$ message lower bound also holds in the KT-$1$ model; or
whether sublinear, i.e., $o(m)$ message complexity is possible.

The above question was partially answered in a seminal paper by Awerbuch et
al. (Awerbuch et al., 1988) who initiated the study of trade-offs between the
message complexity and _initial knowledge_ of distributed algorithms that
solve _global_ problems, such as broadcast and spanning tree construction. For
any integer $\rho>0$, in the KT-$\rho$ version of the Congest model (in short,
KT-$\rho$ Congest), each node $v$ is provided initial knowledge of (i) the IDs
of all nodes at distance at most $\rho$ from $v$ and (ii) the neighborhood of
every node at distance at most $\rho-1$ from $v$. The bounds in this paper
(Awerbuch et al., 1988) are for _comparison-based algorithms_ , i.e.,
algorithms in which local computations on IDs are restricted to comparisons
only. This means that operations on IDs such as those used in the Cole-Vishkin
coloring algorithm (Cole and Vishkin, 1986) or applying random hash functions
to IDs are disallowed. Comparison-based algorithms are quite natural and
indeed, most distributed algorithms (with few notable exceptions such as Cole-
Vishkin (Cole and Vishkin, 1986) and hash-functions based algorithms of King
et al (King et al., 2015)) are comparison-based. For the KT-$1$ Congest model
the authors show that $\Omega(m)$ messages are needed for any _comparison-
based_ algorithm (even randomized) that solves broadcast. Furthermore, in the
KT-$\rho$ Congest model,
$\Omega\left(\min\left\\{m,n^{\frac{1+\Theta(1)}{\rho}}\right\\}\right)$
messages are needed for any comparison-based algorithm that solves broadcast.
The paper also shows matching upper bounds for comparison-based algorithms for
broadcast. These lower bounds also hold for non-comparison based algorithms,
where the size of the IDs is very large and grows independently with respect
to message size, time, and randomness. This paper left open the possibility of
circumventing the lower bound if one uses non-comparison based algorithms on
more natural ID spaces typically used in distributed algorithms (as assumed in
the current paper), where IDs are drawn from a polynomial-sized ID space.

Nearly 35 years later, the above question was settled by King et al. (King et
al., 2015) who showed that the Awerbuch et al. lower bounds “break” if the
assumption that the algorithms be comparison-based is dropped and one uses ID
space that is of polynomial size.111This can be relaxed to allow even
exponential-sized ID space: by using fingerprinting technique (Karp and Rabin,
1987; King et al., 2015), with high probability, one can map $n$ IDs in
exponential ID space to distinct IDs in polynomial ID space. Specifically, it
is shown in (King et al., 2015) that the Spanning Tree (and hence broadcast)
and Minimum Spanning Tree (MST) problem can be solved using $\tilde{O}(n)$
messages in KT-$1$ Congest model.222We use $\tilde{O}(f(n))$ as short for
$O(f(n)\cdot\operatorname{\text{{\rm poly}}}\log n)$ and
$\tilde{\Omega}(g(n))$ as short for $\Omega(g(n)/(\operatorname{\text{{\rm
poly}}}\log n))$. In followup papers, it is shown that these problems can be
solved with $o(m)$ messages, but with a higher message bound of
$\tilde{O}(n^{1.5})$, even in the _asynchronous_ Congest KT-$1$ model
(Mashreghi and King, 2018, 2019). Using the King et al. (King et al., 2015)
result, it is possible to solve _any_ graph problem (including symmetry
breaking problems) using randomized _non-comparison_ based algorithms in
$\tilde{O}(n)$ messages. However, this takes an _exponential_ number of
rounds. This is done by building a spanning tree using the algorithm of King
et al. and then using time-encoding to convey the entire topology to the root
of the spanning tree. The root then locally computes the result and
disseminates it to the entire network, again using time-encoding (e.g., see
(Robinson, 2021) for details). Time-encoding uses silence to convey
information and takes at least exponential (in $m$) rounds. Note that this
works only in _synchronous_ setting and not in the asynchronous model. Hence,
designing algorithms that use $\tilde{O}(n)$ (or even $o(m)$) messages for
other graph problems, including local symmetry breaking problems, regardless
of the number of rounds, in the asynchronous Congest KT-$1$ model is open.

Motivated by the above results, we initiate a similar study, but for
fundamental _local symmetry breaking_ problems, such as $(\Delta+1)$-coloring
and Maximal Independent Set (MIS). These problems have been studied
extensively for over four decades. Significant progress has been made in
understanding and improving the _running time_ (round complexity) of these
problems (see e.g., (Barenboim and Elkin, 2013; Chang et al., 2018;
Halldórsson et al., 2020; Rozhon and Ghaffari, 2020; Ghaffari, 2016, 2019;
Barenboim et al., 2012) and the references therein); however, much less is
known with respect to message complexity. For $(\Delta+1)$-coloring and MIS,
to the best of our knowledge, all known distributed algorithms use at least
$\Omega(m)$ messages. The overarching question we address in this paper is
whether these problems can be solved using $o(m)$ messages in the Congest
model and if so, under what conditions.

Our paper presents both negative and positive answers for the above question
and shows results in three general directions. First, we show that even though
the _round complexity_ of local symmetry breaking problems is provably much
smaller than the round complexity of global problems, comparison-based
algorithms for local symmetry breaking problems require _as many messages_ as
they do for global problems in the KT-$1$ Congest model. Second, we show that
if we drop the requirement that our algorithms be comparison-based only, then
it is possible to design algorithms for local symmetry breaking problems in
the KT-$1$ Congest model that use far fewer messages. Third, as we increase
$\rho$, the radius of initial knowledge, to just two, i.e., in the KT-$2$
Congest model, it is possible to design algorithms for local symmetry breaking
problems that use even fewer messages. The specific results that illustrate
these three directions are presented in the next subsection.

###  1.1. Main Results

|  $(\Delta+1)$-coloring | MIS
---|---|---
KT-$1$ | Lower Bound (C): $\Omega(m)$ | Lower Bound (C): $\Omega(m)$
Upper Bound (NC): $\tilde{O}(n^{1.5})$ | Upper Bound (C): $\tilde{O}(m)$
KT-$2$ | Lower Bound (NC): $\Omega(n)$ | Lower Bound (NC): $\Omega(n)$
| Upper Bound (C): $\tilde{O}(n^{1.5})$
KT-$\rho$ | Lower Bound (NC): $\Omega(n)$ | Lower Bound (NC): $\Omega(n)$
Figure 1. A summary of lower and upper bounds results in this paper. The
notation “(C)” and “(NC)” in each cell stand for comparison-based and non-
comparison-based respectively. The KT-$1$ upper bound of $\tilde{O}(m)$ for
MIS is not from this paper; it is immediately implied by a number of well-
known MIS algorithms (e.g., (Luby, 1985; Ghaffari, 2016)). The KT-$\rho$ lower
bounds hold for any constant $\rho\geq 1$ and hold even for non-comparison-
based algorithms.

We present new lower and upper bounds on the message complexity for two
fundamental symmetry breaking problems, namely, coloring and MIS. See Figure 1
for a summary.

Lower bounds::

In the KT-$1$ Congest model, we show that any comparison-based algorithm, even
a randomized Monte Carlo algorithm with constant success probability, requires
$\Omega(n^{2})$ messages in the worst case to solve either
$(\Delta+1)$-coloring or MIS, regardless of the number of rounds. Our result
can be considered as a counterpart to the classical result of Awerbuch et al.
(Awerbuch et al., 1988), but for local problems. We also show that in the
KT-$\rho$ Congest model, for any constant $\rho\geq 1$, $(\Delta+1)$-coloring
and MIS require $\Omega(n)$ messages even for non-comparison-based and Monte
Carlo randomized algorithms with constant success probability.

Upper bounds::

In the KT-$1$ Congest model, we present the following randomized non-
comparison-based algorithms for coloring that with high probability333This
refers to probability at least $1-n^{-c}$ for constant $c\geq 1$. (w.h.p.) use
$o(m)$ messages and run in polynomially many rounds.

(a):

A $(\Delta+1)$-coloring algorithm that uses $\tilde{O}(n^{1.5})$ messages,
while running in $\tilde{O}(D+\sqrt{n})$ rounds, where $D$ is the graph
diameter. Our result also implies an _asynchronous_ algorithm for
$(\Delta+1)$-coloring with the same message bound but running in
$\tilde{O}(n)$ rounds.

(b):

A $(1+\varepsilon)\Delta$-coloring algorithm that uses
$\tilde{O}(n/\varepsilon^{2})$ messages, while running in $\tilde{O}(n)$
rounds.

If we increase our input knowledge slightly, i.e., we work in the KT-$2$
Congest model, where nodes have initial knowledge of their _two hop-
neighborhood_ , then we get the following additional and stronger result.

(c):

A _comparison-based_ algorithm for MIS that uses $\tilde{O}(n^{1.5})$
messages, while running in $\tilde{O}(\sqrt{n})$ rounds.

Our algorithms for coloring and MIS are the first-known algorithms that take
$o(m)$ messages and running in polynomial number of rounds.

###  1.2. Other Related Work

Several recent papers (see e.g., (Gmyr and Pandurangan, 2018; Ghaffari and
Kuhn, 2018; Mashreghi and King, 2018, 2019) have studied message-efficient
algorithms for _global_ problems, namely, construction of spanning tree,
minimum spanning tree, broadcasting and leader election, in the KT-$1$ Congest
model inspired by the work of King et al. (King et al., 2015). We note that
all these are non-comparison-based algorithms. We use these prior algorithms
for our non-comparison-based algorithms in the KT-$1$ and KT-$2$ models. In a
recent paper, Robinson (Robinson, 2021) shows non-trivial lower bounds on the
message complexity of constructing graph spanners in the Congest KT-$1$ model.

In contrast to global problems, much less is known about obtaining sublinear,
i.e., $o(m)$ algorithms for local problems, such as MIS and coloring. Pai et
al. (Pai et al., 2017) showed that MIS has a fundamental lower bound of
$\Omega(n^{2})$ messages in the Congest KT-$0$ model (even for randomized
algorithms). However, this result does not extend to the KT-$1$ model. In
contrast, they also showed that the 2-ruling set problem (note that MIS is
1-ruling set) can be solved using $\tilde{O}(n)$ messages in the KT-$0$ model
in polynomial time. To the best of our knowledge, we are not aware of other
results on the message complexity (in particular, lower bounds and sublinear
upper bounds) on fundamental symmetry breaking problems, vis-a-vis the initial
input knowledge.

###  1.3. Technical Contributions

  * •

Lower bounds: To obtain our KT-$1$ Congest lower bounds for comparison-based
algorithms for $(\Delta+1)$-coloring and MIS, we start with the machinery
introduced by Awerbuch et al. (Awerbuch et al., 1988) for proving their KT-$1$
Congest lower bounds for comparison-based algorithms for broadcast. At the
core of their approach is an indistinguishability argument that uses edge
crossings. Edge crossings have been used numerous times to prove a variety of
distributed computing lower bounds (see (Korach et al., 1987; Kutten et al.,
2015; Pai and Pemmaraju, 2020; Pai et al., 2017; Patt-Shamir and Perry, 2017)
for some examples). However, in the KT-$1$ Congest model, indistinguishability
arguments via edge crossing are more challenging because when an edge incident
on a node is crossed, the node is exposed to a new ID due to KT-$1$. For
symmetry breaking problems, there is a further challenge due to the fact that
multiple outputs are possible and the indistinguishability argument needs to
work for all outputs. Finally, since we want to show our lower bounds even for
Monte Carlo algorithms with constant success probability, we require our
indistinguishability arguments to apply to a large fraction of edge crossings
(so as to be able to apply Yao’s lemma (Yao, 1977; Motwani and Raghavan,
1995)). The lower bound graph family and ID assignment we design, overcomes
all of these challenges. We use a unified construction that works for both
$(\Delta+1)$-coloring and MIS and we expect this construction to work for
other symmetry breaking problems such as maximal matching and edge coloring.

  * •

Upper bounds: Our upper bounds are largely obtained by exploiting the fact
that shared (or public) randomness combined with KT-$1$ is a powerful way of
eliminating the need to communicate over a large number of edges.444Note that
we do not a priori assume shared randomness, but only private randomness (as
is usual), but use the danner structure (Section 1.4.3) to share privately
generated random bits throughput the graph. Specifically, we start with the
recent coloring algorithm of Chang et al. (Chang et al., 2019) that works
efficiently in the MPC model. Roughly speaking, this algorithm starts with a
probabilistic step; by randomly partitioning the nodes and the color palette.
Then, after this probabilistic step, a large number of edges become inactive
for the rest of algorithm. This property is crucial to ensuring that the
algorithm is efficient in the MPC model. After the probabilistic step, nodes
exchange their state with neighbors in so that every node can determine which
of its incident edges to render inactive. This state exchange is cheap in the
MPC model, but is costly with respect to messages in the Congest model. We
show how to simulate this coloring algorithm in the Congest model without the
costly exchange of state. Instead we use shared randomness with limited
dependence combined with KT-$1$.

###  1.4. Preliminaries

####  1.4.1. KT-$\rho$ Congest model

We work in the synchronous, message-passing model of distributed computing,
known as the Congest model. The input is a graph $G=(V,E)$, $n=|V|$, which
also serves as the communication network. Nodes in the graph are processors
with unique IDs from a space whose size is polynomial in $n$. In each round,
each node can send an $O(\log n)$-bit message to each of its neighbors. Since
we are interested in message complexity, the initial knowledge of the nodes is
important. For any integer $\rho>0$, in the KT-$\rho$ Congest model each node
$v$ is provided initial knowledge of (i) the IDs of all nodes at distance at
most $\rho$ from $v$ and (ii) the neighborhood of every vertex at distance at
most $\rho-1$ from $v$.

####  1.4.2. Comparison-based Algorithms

Often, the outcome of a distributed algorithm does not depend on specific
values of node IDs, but may depend on the relative ordering of IDs. For
example, node IDs of endpoints may be used to break ties between edges of the
same weight vying to join a minimum spanning tree. In this case, only the
ordering of the IDs matters, not their specific values. Since this type of
behavior is characteristic of many distributed algorithms, Awerbuch et al.
(Awerbuch et al., 1988) formally define these as _comparison-based_
algorithms. In comparison-based algorithms, the algorithm executed by each
node contains two types of variables: ID-type variables and _ordinary_
variables. In the KT-$\rho$ Congest model, the ID-type variables at a node $v$
will store the IDs of all nodes within $\rho$ hops of $v$. Nodes can send ID-
type variables in messages, but since messages in the Congest model are
restricted to be $O(\log n)$ bits long, each message can contain only a
constant number of ID-type variables. The local computations at any node may
involve operations of the following two forms only:

  1. (1)

Comparing two ID-type variables $I_{i},I_{j}$ and storing the result of the
comparison in an ordinary variable.

  2. (2)

Performing an arbitrary computation on ordinary variables and storing the
result in another ordinary variable.

Note that if randomization is allowed, then nodes can choose to ignore the
node IDs and choose a new set of ($O(\log n)$-length) IDs and do arbitrary
computations with them. These are still comparison-based
algorithms.555However, note that such randomly chosen node IDs are unknown to
neighbors and if the algorithm uses only those IDs then this becomes
effectively the KT0 model where bounds are already known (Pai et al., 2017;
Awerbuch et al., 1988).

####  1.4.3. Efficient Broadcasting in the KT-$1$ Congest model

As explained earlier, shared randomness along with initial knowledge, plays a
key role in making our algorithms message-efficient. We use a graph structure
called a _danner_ introduced by Gmyr and Pandurangan (Gmyr and Pandurangan,
2018) to share random bits among the nodes in the graph in a message-efficient
fashion. Their specific result is stated in the following theorem.

###### Theorem 1.1 (Gmyr and Pandurangan (Gmyr and Pandurangan, 2018)).

Given an $n$-vertex, $m$-edge, diameter $D$, graph $G=(V,E)$ and a parameter
$\delta\in[0,1]$, there is a randomized algorithm in the KT-1 Congest model,
that constructs a spanning subgraph (i.e., a danner) $H$ of $G$ such that $H$
has $\tilde{O}(\min\\{m,n^{1+\delta}\\})$ edges and diameter
$\tilde{O}(D+n^{1-\delta})$ with high probability. This construction uses
$\tilde{O}(\min\\{m,n^{1+\delta}\\})$ messages and runs in
$\tilde{O}(n^{1-\delta})$ rounds with high probability.

We need the following corollary of this theorem.

###### Corollary 1.2.

Given an $n$-vertex, $m$-edge, diameter $D$ graph $G=(V,E)$ and a parameter
$\delta\in[0,1]$, there exists a randomized algorithm to solve the leader
election and broadcast problems in the synchronous KT-1 Congest model using
$\tilde{O}(\min\\{m,n^{1+\delta}\\})$ messages and in
$\tilde{O}(D+n^{1-\delta})$ rounds with high probability.

We use this corollary to share $O(\operatorname{\text{{\rm poly}}}\log n)$
random bits in a message-efficient manner by first electing a leader and then
having the leader locally generate the random bits and broadcasting them. The
message and time complexities for this operation are given by the above
corollary. We note that the above danner bounds hold in KT-$1$ Congest model,
which is _synchronous_. In the _asynchronous_ version of the KT-$1$ Congest
model, we appeal to the following result.

###### Theorem 1.3 (Mashregi and King (Mashreghi and King, 2019, 2018)).

Given an $n$-vertex, $m$-edge graph $G=(V,E)$, there exists a randomized
algorithm to construct a minimum spanning tree and (hence) solve the leader
election and broadcast problems in the asynchronous KT-1 Congest model using
$\tilde{O}(\min\\{m,n^{1.5}\\})$ messages and in $O(n)$ rounds, with high
probability.

##  2\. Message Complexity Lower Bounds

###  2.1. Technical Preliminaries

We now state key definitions and notation from Awerbuch et al. (Awerbuch et
al., 1988) which we will use in our proofs of the $\Omega(m)$ message lower
bounds for $(\Delta+1)$-coloring and MIS, for comparison-based algorithms, in
the KT-$1$ Congest model.

###### Definition 2.1 (Executions).

We denote the execution of a Congest algorithm (or protocol) $\mathcal{A}$ on
a graph $G(V,E)$ with an ID-assignment $\phi$ by $EX(\mathcal{A},G,\phi)$.
This execution contains (i) the messages sent and received by the nodes in
each round and (ii) a snapshot of the local state of each node in each round.
We denote the state of a node $v$ in the beginning of round $i$ of the
execution $EX(\mathcal{A},G,\phi)$ by $L_{i}(EX,v)$.

The _decoded representation_ of an execution is obtained by replacing each
occurrence of an ID value $\phi(v)$ by $v$ in the execution. This decoded
representation allows us to define a similarity of executions. We denote the
decoded representations of all messages sent during round $i$ of an execution
$EX(\mathcal{A},G,\phi)$ as $h_{i}(EX(\mathcal{A},G,\phi))$.

###### Definition 2.2 (Similar executions).

Two executions of a Congest algorithm $\mathcal{A}$ on graphs $G(V,E)$ and
$G^{\prime}(V,E^{\prime})$ with ID-assignments $\phi$ and $\phi^{\prime}$ are
_similar_ if they have the same decoded representation. Likewise, we say that
two messages are _similar_ if their decoded representations are the same.

A crucial element of our lower bound proof consists of taking two graphs
$G(V,E)$ and $G^{\prime}(V^{\prime},E^{\prime})$, where $G^{\prime}$ is
obtained from $G$ by “crossing” a pair of edges in $G$, and showing that the
executions of any comparison-based algorithm, on $G$ and $G^{\prime}$ are
similar. Showing similarity of executions requires that the “crossing” of
edges remains, in a certain sense, hidden from the algorithm. Below, we define
what it means for an algorithm to _utilize_ an edge. Later on we will be able
to show that if the edges being “crossed” are not utilized by the algorithm,
then the edge “crossing” is hidden from the algorithm. One way an algorithm
utilizes an edge is by sending a message across it. But, this notion of
utilization does not suffice in the KT-$1$ model. We need the stronger notion,
defined below.

###### Definition 2.3 (Utilized Edge).

An edge $e=\\{u,v\\}$ is utilized if any one of the following happens during
the course of the algorithm: (i) a message is sent along $e$, (ii) the node
$u$ sends or receives ID $\phi(v)$, or (iii) the node $v$ sends or receives ID
$\phi(u)$.

By definition, the number of utilized edges is an upper bound on the number of
edges along which a message sent. Using a charging argument, Awerbuch et al.
(Awerbuch et al., 1988) show that the number of utilized edges is also upper
bounded by a constant times the number of edges along which a message sent. We
restate their claim here.

###### Lemma 2.4 (Lemma 3.4 of (Awerbuch et al., 1988)).

Let $m_{u}$ denote the number of utilized edges in an execution
$EX(\mathcal{A},G,\phi)$. Then the message complexity of the execution is
$\Omega(m_{u})$.

###  2.2. Lower Bound Graph Construction and ID Assignments

We now describe the construction of lower bound graphs that we use for our
$\Omega(n^{2})$ message complexity lower bounds. The same construction works
for both the $(\Delta+1)$-coloring and MIS lower bounds. Recall that these
bounds are for comparison-based algorithms in the KT-1 Congest model.

We start with a graph $G(X,Y,Z,E)$ such that $|X|=|Y|=|Z|=t$ and the subgraphs
of $G$ induced by $X\cup Y$ and $Y\cup Z$ are both isomorphic to the complete
bipartite graph $K_{t,t}$. Thus, $|E|=2t^{2}$. We then add a copy
$G^{\prime}(X^{\prime},Y^{\prime},Z^{\prime},E^{\prime})$ of $G$ and consider
the graph $G\cup G^{\prime}$. We call this the _base graph_. Let $V=X\cup
Y\cup Z$ and $V^{\prime}=X^{\prime}\cup Y^{\prime}\cup Z^{\prime}$. For each
$v\in V$, the corresponding copy in $V^{\prime}$ is named $v^{\prime}$. Let
$n=|V\cup V^{\prime}|$. Thus $t=n/6$. From the base graph $G\cup G^{\prime}$,
we obtain a _crossed graph_ as follows. For a vertex $y\in Y$, _cross_ an edge
$e=\\{y,z\\}$ in $G$, where $z\in Z$ with the edge
$e^{\prime}=\\{x^{\prime},y^{\prime}\\}$ in $G^{\prime}$ where $x^{\prime}\in
X^{\prime}$ to obtain the graph $G_{e,e^{\prime}}$. When we cross the edge
$e=\\{y,z\\}\in E$ with $e^{\prime}=\\{x^{\prime},y^{\prime}\\}\in
E^{\prime}$, the resulting _crossed graph_ $G_{e,e^{\prime}}$ has vertex set
$V\cup V^{\prime}$ and edge set $(E\cup
E^{\prime}\setminus\\{e,e^{\prime}\\})\cup\\{\\{y,y^{\prime}\\},\\{x^{\prime},z\\}\\}$.
The base graph $G\cup G^{\prime}$ and the crossed graph $G_{e,e^{\prime}}$ for
edges $e\in E,e^{\prime}\in E^{\prime}$ are illustrated in Figure 2.

Figure 2.  This figure shows the base graph $G\cup G^{\prime}$ and the crossed
graph $G_{e,e^{\prime}}$, described in Section 2.2

We now define appropriate ID-assignments for the base graph and the crossed
graph. Let $S$ be an arbitrary totally ordered set such that $|S|=40t$, and
let $\overline{S}$ be the sorted list of elements in $S$ in ascending order.
We will assign distinct elements in $S$ as ID’s to the base graph and the
crossed graph. We use a short-hand and say that the ID of a vertex $v$ is
$i\in[0,40t)$, when we mean that the ID of $v$ is $\overline{S}[i]$. Note that
since $\overline{S}$ is sorted in ascending order, the relative ordering of
the indices is the same as that of the corresponding ID’s in $\overline{S}$.

Let $\phi:V\to[0,40t)$ be an ID assignment such that $\phi(v)$ is even for all
$v\in V$ and additionally $\phi(v)\in[0,2t)$ if $v\in X$,
$\phi(v)\in[10t,12t)$ if $v\in Y$, and $\phi(v)\in[20t,22t)$ if $v\in Z$. For
a vertex $y\in Y$ and pair of incident edges $e=\\{y,z\\}$ and
$e^{\prime}=\\{x^{\prime},y^{\prime}\\}$, we define a “shifted” ID assignment
$\phi^{\prime}_{e,e^{\prime}}$ for the vertex set $V^{\prime}$ of
$G^{\prime}$. We motivate this “shifted” assignment and define it precisely
further below. But for now, assuming $\phi^{\prime}_{e,e^{\prime}}$ is
defined, we define the ID assignment $\psi_{e,e^{\prime}}:V\cup
V^{\prime}\to[0,40t)$ as just the union of $\phi$ and
$\phi^{\prime}_{e,e^{\prime}}$, i.e., $\psi_{e,e^{\prime}}(v)=\phi(v)$ for all
$v\in V$ and
$\psi_{e,e^{\prime}}(v^{\prime})=\phi^{\prime}_{e,e^{\prime}}(v^{\prime})$ for
all $v^{\prime}\in V^{\prime}$. Our first goal in this subsection is to show
that these two executions

$EX=EX(\mathcal{A},G\cup G^{\prime},\psi_{e,e^{\prime}})\qquad\qquad
EX_{e,e^{\prime}}=EX(\mathcal{A},G_{e,e^{\prime}},\psi_{e,e^{\prime}})$

on the base graph $G\cup G^{\prime}$ and the crossed graph $G_{e,e^{\prime}}$
are similar for any comparison-based algorithm $\mathcal{A}$.

For the executions $EX$ and $EX_{e,e^{\prime}}$ to be similar, it must be the
case that the crossing of edges $e$ and $e^{\prime}$ is hidden from algorithm
$\mathcal{A}$. To achieve this, the ID assignment
$\phi^{\prime}_{e,e^{\prime}}$ of $V^{\prime}$ must be carefully chosen. For
example, vertex $z$ has neighbor $y$ in $G\cup G^{\prime}$, but has neighbor
$x^{\prime}$ in $G_{e,e^{\prime}}$ (see Figure 2). In the KT-1 model, $z$’s
initial local knowledge consists of vertex $y$ in $G\cup G^{\prime}$ and
vertex $x^{\prime}$ in $G_{e,e^{\prime}}$. Therefore, for $\mathcal{A}$ to not
distinguish between these two situations, it must be the case that the ID of
$x^{\prime}$ is “adjacent” to the ID of $y$. To achieve this, without
disrupting other constraints on the relative order of ID’s, we start by
assigning vertices in $X^{\prime}$ the ID’s of their corresponding vertices in
$X$ and then “shift” these by $(\phi(y)-\phi(x))+1$. As a result, vertex
$x^{\prime}$ ends up with ID $\phi(y)+1$. A similar “shift” is performed to
obtain the ID’s of vertex set $Y^{\prime}$, though this time the “shift” is by
the amount $(\phi(z)-\phi(y))+1$ because we want vertex $y^{\prime}$ to be
“adjacent” to vertex $z$. The “shift” for vertex set $Z^{\prime}$ just needs
to be so that the ID assignment is disjoint, We now define the ID assignment
$\phi^{\prime}_{e,e^{\prime}}:V^{\prime}\to[0,40t)$ as

(1)
$\phi^{\prime}_{e,e^{\prime}}(v^{\prime})=\begin{cases}\phi(v)+(\phi(y)-\phi(x))+1,\mbox{
if }v^{\prime}\in X^{\prime}\\\ \phi(v)+(\phi(z)-\phi(y))+1,\mbox{ if
}v^{\prime}\in Y^{\prime}\\\ \phi(v)+10t+1,\mbox{ if }v^{\prime}\in
Z^{\prime}\end{cases}$

Note that the IDs of all vertices in each of the parts, $X^{\prime}$,
$Y^{\prime}$, and $Z^{\prime}$, are “shifted” by the same amount, though IDs
in different parts may be “shifted” by different amounts.

The following observations about $\phi^{\prime}_{e,e^{\prime}}$ are easy to
verify.

  * (i)

The ranges of $\phi$ and $\phi^{\prime}_{e,e^{\prime}}$ are disjoint.

  * (ii)

Moreover, $\phi^{\prime}_{e,e^{\prime}}(v)\in[8t+1,14t+1]$ if $v\in
X^{\prime}$, $\phi^{\prime}_{e,e^{\prime}}(v)\in[18t+1,24t+1]$ if $v\in
Y^{\prime}$, and $\phi^{\prime}_{e,e^{\prime}}(v)\in[30t+1,32t+1]$ if $v\in
Z^{\prime}$.

  * (iii)

For any $u,v\in V$, $u\not=v$, $\phi(u)<\phi(v)$ iff
$\phi^{\prime}_{e,e^{\prime}}(u^{\prime})<\phi^{\prime}_{e,e^{\prime}}(v^{\prime})$.

Item (iii) is simply saying that the ID ordering on $V^{\prime}$ induced by
$\phi^{\prime}_{e,e^{\prime}}$ is the same as the ID ordering induced by
$\phi$ with respect to the corresponding vertices in $V$. This follows from
the fact that the ID’s of vertices in $X^{\prime}$ are obtained by shifting
the ID’s of vertices in $X$ by the same amount, thus preserving the relative
ordering of ID’s in $X$ and $X^{\prime}$. Similarly, for vertex sets
$Y^{\prime}$ and $Z^{\prime}$. Furthermore, even though the ID’s of different
sets, $X^{\prime}$, $Y^{\prime}$, and $Z^{\prime}$ are obtained by “shifting”
by different amounts, the “shifting” also ensures that ID’s in $X^{\prime}$
remain less than ID’s in $Y^{\prime}$, which in turn remain less than ID’s in
$Z^{\prime}$.

To prove that $EX$ and $EX_{e,e^{\prime}}$ are similar, we need two
intermediate ID assignments for the set $V\cup V^{\prime}$. Recall that edge
$e=\\{y,z\\}$ and edge $e^{\prime}=\\{x^{\prime},y^{\prime}\\}$.

  * (i)

Define $\psi_{e,e^{\prime},x}$ to be the ID assignment $\psi_{e,e^{\prime}}$
except for interchanging the values of $x^{\prime}$ and $y$ (i.e.
$\psi_{e,e^{\prime},x}(y)=\phi^{\prime}_{e,e^{\prime}}(x^{\prime})$ and
$\psi_{e,e^{\prime},x}(x^{\prime})=\phi(y)$).

  * (ii)

Define $\psi_{e,e^{\prime},z}$ analogously as $\psi_{e,e^{\prime}}$ except for
interchanging the values of $y^{\prime}$ and $z$ (i.e.
$\psi_{e,e^{\prime},z}(z)=\phi^{\prime}_{e,e^{\prime}}(y^{\prime})$ and
$\psi_{e,e^{\prime},z}(y^{\prime})=\phi(z)$).

Using these ID assignments, we define two intermediate executions on the base
graph $G\cup G^{\prime}$.

$EX_{e,e^{\prime},x}=EX(\mathcal{A},G\cup
G^{\prime},\psi_{e,e^{\prime},x});\quad
EX_{e,e^{\prime},z}=EX(\mathcal{A},G\cup G^{\prime},\psi_{e,e^{\prime},z})$

The following lemma, which shows that $EX$, $EX_{e,e^{\prime},x}$, and
$EX_{e,e^{\prime},y}$ are similar, critically uses the fact that the ID
assignment $\psi_{e,e^{\prime}}$ shifts the ID’s of vertices in
$X^{\prime}\cup Y^{\prime}\cup Z^{\prime}$ so that the ID of $x^{\prime}$
becomes “adjacent” to the ID of $y$ and the ID of $y^{\prime}$ becomes
“adjacent” to the ID of $z$.

###### Lemma 2.5.

For any $x\in X$, $y\in Y$, $z\in Z$ and edges $e=\\{y,z\\}$ and
$e^{\prime}=\\{x^{\prime},y^{\prime}\\}$, the executions $EX$,
$EX_{e,e^{\prime},x}$ and $EX_{e,e^{\prime},z}$ are similar.

###### Proof.

All three executions have the same input graph $G\cup G^{\prime}$. The
execution pair $EX$ and $EX_{e,e^{\prime},x}$ have the same ID assignment
except for the vertices $x^{\prime}$ and $y$, which have their ID’s swapped.
Note that by definition of $\psi^{\prime}_{e,e^{\prime}}$ and
$\phi^{\prime}_{e,e^{\prime}}$ in (1), we have

$\psi_{e,e^{\prime}}(x^{\prime})=\phi^{\prime}_{e,e^{\prime}}(x^{\prime})=\phi(x)+(\phi(y)-\phi(x))+1=\phi(y)+1.$

Furthermore, $\psi_{e,e^{\prime}}(y)=\phi(y)$. Therefore, when we swap the
ID’s of $x^{\prime}$ and $y$ in $\psi_{e,e^{\prime}}$ to obtain
$\psi_{e,e^{\prime},x}$, there is no change in the relative ordering of ID’s
and therefore the executions $EX$ and $EX_{e,e^{\prime},x}$ are similar.

A similar argument holds for the execution pair $EX$ and
$EX_{e,e^{\prime},z}$. By the definition of $\psi^{\prime}_{e,e^{\prime}}$ and
$\phi^{\prime}_{e,e^{\prime}}$ in (1), we have

$\psi_{e,e^{\prime}}(y^{\prime})=\phi^{\prime}_{e,e^{\prime}}(y^{\prime})=\phi(y)+(\phi(z)-\phi(y))+1=\phi(z)+1$

and $\psi_{e,e^{\prime}}(z)=\phi(z)$. Thus the relative ordering of ID’s in
$\psi_{e,e^{\prime}}$ and $\psi_{e,e^{\prime},z}$ is the same and therefore
the executions $EX$ and $EX_{e,e^{\prime},x}$ are similar.

The lemma follows because similarity of executions is transitive. ∎

We can derive the final tool we need by directly appealing to a lemma in
Awerbuch et al. (Awerbuch et al., 1988). Informally, the lemma shows that if
edges $e=\\{y,z\\}$ and $\\{x^{\prime},y^{\prime}\\}$ are not utilized in the
execution $EX$ of algorithm $\mathcal{A}$, then executions $EX$ and
$EX_{e,e^{\prime}}$ are similar. The main obstacle is that the initial
knowledge vertices $x^{\prime},y,y^{\prime},z$ is different in $EX$ and
$EX_{e,e^{\prime}}$ so a direct inductive proof like in Lemma 2.5 does not
work. But we can use the intermediate executions of Lemma 2.5 to show the
similarity for these four vertices. For all other vertices, we can do a direct
inductive argument.

###### Lemma 2.6 (Restatement of Lemma 3.8 of (Awerbuch et al., 1988)).

Let $x\in X$, $y\in Y$, and $z\in Z$ be arbitrary vertices and let
$e=\\{y,z\\}$ and $e^{\prime}=\\{x^{\prime},y^{\prime}\\}$. Suppose that
during the first $r$ rounds of the execution $EX$ both $e$ and $e^{\prime}$
are not utilized. Then the following hold for every round $1\leq i\leq r$ of
the executions $EX$, $EX_{e,e^{\prime},x}$ , $EX_{e,e^{\prime},z}$ and
$EX_{e,e^{\prime}}$:

  1. (1)

The states of the nodes in the beginning of the round, i.e.
$L_{i}(\cdot,\cdot)$ satisfy:

    1. (a)

For every processor $w\in V\setminus\\{y,z,y^{\prime},x^{\prime}\\}$,
$L_{i}(EX_{e,e^{\prime}},w)=L_{i}(EX,w)$.

    2. (b)

For $u\in\\{x^{\prime},z\\}$,
$L_{i}(EX_{e,e^{\prime}},u)=L_{i}(EX_{e,e^{\prime},x},u)$.

    3. (c)

For $v\in\\{y,y^{\prime}\\}$,
$L_{i}(EX_{e,e^{\prime}},v)=L_{i}(EX_{e,e^{\prime},z},v)$.

  2. (2)

The messages sent during the round are similar, i.e.,
$h_{i}(EX)=h_{i}(EX_{e,e^{\prime},x})=h_{i}(EX_{e,e^{\prime},z})=h_{i}(EX_{e,e^{\prime}})$.

  3. (3)

In $EX_{e,e^{\prime}}$, no messages are sent during the round over the edges
$\\{x^{\prime},z\\}$ and $\\{y,y^{\prime}\\}$.

###### Corollary 2.7.

Suppose that during the execution $EX$ neither of the edges $e=\\{y,z\\}$ and
$e^{\prime}=\\{x^{\prime},y^{\prime}\\}$ are utilized, for some vertices $x\in
X$, $y\in Y$, and $z\in Z$. Then the executions $EX$ and $EX_{e,e^{\prime}}$
are similar and furthermore in $EX_{e,e^{\prime}}$, no messages are sent
through the edges $\\{y,y^{\prime}\\}$ and $\\{x^{\prime},z\\}$.

In the next subsections, we will show that this similarity leads to a
contradiction with respect to correctness for problems such as
$(\Delta+1)$-coloring and MIS. This in turn will imply a constraint on the
behavior of algorithm $\mathcal{A}$: for every pair of edges $e=\\{y,z\\}$ and
$e^{\prime}=\\{x^{\prime},y^{\prime}\\}$, at least one of the edges is
utilized by $\mathcal{A}$. This in turn will lead to the message complexity
lower bound we desire.

###  2.3. $\Omega(m)$ message lower bound for $(\Delta+1)$-Coloring in KT-$1$
Congest

Now that we have shown that $EX$ and $EX_{e,e^{\prime}}$ are similar if $e$
and $e^{\prime}$ are not utilized by algorithm $\mathcal{A}$, we will show
that for some problems this leads to a contradiction. The intuition for this
is simple. Let $\phi$ and $\phi^{\prime}$ be ID assignments for $V$ and
$V^{\prime}$ respectively, that consistently order the vertices, i.e.,
$\phi(u)<\phi(v)$ iff $\phi^{\prime}(u^{\prime})<\phi^{\prime}(v^{\prime})$
for all $u,v\in V$. Since $G$ and $G^{\prime}$ are isomorphic, it is easy to
show that $EX_{G}=EX(\mathcal{A},G,\phi)$ and
$EX_{G^{\prime}}=EX(\mathcal{A},G^{\prime},\phi^{\prime})$ are similar. This
is shown below in Lemma 2.8 below. Now consider the base graph $G\cup
G^{\prime}$ and the ID assignment $\psi_{e,e^{\prime}}$ of $V\cup V^{\prime}$.
Lemma 2.8 implies that corresponding vertices $v$ and $v^{\prime}$ have the
same local states after execution $EX=EX(\mathcal{A},G\cup
G^{\prime},\psi_{e,e^{\prime}})$ completes. Since $EX$ and
$EX_{e,e^{\prime}}=EX(\mathcal{A},G_{e,e^{\prime}},\psi_{e,e^{\prime}})$ are
similar, this also implies that vertices $v$ and $v^{\prime}$ have the same
local states after execution $EX_{e,e^{\prime}}$. But, in the crossed graph
$G_{e,e^{\prime}}$, $y$ and $y^{\prime}$ are neighbors. For problems in which
neighboring vertices ought not to have the same local state (e.g., neighboring
vertices cannot have the same color in a solution to the vertex coloring
problem), this is a contradiction.

###### Lemma 2.8.

Consider an arbitrary vertex $y\in Y$ and an arbitrary pair of edges
$e=\\{y,z\\}$, $z\in Z$ and $e^{\prime}=\\{x^{\prime},y^{\prime}\\}$,
$x^{\prime}\in X^{\prime}$. For any comparison-based algorithm $\mathcal{A}$
in the KT-1 Congest model, the executions $EX_{G}=EX(\mathcal{A},G,\phi)$ and
$EX_{G^{\prime}}=EX(\mathcal{A},G^{\prime},\phi^{\prime}_{e,e^{\prime}})$ are
similar.

###### Proof.

Since the input graphs $G$ and $G^{\prime}$ are copies of each other, the only
thing that is different between the two executions is the ID assignments.
However, Property (iii) of the ID assignment $\phi^{\prime}_{e,e^{\prime}}$
above implies that every ID comparison by $\mathcal{A}$ on $G$ yields the same
result as the corresponding ID comparison on $G^{\prime}$. Therefore, by an
inductive argument it can be shown that at the beginning of each round, the
state of each vertex $v$ in $G$ is the same as the state of the corresponding
vertex $v^{\prime}$ in $G^{\prime}$ and the messages received by these
vertices are also be the same. This gives us that the executions $EX_{G}$ and
$EX_{G^{\prime}}$ are similar. ∎

###### Lemma 2.9.

Let $x\in X$, $y\in Y$, and $z\in Z$ be three vertices such that the edges
$e=\\{y,z)\\}$ and $e^{\prime}=\\{x^{\prime},y^{\prime}\\}$ are not utilized
in the execution $EX$. Then, algorithm $\mathcal{A}$ computes an incorrect
$(\Delta+1)$-coloring for the crossed graph $G_{e,e^{\prime}}$.

###### Proof.

In the execution $EX$, since the input graph has two disconnected components
$G$ and $G^{\prime}$, Lemma 2.8 gives us that the color of a vertex $v$ in $G$
is the same as the color of the corresponding vertex $v^{\prime}$ in
$G^{\prime}$. Since the edges $e=\\{y,z\\}$ and
$e^{\prime}=\\{x^{\prime},y^{\prime}\\}$ are not utilized in $G\cup
G^{\prime}$, applying Corollary 2.7, $\mathcal{A}$ will compute the same
coloring in the graph $G_{e,e^{\prime}}$ as it will in $G\cup G^{\prime}$.
This implies a monochromatic edge $\\{y,y^{\prime}\\}$ in $G_{e,e^{\prime}}$
which contradicts the correctness of the algorithm. ∎

###### Theorem 2.10 (Deterministic Lower Bound).

Let $\mathcal{A}$ be a deterministic comparison-based algorithm that computes
a $(\Delta+1)$-coloring. Then the message complexity of $\mathcal{A}$ is
$\Omega(n^{2})$. This holds even if the vertices know the size of the network.

###### Proof.

Suppose that $\mathcal{A}$ is a deterministic comparison-based algorithm that
computes a $(\Delta+1)$-coloring and has message complexity $o(n^{2})$. Then
by Lemma 2.4, the number of edges utilized by $\mathcal{A}$ is $o(n^{2})$.
This implies that there exists a $y\in Y$ and edges $e=\\{y,z\\}$ and
$e^{\prime}=\\{x^{\prime},y^{\prime}\\}$ such that $e$ and $e^{\prime}$ are
not utilized when $\mathcal{A}$ executes on $G\cup G^{\prime}$. By Lemma 2.9
this implies that $\mathcal{A}$ computes an incorrect $(\Delta+1)$-coloring
for $G_{e,e^{\prime}}$. ∎

We now extend this lower bound to Monte Carlo randomized algorithms, even with
constant error probability. To do this we strengthen Lemma 2.9 so that it
applies not just to a single crossed graph, but to the entire family of
crossed graphs. Let $\mathcal{F}$ denote the family of all crossed graphs,
i.e., $\mathcal{F}=\\{G_{e,e^{\prime}}\mid
e=\\{y,z\\},e^{\prime}=\\{x^{\prime},y^{\prime}\\},x,y,z,\in V\\}$. Note that
$|\mathcal{F}|=t^{3}$ because there are $t$ choices for $y$ and for each
choice of $y$, there are $t^{2}$ choices for $e$ and $e^{\prime}$.

###### Lemma 2.11.

Let $\mathcal{A}$ be a deterministic comparison-based KT-$1$ Congest algorithm
that computes a $(\Delta+1)$-coloring correctly on at least a constant
$\delta$ fraction of graphs in the family $\mathcal{F}$. Then the message
complexity of $\mathcal{A}$ is $\Omega(\delta n^{2})$. This holds even if the
vertices know the size of the network.

###### Proof.

Assume for the sake of contradiction that the message complexity of
$\mathcal{A}$ is $o(\delta n^{2})$. By Lemma 2.4, we have that $\mathcal{A}$
utilizes $o(\delta n^{2})$ edges in any graph that it runs on. Specifically
consider the execution $EX$ of algorithm $\mathcal{A}$ on input graph $G\cup
G^{\prime}$ and ID assignment $\psi_{e,e^{\prime}}$ where $e,e^{\prime}$
denote a graph $G_{e,e^{\prime}}$ in the family $\mathcal{F}$.

Since $\mathcal{A}$ utilizes $o(\delta n^{2})$ edges, there can only be
$o(n)=o(t)$ vertices in $Y$ such that more than $cn/6=ct$ incident edges are
utilized, for some constant $c$ to be determined later. Recall that $t=n/6$.
The rest of the $t-o(t)$ vertices in $Y$ have less than $ct$ incident edges
that are utilized. By Lemma 2.8 the same statement holds for the corresponding
vertices in $Y^{\prime}$ because in $EX$, the two graphs $G$ and $G^{\prime}$
that form the input graph are disconnected, which implies the executions of
$\mathcal{A}$ on $G$ and $G^{\prime}$ are similar.

So for each such vertex $y\in Y$, there are at most $(c^{2}/4)t^{2}$ edge
pairs of the form $e=\\{y,z\\},e^{\prime}=\\{x^{\prime},y^{\prime}\\}$ such
that $e,e^{\prime}$ are utilized. Therefore, by Lemma 2.9, the algorithm
computes an incorrect $(\Delta+1)$-coloring on at least
$(1-o(1))(1-(c^{2}/4))=1-(c^{2}/4)-o(1)$-fraction of the graphs in
$\mathcal{F}$ (since for each $y\in Y$ there are exactly $t^{2}$ graphs in
$\mathcal{F}$). Setting $c=\sqrt{2\delta}$, the algorithm computes an
incorrect $(\Delta+1)$-coloring on at least $1-\delta/2-o(1)$-fraction of the
graphs in $\mathcal{F}$. This is a contradiction if $1-\delta<1-\delta/2-o(1)$
or $\delta>o(1)$. Since $\delta$ is a constant, we get a contradiction. ∎

A simple application of Yao’s lemma (Yao, 1977; Motwani and Raghavan, 1995)
with the uniform distribution on all the graphs in the family $\mathcal{F}$
gives the following theorem.

###### Theorem 2.12 (Randomized Lower Bound).

Let $\mathcal{A}$ be a randomized Monte-Carlo comparison based KT-$1$ Congest
algorithm that computes a $(\Delta+1)$-coloring with probability of error less
than a constant $\epsilon\in[0,1)$. Then the worst case message complexity of
$\mathcal{A}$ is $\Omega((1-\epsilon)n^{2})$. This holds even if the vertices
know the size of the network.

###  2.4. $\Omega(m)$ message lower bound for MIS in KT-$1$ Congest

###### Lemma 2.13.

Let $x\in X$, $y\in Y$, and $z\in Z$ be three vertices such that the edges
$e=\\{y,z\\}$ and $e^{\prime}=\\{x^{\prime},y^{\prime}\\}$ are not utilized in
the execution $EX$. Then, algorithm $\mathcal{A}$ computes an incorrect MIS on
$G_{e,e^{\prime}}$.

###### Proof.

Due to Lemma 2.8, we can only have two MIS’s in $G\cup G^{\prime}$ which are:
$Y,Y^{\prime}$ or $X,X^{\prime},Z,Z^{\prime}$. Since the edges $e=\\{y,z\\}$
and $e^{\prime}=\\{x^{\prime},y^{\prime}\\}$ are not utilized in $G\cup
G^{\prime}$, applying Corollary 2.7, $\mathcal{A}$ will compute the same MIS
in the graph $G_{e,e^{\prime}}$ as it will in $G\cup G^{\prime}$. Both the MIS
solutions mentioned above violate the independence requirement of MIS in
$G_{e,e^{\prime}}$. This contradicts the correctness of the algorithm. ∎

A similar proof as the coloring deterministic lower bound gives us the
following theorem.

###### Theorem 2.14 (Deterministic Lower Bound).

Let $\mathcal{A}$ be a deterministic comparison-based KT-$1$ Congest algorithm
that solves the MIS problem. Then the message complexity of $\mathcal{A}$ is
$\Omega(n^{2})$. This holds even if the vertices know the size of the network.

The following lemma for MIS parallels Lemma 2.11 for $(\Delta+1)$-coloring.
This has a very similar proof, which we skip.

###### Lemma 2.15.

Let $\mathcal{A}$ be a deterministic comparison-based KT-$1$ Congest algorithm
that computes an MIS correctly on at least a constant $\delta$ fraction of
graphs in the family $\mathcal{F}$. Then the message complexity of
$\mathcal{A}$ is $\Omega(\delta n^{2})$. This holds even if the vertices know
the size of the network.

A simple application of Yao’s lemma (Yao, 1977; Motwani and Raghavan, 1995)
with the uniform distribution on all the graphs in the family. $\mathcal{F}$
gives the following theorem.

###### Theorem 2.16 (Randomized Lower Bound).

Let $\mathcal{A}$ be a randomized Monte-Carlo comparison-based KT-$1$ Congest
algorithm that computes an MIS with probability of error less than a constant
$\epsilon\in[0,1)$. Then the worst case message complexity of $\mathcal{A}$ is
$\Omega((1-\epsilon)n^{2})$. This holds even if the vertices know the size of
the network.

###  2.5. $\Omega(n)$ message lower bound in KT-$\rho$ Congest

The $\Omega(m)$ lower bounds we have proved apply to comparison-based
algorithms in the KT-$1$ Congest model. We now prove a weaker $\Omega(n)$
message complexity bound for $(\Delta+1)$-coloring and MIS, but these apply
more generally, to all algorithms (even non-comparison-based) and to the
KT-$\rho$ Congest model, for any constant $\rho$.

###### Theorem 2.17.

Any randomized Monte Carlo algorithm that computes an MIS or a
$(\Delta+1)$-vertex coloring with probability at least $\tfrac{5}{8}$,
requires $\Omega(n)$ messages in expectation in the KT-$\rho$ Congest model,
for any constant $\rho$.

###### Proof.

Similarly to (Naor, 1991; Linial, 1992), we assume without loss of generality
that algorithms follow the general framework that all nodes perform their coin
flips initially and only exchange their current local state (including coin
flips) without performing any other local computation until the very last
round.

For the given constant $\rho$, define the constant $k$ to be the smallest
integer such that

$\log^{*}(k)\geq 2(\rho+3).$

Consider an $n$-node graph $G$ consisting of the disjoint union of $n/k$
cycles each of $k$ nodes.666For simplicity, we assume that $n/k$ is an
integer. For each cycle $C_{i}$, we fix a set of IDs $R_{i}$ from some integer
range of size $k$ such that all ID ranges assigned to the cycles are pairwise
disjoint. We will equip the nodes of each cycle $C_{i}$ with $k$ unique IDs,
as described below.

Consider any randomized algorithm $B_{0}$ that works on a cycle. We know from
(Naor, 1991) that any randomized algorithm that succeeds in computing a
$3$-coloring on cycle $C_{i}$ with probability more than $\tfrac{1}{2}$
requires at least $\tfrac{1}{2}\log^{*}(k)-2$ rounds in the worst case, under
the KT-$0$ assumption. Now suppose that we execute $B_{0}$ on our lower bound
graph $G$ for at most $\rho<\tfrac{1}{2}\log^{*}(k)-2$ rounds under the KT-$0$
assumption. Even though $B_{0}$ is not guaranteed to work on $G$, it
nevertheless exhibits some well-defined behavior on each cycle that we will
exploit. Observe that each node $u$ in $G$ is part of some cycle $C_{i}$ and
hence the color output by $u$ is a function of the observed neighborhood and
the random coin flips. We point out that, even though that $u$ also has
knowledge of $n$, it is easy to see that this does not have any impact on the
output of the algorithm. As a straightforward consequence of (Naor, 1991), we
know that, for each cycle $C_{i}$, there exists some _hard ID assignment_
$I_{i}$, which is a permutation of the set $R_{i}$, such that $B_{0}$ fails to
yield a valid coloring on $C_{i}$ with some probability greater than
$\tfrac{1}{2}$ (assuming KT-$0$), where this probability is taken over the
coin flips of the nodes in $C_{i}$.

Returning to the KT-$\rho$ assumption, suppose towards a contradiction that
there exists an algorithm $B_{\rho}$ that computes a $3$-coloring on $G$ while
sending $o(n)$ messages in expectation. We provide additional power to the
algorithm by revealing, to each node $u$, the coin flips of the nodes in its
$\rho$-neighborhood.

We assign the IDs of the nodes in each cycle $C_{i}$ according to $I_{i}$.
Since there are $n/k=\Omega(n)$ cycles but the expected message complexity of
$B_{\rho}$ is $o(n)$, it holds that, with probability at least $\tfrac{3}{4}$,
there exists a cycle $C_{j}$ such that the nodes in $C_{j}$ do not send any
messages at all when executing $B_{\rho}$; call this event Mute. We now
condition on Mute occurring: Consider any node $u\in C_{j}$ and observe that
the output of $u$ is a function of its initial knowledge, i.e., its random
coin flips and the local state of its $\rho$-neighborhood. Clearly, the
behavior of $u$ follows the exact same probability distribution when executing
$B_{\rho}$ under the KT-$\rho$ assumption as it does when executing algorithm
$B_{0}$ under the KT-$0$ assumption. In particular, the result of (Naor, 1991)
implies that some neighboring nodes in $C_{j}$ will output the same color with
probability greater than $\tfrac{1}{2}$. Since event Mute occurs with
probability at least $\tfrac{3}{4}$, it follows that algorithm $B_{\rho}$
fails with probability $>\tfrac{3}{8}$, yielding a contradiction. ∎

##  3\. Upper bounds in KT-1 Congest

###  3.1. $(\Delta+1)$-Coloring using $\tilde{O}(n^{1.5})$ Messages in KT-1
Congest

In this section we present a $(\Delta+1)$-list-coloring algorithm in the KT-1
Congest model that uses $\tilde{O}(n^{1.5})$ messages. This algorithm is
obtained by utilizing – with some modifications – the simple graph
partitioning technique introduced recently by Chang et al. (Chang et al.,
2019). This technique is central to the fast $(\Delta+1)$-coloring algorithms
that Chang et al. (Chang et al., 2019) obtain in different models of
computation, namely Congested Clique, MPC, and Centralized Local Computation.

The Chang et al. (Chang et al., 2019) graph partitioning scheme is as follows.
Let $\Psi(v)$ denote the palette of vertex $v\in V$ and let $k=\sqrt{\Delta}$.

  * •

Vertex set partition: We partition $V$ into $B_{1},\dots,B_{k},L$ as follows.
Include each $v\in V$ in the set $L$ with probability
$q=\Theta\left(\frac{\sqrt{\log n}}{\Delta^{1/4}}\right)$. Then each remaining
vertex joins one of $B_{1},\ldots,B_{k}$ uniformly at random.

  * •

Palette partition: Let $C=\bigcup_{v\in V}\Psi(v)$ be the set of all colors.
We partition $C$ into $k$ sets $C_{1},\dots,C_{k}$ where each color $c\in C$
joins one of the $k$ sets uniformly at random.

Chang et al. (Chang et al., 2019) then show that whp, the output of the
partitioning scheme satisfies the following 4 properties, assuming that
$\Delta=\omega(\log^{2}n)$. These properties allow us to color each set
$B_{i}$ using palette $C_{i}$, in parallel, and then recursively color the set
$L$ until it becomes small enough to color trivially.

(i) Size of Each Part::

$|E(G[B_{i}])|=O(|V|)$, for each $i\in[k]$. Also,
$|L|=O(q|V|)=O\left(\frac{\sqrt{\log n}}{\Delta^{1/4}}\right)\cdot|V|$.

(ii) Available Colors in $B_{i}$::

For each $i\in\\{1,\ldots,k\\}$ and $v\in B_{i}$, let the number of available
colors in $v$ in the subgraph $B_{i}$ be $g_{i}(v):=|\Psi(v)\cap C_{i}|$. Then
$g_{i}(v)\geq\Delta_{i}+1$, where $\Delta_{i}:=\max_{v\in
B_{i}}\deg_{B_{i}}(v)$.

(iii) Available Colors in $L$::

For each $v\in L$, define $g_{L}(v):=|\Psi(v)|-(\deg_{G}(v)-\deg_{L}(v))$. It
is required that
$g_{L}(v)\geq\max\\{\deg_{L}(v),\Delta_{L}-\Delta_{L}^{3/4}\\}+1$ for each
$v\in L$, where $\Delta_{L}:=\max_{v\in L}\deg_{L}(v)$. Note that $g_{L}(v)$
represents a lower bound on the number of available colors in $v$’s palette
after  all of $B_{1},\ldots,B_{k}$ have been colored.

(iv) Remaining Degrees::

The maximum degrees of $B_{i}$ and $L$ are
$\deg_{B_{i}}(v)\leq\Delta_{i}=O(\sqrt{\Delta})$ and
$\deg_{L}(v)\leq\Delta_{L}=O(q\Delta)=O\left(\frac{\sqrt{\log
n}}{\Delta^{1/4}}\right)\cdot\Delta$. For each vertex, we have that
$\deg_{B_{i}}(v)\leq\max\\{O(\log n),O(1/\sqrt{\Delta})\cdot\deg(v)\\}$ and
also have $\deg_{L}(v)\leq\max\\{O(\log n),O(q)\cdot\deg(v)\\}$.

We now present our algorithm, which takes as input an $n$-vertex graph $G$
with maximum degree $\Delta$ and diameter $D$. The algorithm runs in the KT-1
Congest model and produces a $(\Delta+1)$-list-coloring of $G$ using
$\tilde{O}(n^{1.5})$ messages and running in $\tilde{O}(D+\sqrt{n})$ rounds.

1For $\delta=1/2$, build a danner $H$, elect a leader $\ell$, and have the
leader broadcast a string $R$ of $O(\log^{2}n)$ random bits.

2 Nodes use the $O(\log^{2}n)$ bits of $R$ to sample three $O(\log n)$-wise
independent hash functions: (a) $h_{L}$, to decide whether to join $L$, (b)
$h$, to decide which set $B_{i}$ to join, and (c) $h_{c}$, to determine which
color goes into which part $C_{i}$.

3 Nodes execute a randomized algorithm for list coloring by Johansson (Öjvind
Johansson, 1999) in each $B_{i}$ in parallel.

4 Using the danner $H$, we can check whether the induced graph $G[L]$ has
$\tilde{O}(n)$ edges.

5 If it does, we execute the list coloring algorithm by Johansson (Öjvind
Johansson, 1999) on $G[L]$.

If not, we recursively run this algorithm on $G[L]$ with the same parameter
$n$.

Algorithm 1 KT-$1$ $(\Delta+1)$-Coloring Algorithm:

The “full independence” version of the following lemma is proved in (Chang et
al., 2019). We provide a brief sketch of the changes required in this proof to
make a version with limited independence go through.

###### Lemma 3.1.

Properties (i)-(iv) mentioned above hold w.h.p., even when the partitioning of
vertices and colors is done using $O(\log n)$-wise independence, as described
in Line 2 of Algorithm 1.

###### Proof.

Chang et al. (Chang et al., 2019) show that this lemma holds when the vertex
partitioning is done using full independence, while the color partitioning is
done using $O(\log n)$-wise independence. A closer look at their proof reveals
that all four properties are shown using Chernoff bounds, and these bounds can
be safely replaced by limited dependence Chernoff bounds described in Lemma
A.2. Therefore the four properties hold whp even when the partitioning of both
vertices and colors is done using $O(\log n)$-wise independence. ∎

The following lemma is proved in (Chang et al., 2019) and given that
Properties (i)-(iv) hold in the limited independence setting we use, it goes
through without any changes.

###### Lemma 3.2.

The algorithm makes $O(1)$ recursive calls w.h.p.

###### Theorem 3.3.

Given as input an $n$-vertex graph $G$ with maximum degree $\Delta$ and
diameter $D$, Algorithm 1 runs in the KT-1 Congest model and produces a
$(\Delta+1)$-list-coloring of $G$ using $\tilde{O}(n^{1.5})$ messages and
running in $\tilde{O}(D+\sqrt{n})$ rounds.

###### Proof.

In Step 1, we create a danner with the parameter $\delta=1/2$, building the
danner takes $\tilde{O}(\sqrt{n})$ rounds and $\tilde{O}(n^{1.5})$ messages,
see Lemma 1.1. Also, because of danner property, the diameter of the danner is
$\tilde{O}(D+\sqrt{n})$ and hence electing a leader and broadcasting a
$\log^{2}n$-bit random string takes $\tilde{O}(D+\sqrt{n})$ rounds and
$\tilde{O}(n^{1.5})$ messages (Corollary 1.2). Step 2 is just local
computation.

In step 3 we use Johansson’s randomized algorithm on each $G[B_{i}]$. This
algorithm works in $O(\log n)$ rounds and $\tilde{O}(|E(G[B_{i}])|)$ messages
whp even when the palette of each vertex $v$ has been initialized to an
arbitrary subset of $\deg(v)+1$ colors chosen from $\\{1,2,\dots,\Delta+1\\}$
(Öjvind Johansson, 1999). According to Property (ii), the palettes of vertices
in each $B_{i}$ are large enough. And according to property (i),
$|E(G[B_{i}])|=|V|$ So this step runs in $O(\log n)$ rounds and takes
$\tilde{O}(n\sqrt{\Delta})$ messages over all the $B_{i}$’s whp, since there
are $O(\sqrt{\Delta})$ $B_{i}$’s.

Step 4 takes $\tilde{O}(D+\sqrt{n})$ rounds and $\tilde{O}(n^{1.5})$ messages
by Corollary 1.2. Using Lemma 3.2 and the above arguments guarantee that steps
5 and 6 together take $\tilde{O}(D+\sqrt{n})$ rounds and $\tilde{O}(n^{1.5})$
messages whp. The theorem follows. ∎

####  3.1.1. Asynchronous KT-1 Congest algorithm

The $(\Delta+1)$-coloring in the Congest KT-1 mode described above (Algorithm
1) has a natural counterpart in the asynchronous version of the Congest KT-1
model. The broadcast of random bits in Step 1 can be done asynchronously using
$\tilde{O}(n^{1.5})$ messages and in $O(n)$ rounds by appealing to the result
of Mashregi and King (Mashreghi and King, 2019, 2018) (see Theorem 1.3). Every
node, on receiving the random bits that were broadcast, completes Step 2 via
local computation. Due to shared randomness, each node $v\in B_{i}$, for each
$i\in[k]$, knows which of its neighbors are in $B_{i}$. The coloring algorithm
in Step 3 therefore can be executed by nodes in $B_{i}$ by communicating just
over the edges in the induced graph $G[B_{i}]$. The synchronous algorithm used
in Step 3 in Algorithm 1 can be simulated by using an $\alpha$-synchronizer
(Awerbuch, 1985) (see Theorem A.5) in an asynchronous setting. This takes
$\tilde{O}(n)$ messages since (i) according to Lemma 3.1, $G[B_{i}]$ contains
$O(n)$ edges and (ii) Step 3 runs in $O(\log n)$ rounds. Checking if $G[L]$
has $\tilde{O}(n)$ edges (Step 4) can be done via asynchronous upcast, using
$\tilde{O}(n)$ messages and in $O(n)$ rounds. This is possible because each
node $v\in L$, knows which of its neighbors are in $L$ and can therefore send
the size of its $L$-restricted neighborhood up the spanning tree. Like Step 3,
Step 5 can also be executed using $O(n)$ messages, in $O(\log n)$ rounds. This
description leads to the following theorem.

###### Theorem 3.4.

Given as input an $n$-vertex graph $G$ with maximum degree $\Delta$, there is
an algorithm that runs in the asynchronous KT-1 Congest model and produces a
$(\Delta+1)$-list-coloring of $G$ using $\tilde{O}(n^{1.5})$ messages and
running in $\tilde{O}(n)$ rounds.

###  3.2. $(1+\epsilon)\Delta$-Coloring using $\tilde{O}(n)$ Messages in KT-1
Congest

In this section, we show that for any $\epsilon>0$, there is an algorithm that
can compute a $(1+\epsilon)\Delta$-coloring in the KT-1 Congest model in
$\tilde{O}(n)$ rounds, using $\tilde{O}(n/\epsilon^{2})$ messages.

At the beginning of the algorithm, for a large enough constant $C$, one node
generates $(C/\epsilon)\cdot\log^{3}n$ random bits and shares it with all
other nodes using a danner (Gmyr and Pandurangan, 2018), using
$\tilde{O}(n/\epsilon)$ messages and $\tilde{O}(n)$ rounds in the KT-1 Congest
model (cf. Corollary 1.2). In the following algorithm, each node $v$ that has
not already permanently colored itself, will use random bit string $s_{i}$ in
Phase $i$ to first select a random hash function $h_{i}$ from a family of
$\Theta(\log n)$-wise independent hash functions
$\mathcal{H}=\\{h:[\text{poly}(n)]\to[(1+\epsilon)\Delta]\\}$. Node $v$ will
then compute $h_{i}(\texttt{ID}_{v})$ to pick a random color from the palette
$[(1+\epsilon)\Delta]$. Note that the length of $s_{i}$ is $\Theta(\log^{2}n)$
and by Lemma A.4, this number of random bits suffice to pick a $\Theta(\log
n)$-wise independent hash function with domain size $\text{poly}(n)$ and range
size $(1+\epsilon)\Delta$. In Corollary 3.6, it is shown that Algorithm 2 runs
in $O(\log n/\epsilon)$ phases and therefore $r=\Theta(\log n/\epsilon)$
random bit strings suffice.

1Each active node (i.e., which has not been colored yet) chooses a random
candidate color from $(1+\varepsilon)\Delta$ color palette.

2

3It makes this color permanent if it is sure that none of its neighbors has
chosen this color yet.

4

If unsuccessful in choosing a permanent color, go to step 1.

Algorithm 2 $(1+\epsilon)\Delta$-Coloring Algorithm (One phase):

In step 2, we will show that a node has to check only a small subset of its
neighbors in any phase.

First, we will show that the probability of success in each phase is large.

###### Lemma 3.5.

In any phase, a node chooses a color that has not been chosen by any of its
neighbors in this phase or in any previous phases with probability at least
$\varepsilon/(1+\varepsilon)\approx\varepsilon$ (for small $\varepsilon$).
Hence there will be no conflict with the chosen color and hence the node will
successfully color itself. Thus, a node successfully colors itself in $O(\log
n/\varepsilon)$ rounds whp.

###### Proof.

Fix a node $v$ and suppose that it has degree $d$. Arbitrarily label the
neighbors of $v$, $v_{1},v_{2},\ldots,v_{d}$ and let $X_{i}$ be the indicator
variable that indicates if neighbor $v_{i}$ has picked same color as $v$. Let
$X=\sum_{i=1}^{d}X_{i}$. Then $\text{Pr}[X_{i}=1]=1/(1+\epsilon)\Delta$ and
$\mathbb{E}[X]\leq d/(1+\epsilon)\Delta\leq 1/(1+\epsilon)$. Then, by Markov’s
inequality, $\text{Pr}[X\geq 1]\leq 1/(1+\epsilon)$. Therefore,
$\text{Pr}[X=0]\geq\epsilon/(1+\epsilon)\approx\varepsilon$, (for small
$\varepsilon>0$). Since $X=0$ represents the event that no neighbor of $v$
chooses the color $v$ picked, we get the first part of the lemma.

Thus after $(c\log n)/\varepsilon$ rounds for a large enough constant $c$, $v$
will successfully color itself whp. ∎

###### Corollary 3.6.

Whp, all nodes successfully color themselves in $O(\log n/\varepsilon)$
rounds.

###### Proof.

By Lemma 3.5 and union bound over all nodes. ∎

Implementing step 2 with small message complexity:

###### Lemma 3.7.

In each phase, each node exchanges at most $O(\log^{2}n/\varepsilon)$ messages
whp.

###### Proof.

In Step 2, a node will check to see if the color chosen by itself is not
chosen by any of its neighbors. To check this, it will only check neighbors
that could have chosen this color in this round or in any previous rounds. Fix
a node $v$ and let $c$ be the color it samples in this round. Arbitrarily
label the neighbors of $v$, $v_{1},v_{2},\ldots,v_{d}$ and let $X_{i}$ be the
indicator variable that indicates if neighbor $v_{i}$ has picked same color as
$v$ in this round. Let $X=\sum_{i=1}^{d}X_{i}$. Then
$\text{Pr}[X_{i}=1]=1/(1+\epsilon)\Delta$ and $\mathbb{E}[X]\leq
d/(1+\epsilon)\Delta\leq 1/(1+\epsilon)$. Since the colors of vertices are
chosen using an $\Theta(\log n)$-wise independent family of hash functions,
the variables $X_{1},X_{2},\ldots,X_{d}$ are $\Theta(\log n)$-wise
independent. Then, by Lemma A.2, for a sufficiently large constant $A$,
$\text{Pr}[X\geq A\cdot\log n]\leq\exp(-2\log n)=1/n^{2}$. Therefore, whp
there are at most $O(\log n)$ neighbors of $v$ that could have picked color
$c$ in this round.

This is true of color $c$ in previous rounds as well. Node $v$ has to check
all these neighbors which have chosen $c$ in this round or prior rounds to be
sure that there is no conflict in choosing $c$. Since there are at most
$O(\log n/\varepsilon)$ phases whp (by Lemma 3.5), color $c$ is chosen by only
$O(\log n\log n/\varepsilon)=O(\log^{2}n/\varepsilon)$ neighbors whp. ∎

###### Theorem 3.8.

There is a coloring algorithm that achieves $(1+\varepsilon)\Delta$ coloring
using $O(n\log^{3}n/\varepsilon^{2})$ messages whp in KT1 model (with shared
randomness).

###### Proof.

By Lemma 3.5, all nodes can legally color themselves in $O(\log
n/\varepsilon)$ rounds whp. By Lemma 2, each node exchanges
$O(\log^{2}n/\varepsilon)$ messages in a phase and there are at most $O(\log
n/\varepsilon)$ phases. Hence the overall message complexity (of all nodes) is
$O(n\log^{3}n/\varepsilon^{2})$ whp. ∎

##  4\. An MIS algorithm using $\tilde{O}(n^{1.5})$ messages in KT-$2$ Congest

We now give a high-level overview of Algorithm 3 that uses KT-$2$ knowledge to
compute an MIS using only $O(n^{1.5}\log^{2}n)$ messages while taking
$\tilde{O}(\sqrt{n})$ rounds; the full details are explained in the proof of
Theorem 4.1. We first sample a set $S$ of $\Theta(\sqrt{n})$ nodes and then
add these nodes to the independent set according to the randomized greedy MIS
algorithm. Since $S$ was chosen randomly, this has the same effect as
performing $\Theta(\sqrt{n})$ iterations of the sequential randomized greedy
algorithm, which is known to reduce the maximum degree in the remnant graph to
$\tilde{O}(\sqrt{n})$ (see (Konrad, 2018)). Then, each node $u\in S$ that
entered the independent set informs its 2-hop neighbors. It is crucial that
node $u$ uses its KT-$2$ knowledge to convey this information, as otherwise
the same 2-hop neighbor $v$ might receive $u$’s message from multiple 1-hop
neighbors of $u$, which may result in $\omega(n)$ messages being sent on
behalf of $u$. Finally, we compute an MIS on the (sparsified) remnant graph
using Luby’s algorithm.

1

2Sample $O(\sqrt{n})$ vertices: Add each node to a set $S$ with probability
$c/\sqrt{n}$.

3

4Run Randomized Greedy MIS: Each node in $S$ chooses a random rank at the
start of the algorithm. In the parallel version of Greedy, a node enters the
MIS as soon as it is a local maximum among undecided neighbors in $S$.

5Inform $2$-hop Neighbors: Each node $u\in S$ that enters the MIS $u$ uses
KT-2 knowledge to inform all of its 2-hop neighbors that it has joined the
MIS.

6Pruning Inactive Edges: Each node $v\in V$ uses its own KT-$2$ knowledge to
either deactivate itself if a $1$-hop neighbor has joined the MIS or
deactivate edges incident on the $1$-hop neighbors that are neighbors with a
node that joins the MIS.

7

Finishing Up: All nodes in the remnant graph know which of their neighbors are
deactivated and so we can run Luby’s algorithm on the remnant graph.

Algorithm 3 MIS Algorithm

###### Theorem 4.1.

Algorithm 3 computes a correct MIS. It uses $O(n^{1.5}\log^{2}n)$ messages and
runs in $\tilde{O}(\sqrt{n})$ rounds with high probability.

###### Proof.

In the first two steps, we aim to simulate $O(\sqrt{n})$ iterations of the
sequential randomized greedy algorithm, see Algorithm 2 in (Blelloch et al.,
2012). In the randomized greedy MIS algorithm, each node chooses a random rank
at the start of the algorithm and we process the nodes by rank to compute an
MIS using the greedy algorithm. Simulating $i$ iterations of this algorithm is
probabilistically equivalent to sampling $i$ vertices uniformly at random and
generating random ranks at just tho sampled vertices. Note that since we
sample vertices uniformly at random with probability $c/\sqrt{n}$, we get
$|S|=O(\sqrt{n})$ whp.

We instead run the parallel randomized greedy MIS algorithm which computes the
same MIS as the sequential version (see (Blelloch et al., 2012)), and in
(Fischer and Noever, 2018), they show that the parallel randomized greedy MIS
algorithm finishes in $O(\log n)$ rounds whp, and so the message complexity of
steps will just be $O(|S|n\log n)=O(n^{1.5}\log n)$ whp.

Using KT-2 information, each vertex in $u\in S$ that joins the MIS locally
creates a depth $2$ BFS tree on its $2$-hop neighborhood and sends the message
through this tree. This BFS tree is constructed by having all $1$-hop
neighbors of $u$ at depth $1$ and assigning a node $v$ that is exactly
$2$-hops away as a child to the $1$-hop neighbor with lowest ID. The local
view of this BFS tree can be created at all $1$-hop neighbors of $u$ using
their own KT-2 information since the common $1$-hop neighbors of $u$ and $v$
are all $2$-hops away.

To send the message to $1$-hop neighbors, $u$ can just broadcast. The one hop
neighbors will just inform their neighbors in the BFS tree that $u$ has joined
the MIS. In case a node $w$ gets multiple messages of $1$-hop neighbors in $S$
joining the MIS and their BFS trees lead to the same $2$-hop vertex $v$, then
$w$ will just send all these messages one by one to $v$. The congestion on
such an edge can be at most $|S|$ in the worst case. This allows each such
node $v$ to prune the inactive edges and learn the edges of the remnant graph
that are incident on it without sending or receiving any additional messages.

Since $|S|=O(\sqrt{n})$ whp, and each vertex in $S$ that joins the MIS can
relay this information to it’s 2-hop neighbors using constant messages per
neighbor, this process generates at most $O(|S|n)=O(n^{1.5}\log n)$ messages
whp. But due to congestion, this process will take $O(\sqrt{n})$ whp in the
worst case.

After the simulation, we know from Lemma 1 in (Konrad, 2018) that the remnant
graph has maximum degree $O(n\log n/|S|)=O(\sqrt{n}\log n)$. And since the
nodes know the remnant graph, running Luby’s algorithm (Luby, 1985) will
require an additional $O(\log n)$ rounds and $O(n^{1.5}\log^{2}n)$ messages
whp.

Therefore, Algorithm 3 runs in $O(\sqrt{n})$ rounds and uses
$O(n^{1.5}\log^{2}n)$ messages throughout its execution whp. The theorem
follows. ∎

##  5\. Conclusion

In this paper, we initiate the study of the message complexity of two
fundamental symmetry breaking problems, MIS and $(\Delta+1)$-coloring. We show
that while it is impossible to obtain $o(m)$ message complexity in the KT-$1$
Congest model using comparison-based algorithms, one can do so by either using
non-comparison based algorithms or by slightly increasing the input knowledge,
i.e., in the KT-$2$ Congest model.

Several key open questions arise from our work. The first is whether one can
obtain an $o(m)$-message, non-comparison-based algorithm for MIS in the KT-$1$
Congest model, running in polynomial time. We have shown that this is possible
for $(\Delta+1)$-coloring. The second is whether one can obtain (nearly
optimal) $\tilde{O}(n)$-message (non-comparison-based) algorithms for MIS and
$(\Delta+1)$-coloring in the KT-$1$ Congest model, running in polynomial time.
The question is open for MIS even in the KT-$2$ Congest model. Another
important issue is reducing the running time of our algorithms. In particular,
can we make them run in $\operatorname{polylog}{n}$ rounds, for the same
message bounds?

## References

  * (1)
  * Awerbuch (1985) Baruch Awerbuch. 1985\.  Complexity of Network Synchronization.  J. ACM 32, 4 (Oct. 1985), 804–823.  https://doi.org/10.1145/4221.4227
  * Awerbuch et al. (1988) Baruch Awerbuch, Oded Goldreich, David Peleg, and Ronen Vainish. 1988.  A Tradeoff between Information and Communication in Broadcast Protocols.  319 LNCS, 2 (1988), 369–379.  https://doi.org/10.1007/BFb0040404
  * Barenboim and Elkin (2013) Leonid Barenboim and Michael Elkin. 2013.  Distributed Graph Coloring: Fundamentals and Recent Developments.  Morgan & Claypool Publishers.
  * Barenboim et al. (2012) Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. 2012.  The Locality of Distributed Symmetry Breaking. In Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS ’12). IEEE Computer Society, USA, 321–330.  https://doi.org/10.1109/FOCS.2012.60
  * Blelloch et al. (2012) Guy E. Blelloch, Jeremy T. Fineman, and Julian Shun. 2012\.  Greedy sequential maximal independent set and matching are parallel on average. In 24th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’12, Pittsburgh, PA, USA, June 25-27, 2012. 308–317.  https://doi.org/10.1145/2312005.2312058
  * Chang et al. (2018) Yi-Jun Chang, Wenzheng Li, and Seth Pettie. 2018.  An optimal distributed ($\Delta$+1)-coloring algorithm?. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018. 445–456.
  * Chang et al. (2019) Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng. 2019.  The Complexity of $(\Delta+1)$ Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC ’19). Association for Computing Machinery, New York, NY, USA, 471–480.  https://doi.org/10.1145/3293611.3331607
  * Cole and Vishkin (1986) R Cole and U Vishkin. 1986\.  Deterministic Coin Tossing and Accelerating Cascades: Micro and Macro Techniques for Designing Parallel Algorithms. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (STOC ’86). Association for Computing Machinery, New York, NY, USA, 206–219.  https://doi.org/10.1145/12130.12151
  * Czumaj et al. (2020) Artur Czumaj, Peter Davies, and Merav Parter. 2020\.  Simple, Deterministic, Constant-Round Coloring in the Congested Clique.  Proceedings of the 39th Symposium on Principles of Distributed Computing (Jul 2020).  https://doi.org/10.1145/3382734.3405751
  * Elkin (2020) Michael Elkin. 2020\.  A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities.  J. ACM 67, 2 (2020), 13:1–13:15.
  * Fischer and Noever (2018) Manuela Fischer and Andreas Noever. 2018.  Tight Analysis of Parallel Randomized Greedy MIS. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018. 2152–2160.  https://doi.org/10.1137/1.9781611975031.140
  * Ghaffari (2016) Mohsen Ghaffari. 2016\.  An Improved Distributed Algorithm for Maximal Independent Set. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016. 270–277.
  * Ghaffari (2019) Mohsen Ghaffari. 2019\.  Distributed Maximal Independent Set Using Small Messages. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’19). Society for Industrial and Applied Mathematics, USA, 805–820.
  * Ghaffari and Kuhn (2018) Mohsen Ghaffari and Fabian Kuhn. 2018.  Distributed MST and Broadcast with Fewer Messages, and Faster Gossiping. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018 (LIPIcs), Ulrich Schmid and Josef Widder (Eds.), Vol. 121. 30:1–30:12.
  * Gmyr and Pandurangan (2018) Robert Gmyr and Gopal Pandurangan. 2018.  Time-Message Trade-Offs in Distributed Algorithms. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018 (LIPIcs), Ulrich Schmid and Josef Widder (Eds.), Vol. 121. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 32:1–32:18.  https://doi.org/10.4230/LIPIcs.DISC.2018.32
  * Halldórsson et al. (2020) Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, and Tigran Tonoyan. 2020.  Efficient Randomized Distributed Coloring in CONGEST.  CoRR abs/2012.14169 (2020).  https://arxiv.org/abs/2012.14169
  * Karloff et al. (2010) Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. 2010\.  A model of computation for mapreduce. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 938–948.
  * Karp and Rabin (1987) Richard M. Karp and Michael O. Rabin. 1987.  Efficient Randomized Pattern-Matching Algorithms.  IBM J. Res. Dev. 31, 2 (1987), 249–260.
  * King et al. (2015) Valerie King, Shay Kutten, and Mikkel Thorup. 2015\.  Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21 - 23, 2015, Chryssis Georgiou and Paul G. Spirakis (Eds.). ACM, 71–80.  https://doi.org/10.1145/2767386.2767405
  * Klauck et al. (2015) Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, and Peter Robinson. 2015.  Distributed Computation of Large-Scale Graph Problems. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’15). Society for Industrial and Applied Mathematics, USA, 391–410.
  * Konrad (2018) Christian Konrad. 2018\.  MIS in the Congested Clique Model in O(log log $\Delta$) Rounds.  CoRR abs/1802.07647 (2018).  arXiv:1802.07647 http://arxiv.org/abs/1802.07647
  * Korach et al. (1987) E. Korach, S. Moran, and S. Zaks. 1987.  The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors.  SIAM J. Comput. 16, 2 (April 1987), 231–236.  https://doi.org/10.1137/0216019
  * Kutten et al. (2015) Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, and Amitabh Trehan. 2015\.  On the Complexity of Universal Leader Election.  J. ACM 62, 1 (2015), 7:1–7:27.
  * Linial (1992) Nathan Linial. 1992\.  Locality in Distributed Graph Algorithms.  SIAM J. Comput. 21, 1 (1992), 193–201.  https://doi.org/10.1137/0221015
  * Lotker et al. (2005) Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg. 2005.  Minimum-Weight Spanning Tree Construction in O(Log Log n) Communication Rounds.  SIAM J. Comput. 35, 1 (July 2005), 120–131.  https://doi.org/10.1137/S0097539704441848
  * Luby (1985) M Luby. 1985.  A Simple Parallel Algorithm for the Maximal Independent Set Problem. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing (STOC ’85). Association for Computing Machinery, New York, NY, USA, 1–10.  https://doi.org/10.1145/22145.22146
  * Mashreghi and King (2018) Ali Mashreghi and Valerie King. 2018.  Broadcast and Minimum Spanning Tree with o(m) Messages in the Asynchronous CONGEST Model. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018 (LIPIcs), Vol. 121. 37:1–37:17.
  * Mashreghi and King (2019) Ali Mashreghi and Valerie King. 2019.  Brief Announcement: Faster Asynchronous MST and Low Diameter Tree Construction with Sublinear Communication. In 33rd International Symposium on Distributed Computing, DISC 2019, October 14-18, 2019, Budapest, Hungary (LIPIcs), Jukka Suomela (Ed.), Vol. 146. 49:1–49:3.
  * Motwani and Raghavan (1995) Rajeev Motwani and Prabhakar Raghavan. 1995.  Randomized Algorithms.  Cambridge University Press, USA.
  * Naor (1991) Moni Naor. 1991\.  A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring.  SIAM J. Discret. Math. 4, 3 (1991), 409–412.  https://doi.org/10.1137/0404036
  * Pai et al. (2017) Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Talal Riaz, and Peter Robinson. 2017\.  Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria (LIPIcs), Vol. 91. 38:1–38:16.
  * Pai and Pemmaraju (2020) Shreyas Pai and Sriram V. Pemmaraju. 2020.  Connectivity Lower Bounds in Broadcast Congested Clique. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) (Leibniz International Proceedings in Informatics (LIPIcs)), Nitin Saxena and Sunil Simon (Eds.), Vol. 182. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 32:1–32:17.  https://doi.org/10.4230/LIPIcs.FSTTCS.2020.32
  * Pandurangan et al. (2017) Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. 2017\.  A time- and message-optimal distributed algorithm for minimum spanning trees. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017. ACM, 743–756.
  * Patt-Shamir and Perry (2017) Boaz Patt-Shamir and Mor Perry. 2017.  Proof-Labeling Schemes: Broadcast, Unicast and in Between. In Stabilization, Safety, and Security of Distributed Systems - 19th International Symposium, SSS 2017, Boston, MA, USA, November 5-8, 2017, Proceedings (Lecture Notes in Computer Science), Paul G. Spirakis and Philippas Tsigas (Eds.), Vol. 10616. Springer, 1–17.  https://doi.org/10.1007/978-3-319-69084-1_1
  * Robinson (2021) Peter Robinson. 2021\.  Being Fast Means Being Chatty: The Local Information Cost of Graph Spanners. In ACM-SIAM Symposium on Discrete Algorithms (SODA).
  * Rozhon and Ghaffari (2020) Václav Rozhon and Mohsen Ghaffari. 2020.  Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020. 350–363.
  * Schmidt et al. (1993) Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan. 1993\.  Chernoff-Hoeffding Bounds for Applications with Limited Independence.  Society for Industrial and Applied Mathematics, USA, 331–340.
  * Vadhan (2012) Salil P. Vadhan. 2012\.  Pseudorandomness.  Foundations and Trends in Theoretical Computer Science 7, 1–3 (2012), 1–336.  https://doi.org/10.1561/0400000010
  * Yao (1977) Andrew Chi-Chin Yao. 1977\.  Probabilistic Computations: Toward a Unified Measure of Complexity. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science (SFCS ’77). IEEE Computer Society, USA, 222–227.  https://doi.org/10.1109/SFCS.1977.24
  * Öjvind Johansson (1999) Öjvind Johansson. 1999\.  Simple Distributed $(\Delta+1)$-Coloring of Graphs.  Information Processing Letters 70 70 (1999), 229–232.

##  Appendix A Appendix

###  A.1. Tail inequalities and hash functions with limited independence

To obtain message-efficient algorithms in the KT-$1$ model, we make use of
hash functions with limited independence. These hash functions use $c$-wise
independence and hence we use the following tail inequalities and properties
of such hash functions.

The following tail inequalities are from (Schmidt et al., 1993).

###### Lemma A.1.

Let $c\geq 4$ be an even integer. Suppose $Z_{1},Z_{2},\ldots,Z_{t}$ are
$c$-wise independent random variables taking values in $[0,1]$. Let
$Z=\sum_{i=1}^{t}Z_{i}$ and $\mu=\mathbb{E}[Z]$, and let $\lambda>0$. Then,

$Pr[|Z-\mu|\geq\lambda]\leq 2\left(\frac{ct}{\lambda^{2}}\right)^{c/2}.$

###### Lemma A.2.

Suppose that $X$ is the summation of $n$, $c$-wise independent 0-1 random
variables, each with mean $p$. Let $\mu$ satisfy $\mu\geq\mathbb{E}[X]=np$.
Then,

$\text{Pr}[X\geq(1+\delta)\mu]\leq exp(-\min\\{c,\delta^{2}\mu\\}).$

The following is Definition 7 in (Czumaj et al., 2020).

###### Definition A.3.

For $N$, $L$, $c\in\mathbb{N}$, such that $c\leq N$, a family of functions
$\mathcal{H}=\\{h:[N]\to[L]\\}$ is $c$-wise independent if for all distinct
$x_{1},x_{2},\ldots,x_{c}\in[N]$, the random variables
$h(x_{1}),h(x_{2}),\ldots,h(x_{c})$ are independent and uniformly distributed
in $[L]$ when $h$ is chosen uniformly at random from $H$.

The following lemma appears as Corollary 3.34 in (Vadhan, 2012).

###### Lemma A.4.

For every $a,b,c$, there is a family of $c$-wise independent hash functions
$\mathcal{H}=\\{h:\\{0,1\\}^{a}\to\\{0,1\\}^{b}\\}$ such that choosing a
random function from $\mathcal{H}$ takes $c\cdot\max\\{a,b\\}$ random bits,
and evaluating a function from $\mathcal{H}$ takes $\text{poly}(a,b,c)$
computation.

###  A.2. Simulating synchronous algorithms in an asynchronous model

###### Theorem A.5 (Awerbuch’s $\alpha$-synchronizer (Awerbuch, 1985)).

Given a synchronous Algorithm $A$ running in $T$ rounds on a graph with $m$
edges in the KT-$\rho$ Congest model for any $\rho\geq 1$, it is possible to
simulate $A$ in the asynchronous KT-$\rho$ Congest model in $T$ rounds. The
number of additional messages sent in the asynchronous execution compared to
an execution of $A$ is at most $2(T+1)m$.