U0 6= ∅, the algorithm has not yet found a solution. Define the components, ~x(1)i, of the vector ~x(1) by

npoints, $x(1)_i$, of the vector $x(1)$ by $$\vec{x}(1)_i=\begin{cases}\vec{a}_i&\text{if}i\in U_0\\ \vec{x}(0)_i&\text{if}i\notin U_0\end{cases}$$ |, by Lemma 1,
$$P(X(1)={\vec{x}}(1)|X(0)={\vec{x}}(0))\geq\gamma^{n_{0}}.$$
If U1 = ∅ then X(1) ∈ A, the algorithm has found a solution and τ = 1. If U1 6= ∅, the algorithm has not yet found a solution and we proceed in an iterative fashion. For t ≥ 0,

ne the components, $\vec{x}(t+1)_i$, of the vector $\vec{x}(t+1)_i$, $\vec{x}(t+1)_i=\begin{cases}\vec{a}_i&\text{if}i\in U_t\\ \vec{x}(t)_i&\text{if}i\notin U_t\end{cases}$  , by Lemma 1,
$$P(X(t+1)={\vec{x}}(t+1)|X(t)={\vec{x}}(t))\geq\gamma^{n_{t}}.$$
Let $t^*=\inf\{t:n_t=0\}$ and note that . 
$$P(X(t^{*})\in A)\geq1$$
$$P(X(t^{*})\in\Lambda)=$$ $$P(X(t^{*})={\vec{x}}(t^{*}),\ldots,X(0)={\vec{x}}(0))\geq\gamma^{\sum_{t=0}^{t^{*}}n_{t}}.$$
We wish, therefore, to place an upper bound on the sum in the exponent. Observe that t
∗ ≤ N − 1, as one starts with at least one unsatisfied variable at each stage we me must include at least one new variable and, therefore, this procedure must terminate in no more than N −1 steps with a valid assignment.

In general, the {n
∗
t } sequence that maximizes this sum, even though this sequence may not be feasible for a given CSP, is

$$n_{0}^{*}=1,n_{1}^{*}=2,\ldots,n_{N-1}^{*}=N,$$

This occurs if we start with one unsatisfied variable and, in changing to the valid solution, at each iteration one additional variable has cause to be unsatisfied. On taking its new value, the unsatisfied variable included at time t triggers the failure of t − 1 clauses each of which contains 3 variables: itself, the variable included immediately previously and one of the other variables that has already experienced a failure. This gives

$$\sum_{t=0}^{t^{*}}n_{t}\leq\sum_{t=0}^{N}n_{t}^{*}={\frac{N(N+1)}{2}}.$$

$\;$and therefore: . 
$$P(X(N-1)\in A)\geq\gamma^{N(N+1)/2}.$$

For a CSP corresponding to graph coloring with D colours, the advantage is that variables cannot be dissatisfied indefinitely by newly dissatisfied variables. Instead this procedure generates a flame-front of dissatisfied variables where those variables sufficiently far within the interior of this flamefront can select their final value without further disturbance.

For graph colouring, clauses occur only for each pair of neighbors, i and j, such that Φ(~x) = 0 if (~x)i = (~x)j and Φ(~x) = 1 otherwise. For any initial configuration ~x(0) with dissatisfaction, we must have n0 ≥ 2. In a sequence of events analogous to those in the proof of [6][Theorem 3], these two variables select their final values, ~ai and (~a)j , at the next round, causing their initial clause to be satisfied as ~a ∈ A. If either of the variables taking its final value causes no further clause to be dissatisfied, then in this sequence of events it will never appear in a dissatisfied clause again and stays with its value with probability 1. If it does cause one or more clause to be triggered, once these are satisfied it will experience no more dissatisfaction. Thus each variable experiences at most 2 rounds of dissatisfaction so that for graph colouring:

$$\sum_{t=0}^{t^{*}}n_{t}\leq\sum_{t=0}^{N-1}n_{t}^{*}=2N.$$

As an example that illustrates the difference between a general CSP and graph colouring, consider an instance of 3-
SAT starting with one unsatisfied variable, x1. The following sequence of clauses is possible in general, but not with graph colouring. Starting with an unsatisfied x1, changing its value to satisfy the first clause causes x2 to be dissatisfied, which in turn causes x1 and x2 and x3 to be dissatisfied:

$x_1,\ \neg x_1\lor x_2$ and $\neg x_1\lor\neg x_2\lor x_3$. 
Satisfying these clauses for x1, x2 and x3 causes two more clauses with x4 to trigger, keeping all variables unsatisfied:
¬x1 ∨ ¬x2 ∨ x4 and ¬x1 ∨ ¬x3 ∨ x4.

Satisfying these two clauses causes three further clauses involving x5 to become unsatisfied:
¬x1 ∨ ¬x2 ∨ x5, ¬x1 ∨ ¬x3 ∨ x5 and ¬x1 ∨ ¬x4 ∨ x5 and so forth triggering clauses with three variables at a time such that all variables are unsatisfied until a solution is found.

REFERENCES
[1] H. Wu, Fan Y. Yang, K. Tan, J. Chen, Q. Zhang, and Z. Zhang,
"Distributed channel assignment and routing in multiradio multichannel multihop wireless networks," *IEEE Trans. Wireless Commun.*, vol. 9, no. 10, pp. 1972–1983, 2006.

[2] B. Kauffmann, F. Baccelli, A. Chaintreau, V. Mhatre, K. Papagiannaki, and C. Diot, "Self organization of interfering 802.11 wireless access networks," in *IEEE INFOCOM*, 2007.

[3] J. Crichigno, M.-Y. Wu, and W. Shu, "Protocols and architectures for channel assignment in wireless mesh networks," *Ad Hoc Netw.*, vol. 6, no. 7, pp. 1051–1077, Sept. 2008.

[4] A. P. Subramanian, H. Gupta, S. R. Das, and J. Cao, "Minimum interference channel assignment in multiradio wireless mesh networks,"
IEEE Trans. Mobile Comput., vol. 7, no. 12, pp. 1459–1473, Dec. 2008.

[5] D. J. Leith and P. Clifford, "A self-managed distributed channel selection algorithm for WLANs," in *Procedings of RAWNET, Boston, MA*, 2006.

[6] K. Duffy, N. O'Connell, and A. Sapozhnikov, "Complexity analysis of a decentralised graph colouring algorithm.," *Inform. Process. Lett.*, vol.

107, no. 2, pp. 60–63, 2008.

[7] B. Selman, H. Kautz, and B. Cohen, "Local search strategies for satisfiability testing," in *DIMACS SERIES IN DISCRETE MATHEMATICS*
AND THEORETICAL COMPUTER SCIENCE, 1995, pp. 521–532.

[8] A. Braunstein, M. Mezard, and R. Zecchina, "Survey propagation: An algorithm for satisfiability," *Rand. Struct. Algorithms*, vol. 27, no. 2, pp.

201–226, 2005.

[9] R. Koetter and M. Medard, "An algebraic approach to network coding," ´
IEEE/ACM Trans. Network., vol. 11, pp. 782–795, 2003.

[10] S. Deb, M. Effros, T. Ho, D. R. Karger, R. Koetter, D. S. Lun, M. Medard, and N. Ratnakar, "Network coding for wireless applications: ´
A brief tutorial," in *IWWAN*, 2005.

[11] S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft, ´
"XORs in the air: practical wireless network coding," *SIGCOMM* Comput. Commun. Rev., vol. 36, no. 4, pp. 243–254, Aug. 2006.