clauses in which variable i participates are satisfied or if one or more are not. The CFL algorithm also satisfies the (D2) criterion that it sticks with a solution from the first time one is found. To see this, note that the affect of Step 5 is that if a variable experiences success in all clauses that it participates in it continues to select the same value with probability 1. Thus if all variables are simultaneously satisfied in all clauses, i.e.

if mini minm∈Mi Φi(~x) = 1, then the same assignment will be reselected indefinitely with probability 1.

To establish that the CFL algorithm is a decentralized CSP
solver all that remains is to show that it meets the (D1)
criterion, that if the problem has a solution it will be found, which is dealt with by the the following theorem. It provides an upper bound on the distribution of the number of iterations the algorithm requires to find a solution to any solvable CSP.

It's proof exploits the iterated function system structure of the algorithm and can be found in the Appendix.

Theorem 1: For any satisfiable CSP, with probability greater than 1 −  ∈ (0, 1) the number of iterations for the CFL algorithm to find a satisfying assignment is less than

6
$$\begin{array}{r l}{{}}&{{}{\mathrm{min~to~max~a~satisfying~assignment~to~too~min}}}\\ {{}}&{{}{N\exp\left({\frac{N(N+1)}{2}}\log(\gamma^{-1})\right)\log(\epsilon^{-1}),}}\\ {{}}&{{}{\mathrm{where~}}\gamma={\frac{\mathrm{min}(a,b)}{D-1+a/b}.}}\end{array}$$
For a CSP corresponding to graph coloring, a tighter bound holds and a satisfying assignment will be found with probability greater than 1 −  in a number of iterations less than

## N Exp(2N Log(Γ −1)) Log( −1).

Theorem 1 proves that for fixed N the tail of the distribution of the number of iterations until the first identification of a satisfying assignment is bounded above by a geometric distribution and so all of its moments are finite. As Theorem 1 covers any arbitrary CSP that admits a solution, for any given instance these bounds are likely to be loose. They do, however, allow us to conclude the following corollary proving that if a solution exists, the CFL algorithm will almost surely find it.

Corollary 2: For any CSP that admits a satisfying assignment, the CFL algorithm will find a satisfying assignment in almost surely finite time.

Hence the CFL algorithm satisfies all of the criteria (D1)
(D2) (D3) (D4) (D5) , almost surely, and so is a decentralized CSP solver.

## C. Parameterization

Theorem 1 establishes that the CFL algorithm provably identifies satisfying assignments for all values of its two design parameters, a and b. The value of a determines the algorithm's aversion to variable values for which clause failure has been experienced. The value of b impacts on the speed of convergence of the algorithm. Optimal values of a and b depend upon each problem and a performance metric. For fast convergence across a broad range of CSPs with distinct structure, we have found that small values of a and b, corresponding to strong aversion to a dissatisfying variable value and reasonably long memory, work well. Thus for simplicity, we set a = b in all experimental examples. We use b = 0.2 for random 3-SAT, b = 0.1 for random 4-SAT and b = 0.05 for random 5-SAT. We use b = 0.1 for our wireless networks example, a value which we have found to yield good performance across a range of k-SAT problems.

## Iv. Application-Agnostic Benchmarking

A CSP associated with a specific networking task will possess structure induced by its topology. Before considering practically-motivated applications in Section V, as the CFL algorithm can solve any CSP but its design was subject to restrictions not normally considered it is prudent to investigate its performance as a CSP solver in an application-agnostic setting.

We present simulation data evaluating the performance of the CFL algorithm for random k-SAT, a well-studied class of CSPs. A k-SAT problem is a CSP in which all variables are binary-valued and clauses consist solely of logical disjunctions of no more than k variables. In random k-SAT, an instance of k-SAT is generated by drawing M such clauses uniformly at random [22]. Our investigation surprisingly reveals that the CFL algorithm is competitive with centralized and distributed solvers on problems of reasonable size (order 1000 variables).

Briefly, we first review current knowledge regarding random k-SAT. The behavior of random k-SAT is known to depend strongly on the parameter r = M/N with phase transitions and associated thresholds r¬*exist,k* and r*exist,k*. If r > r¬*exist,k* the constraint problem is unsatisfiable with high probability, while if r < r*exist,k* a satisfying assignments exist with high probability. Evidently, rexist,k ≤ r¬*exist,k* and it is conjectured that rexist,k = r¬*exist,k* [25]. A simple argument gives r¬*exist,k* ≤ 2 klog 2 and this upper bound can be refined to obtain the values in the second row of Table I. Also shown in row four of this table are estimated values for r¬*exist,k* derived from statistical physics considerations. These latter estimates are supported by experimental data for k = 3, e.g. [30], although there are fewer experimental studies for k > 3.

It can be seen that the theoretical bound for r¬*exist,k* and the estimated values are in good agreement for k ≥ 5, and that both approach 2 klog 2 for large k. Recent mathematical results have established that r*exist,k* ≥ 2 klog 2−k [24] and this lower bound can be tightened to obtain the theoretical values shown in the third row of Table I.

There also exists a threshold r*poly,k* below which a satisfying assignment can be found in polynomial time with high probability. This threshold has been the subject of much interest and the current best analytic lower bound for r*poly,k* is also indicated in Table I. Statistical physics considerations have led to the conjecture that r*poly,k* is equal to the value r1*RSB,k* at which the one-step replica symmetry breaking
(1RSB) instability occurs [31]. Current best estimates for this value are given in Table I. For k ≥ 8, it has been proven analytically that the set of satisfying assignments is grouped into widely separated clusters, which lends support to this conjecture [32]. For values of k < 8 the situation is less clear, with experimental evidence indicating that r*poly,k* lies above r1*RSB,k* for k = 3, 4 and 5 [33].