4 Local Symmetry Breaking

---

We will look at problems which are local symmetry breaking, where the goal is to break symmetry among nodes that are quite close, typically neighbors. A fundamental problem in this category is the Maximal Independent Set (MIS) problem. We will look at a MIS Algorithm that takes $O(\log n)$ rounds. Another way to view this analysis is that each node (with high probability) needs only information about its $O(\log n)$ neighborhood.

A fundamental open question in distributed computing is to fully characterize the locality of MIS. We can show a highly non-trivial locality lower bound of $\Omega ({\log }^{\ast }n)$ for MIS.

Besides MIS, another local symmetry breaking problem is coloring. Both are related to each other in some way, yet they have their own characteristics.

We will consider the synchronous LOCAL model, although all the algorithms will work seamlessly in the CONGEST model as well, for the following problems. As usual we consider the network as an undirected connected graph $G=(V,E)$ of $n$ nodes. All nodes have unique identifiers and can be represented in $O(\log n)$ bits. We also assume that all nodes are awake initially and start executing the algorithm simultaneously.

---

Maximal Independent Set (MIS)

An useful property of MIS is that it is also a dominating set. In fact it is a minimal dominating set (MDS) as well. A dominating set could be used as a network backbone for routing - it is enough to find routes between the nodes in the dominating set; any other node can route by sending it to any of its dominator first.

Fast Distributed MIS Algorithms:

The output of each node in this problem would be whether the corresponding node is in the MIS or not. Let $\Gamma (v)$ be the set of vertices in $V$ that are adjacent to $v$. Let $N(v)$ denote the close neighborhood of $v$, i.e., the set consisting of $v$ and $\Gamma (v)$ .

The outline of the algorithm would be somewhat like this . In every round, it finds an independent set $S$ and adds it to $I$ (which is empty initially) as well as deletes $S\cup \Gamma (S)$ from the graph. This is easy to implement in a linear fashion - Choose some arbitrary node, turn off its neighbors (essentially deleting the nodes) and continue the same process with the remaining graph, until the graph becomes empty.

To get a faster algorithm, an obvious strategy is to include as many nodes in the MIS in a round as possible. Consider a node $v$. Clearly, either $v$ or at least one of its neighbors should be in the MIS.

MIS Algorithm 1:

Each node chooses itself to be in the MIS with probability $\frac{1}{2\cdot d(v)}$ . To handle the scenario of two neighboring nodes choosing themselves, the ties are broken based on the degrees with higher degree node favored. This makes sense since once this high degree node comes to MIS, it will eliminate more neighbors.

Pseudocode:

flag = not decided // flag = true if the node is in MIS else false

while(flag is not decided){
	if(degree[v] = 0){
		flag = true 
	}
	else
		mark flag = true with a probability 1/(2* degree[v]) 
		
	if(flag = true){
		receive message from neighbor
		if there is a neighbor with flag = true and degree > degree[v]{
			flag = false 
		}
	}
	if(flag = true){
		notify neighbors.
	}
	else if(flag = false){
		if there is a neighbor with flag = true{
			delete itself and all its edges from the network.
			flag = false.
		}
	}
}

Analysis:

Claim 1:

MIS Algorithm 1 runs in $O(\log n\log \Delta )$ with high probability, where $\Delta$ is the maximum node degree.

Claim 2:

Consider any node $v$ in phase $i$ $(1\le i\le \log \Delta )$ . One of the following events will happen - The status of $v$ will be determined or $d(v)$ will drop below $\frac{\Delta }{2^i}$ .

Proof:

For the sake of analysis, we divide the algorithm into phases - In the first phase, we will consider the nodes having degree between $[\Delta ,\Delta /2)$ . In phase $i$, the nodes considered will have degree between $\left[\frac{\Delta }{2^{i-1}},\frac{\Delta }{2^i}\right)$ .

Thus, there will be $O(\log \Delta )$ phases. At the end of phase $i$ , the status of all nodes of degree higher than $\frac{\Delta }{2^i}$ would have been decided.

Consider phase 1. We lower bound the probability that a status of $v$ will be determined in one round. This can be done in two ways:

1. $v$ enters MIS or
2. a neighbor of $v$ enters MIS.

We can lower bound the probability that a neighbor of $v$ enters MIS as follows in two ways:

1. A neighbor of $v$, say $w$ marks itself.
2. At least one of $v$‘s marked neighbors remain marked after the tie-breaking step.

The probability that none of the neighbors of $v$ enter the MIS is at most

$${\left(1-\frac{1}{2\Delta }\right)}^{\Delta /2}\le e^{-1/4}$$

This is because all the neighbors of $v$ have degree at most $\Delta$ and $d(v)\ge \frac{\Delta }{2}$ . Hence the probability that a neighbor of $v$ enters the MIS is at least $1-e^{-1/4}$ .

Let’s bound the probability of the second way, given that at least one of the neighbor of $v$ has marked itself. Among all the neighbors of $v$ that are marked, consider the one with highest degree and highest priority as $w$. Now it is enough to focus on the neighbors of $w$ that are not in $\Gamma (v)$ since $w$ is the highest degree by assumption among $\Gamma (v)$ .

Thus we can bound the probability of the following event, independent of the nodes in $N(v)$: The probability that at least one of the neighbors of $w$ (excluding those in $N(v)$) is marked is at most

$$\sum _{u\in \Gamma (w)}\frac{1}{2\cdot d(w)}\le \frac{1}{2}$$

Thus the probability that none of its neighbors are marked is at least $\frac{1}{2}$ . Therefore, probability of both the events happening is $\beta =(1-e^{-1/4})\cdot \frac{1}{2}$ . Let $k$ be the number of rounds this phase runs. Then probability that for a given node $v$ , both the events doesn’t happen is $(1-\beta {)}^k$ .

Let $k=(C+1){\log }_{1/(1-\beta )}n=O(\log n)$ , then by the union bound, the probability that there is a node that $v$ such that its status isn’t determined as well it’s degree doesn’t drop below $\frac{\Delta }{2}$ is at most

$$p=n\cdot (1-\beta {)}^k=\frac{1}{n^C}$$

Thus, with probability at least $1-p$, all nodes would have either their status determined or their degree would have dropped below $\frac{\Delta }{2}$ . Similar argument can be applied for subsequent phases, by applying union bound over all the $O(\log \Delta )$ phases, the status of all nodes will be determined with high probability in $O(\log n\log \Delta )$ rounds.

MIS Algorithm 2:

Lets cut the slack and dive into the pseudocode directly.

Pseudocode:

flag = undecided
while(flag is undecided){
	if(degree[v] = 0):
		flag = true
	else
		flag = true 
		Choose a random real number uniformly and independently from [0 , 1]
		Let this number be rank[v]. Notify this to the neighbors
	if flag = true
		if lower-ranked neighbor has flag = true
			flag = undecided  // Tie-breaking step
	if flag = true 
		flag = true 
		send message to its neighbors
	if there is a neighbor with flag = true
		delete the node and all the edges from the network
		flag = false 	
}

Analysis:

Claim:

In one iteration of the while loop of the algorithm, the expected number of edges deleted is at least half the number of edges in the current graph.

Proof:

Let $F$ be the set of edges at the beginning of an iteration. Replace each undirected edge $(u,v)$ with two directed edges $u\to v$ and $v\to u$ . Call a node $u$ eligible with respect to $v$ if $u$ is the smallest ranked node among $N(u),N(v)$. If $u$ is eligible w.r.t $v$, it will be in MIS as it is the lowest ranked node among $N(u)$.

$$P(u\text{is eligibe w.r.t to }v)\ge \frac{1}{d(u)+d(v)}$$

This probability can be derived directly using symmetry, since probability that at least one of the nodes from $N(u),N(v)$ having the smallest number is $1$ , therefore the required probability is at least $\frac{1}{d(u)+d(v)}$ . This can also be shown using integration.

Let random variable $X(u\to v)$ denote the number of directed outgoing edges incident to $v$ that get deleted when $u$ is eligible w.r.t $v$ . $X(u\to v)\ge d(v)$ . Note that this is an undercounting, since we are not counting the edges removed when $u$ is deleted that are outgoing from $u$. But this is to ensure that we don’t overcount the outgoing edges of $u$ that will be deleted when we calculate the total over all edges. More precisely, Let $X$ denote the total number of directed edges deleted in the iteration. Then

$$X\ge \sum _{(u\to v),(v\to u)\in F}X(u\to v)+X(v\to u)$$

Note that $u$ is the lowest ranked among $N(v),N(u)$ if it is eligible w.r.t $v$. This guarantees that no two neighbors of $v$ simultaneously try to delete the outgoing edges of $v$.

By Linearity of Expectation, the expected total number of directed edges deleted is

$$E[X]\ge \sum _{(u\to v),(v\to u)\in F}E[X(u\to v)]+E[X(v\to u)]$$ $$\ge \sum _{(u\to v),(v\to u)\in F}\frac{d(v)}{d(u)+d(v)}+\frac{d(u)}{d(u)+d(v)}$$ $$\ge |F|$$

Since there $2|F|$ directed edges, the actual number of edges deleted is at least $\frac{|F|}{2}$.

Claim:

The algorithm terminates in $O(\log n)$ iterations with high probability.

Proof:

Let $X$ be the number of edges remaining after $k$th iteration. The expected number of edges remaining after $k$ iterations is at most $\frac{|E|}{2^k}$. Let $k=C\log n$. Plugging this in, we get the expected number of edges remaining as

$$E[X]=\frac{|E|}{n^C}$$

Using Markov’s inequality,

$$P(X\ge 1)\le E[X]$$

Since $|E|\le n^2$ , therefore $P(X\le 1)\le \frac{1}{n^{C-2}}$ , we can conveniently chose $C=4$ so that the probability that at least one edge will remain after $4\log n$ iterations is at most $\frac{1}{n^2}$ .

Coloring

We already saw an $O({\log }^{\ast }n)$-round algorithm for directed paths. A similar algorithm can be applied for rooted trees as well. Follow the same strategy, but instead each node comparing its color with its parent instead of its successor. By this way, we can maintain the legality each round. We can view this algorithm on rooted trees working on each disjoint path on the tree separately from a node.

$\Delta +1$ coloring on bounded degree graphs:

Lets now see a coloring algorithm for a general bounded degree graph along the lines of the algorithm we saw previously.

Consider a vertex $v$, and let it have $k$ (at most $\Delta$) neighbors: $u_1,u_2,...,u_k$ . Initially each node takes it own ID as its color. Let $c(v)$ be the bit representation. Let $b(u_j)$ be the bit representation of the index of the first (least significant) bit where $c(v)$ differs from $c(u_j)$ for all $1\le j\le k$ . Then $v$ sets it color to be

$$\text{concat}(b(u_1),c(u_1)[b(u_1)],b(u_2),c(u_2)[b(u_2)],...,b(u_k),c(u_k)[b(u_k)])$$

where $c(u_i)[b(u_i)]$ represents the $b(u_i)$th bit in $c(u_i)$.

This again can be viewed similar to the algorithm presented for rooted trees, here we have $\Delta$ parents at most for each node and we break the symmetry with each parent. This algorithm reduces the number of bits in the colors from $\ell$ to at most $\Delta (\log \ell +1)$ in one step. Thus, by applying this reduction $O({\log }^{\ast }n)$ times, the number of bits in the colors reduce to at most $3\Delta$ . Hence the total number of colors in the graph is at most $2^{3\Delta }$ .

Now we reduce this to $\Delta +1$ in $O(2^{3\Delta })$ rounds. In each round, one color higher than $\Delta +1$ is eliminated. This is straightforward - choose a set of nodes with color $c>\Delta +1$ , let’s say $\Delta +2$ . Now find the minimum color that is not present among the neighbors of this node and recolor it with that color. Since initially legality was preserved before these rounds, no two adjacent nodes will be recoloring themselves, thus preserving legality. We continue the same process for nodes with color $\Delta +3$ , and so on.

Claim:

Any graph with maximum degree $\Delta$ can be colored in $O(2^{3\Delta }+{\log }^{\ast }n)$ rounds using $\Delta +1$ colors. If we assume $\Delta =O(1)$ , then such a graph can be colored in $O({\log }^{\ast }n)$ rounds.

Exercises