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

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 probability³³3This 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.

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.

• •

  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.⁴⁴4Note 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$.

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.

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))$.

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.

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.

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.

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

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

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}$.

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$.

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.

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.

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.

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}$.

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.

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

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