

![0_image_0.png](0_image_0.png)

information, however, tends to be opportunistic in nature and cannot be relied on *a priori*. We leave how best to exploit such partial information to future work, focusing here on the most challenging, fundamental cases where fully decentralized algorithms are required.

## B. Contribution

The primary contributions of this paper are fourfold. Firstly, we show that CSPs provide a unifying framework that encompasses several important problems in wireless networks, including channel selection, inter-session network coding and decentralized scheduling in a WLAN. Each of these problems is generally thought of as being distinct and requiring different solution approaches. We show that they are fundamentally related as CSPs so that the decentralized CSP solver introduced in this paper can be used for all of them. Secondly, we define a new class of CSP algorithms which we term decentralized CSP
solvers and, extending our earlier approach to graph colouring [5][6], introduce a novel stochastic decentralized CSP solver proving that it will find a solution in almost surely finite time, should one exist, and showing it has many practically desirable properties. Thirdly, we benchmark the algorithm's performance on a well-studied class of application-agnostic CSPs, random k-SAT. For problems with up to a thousand variables, which are large for our motivating examples, we find that the time the algorithm takes to find a satisfying assignment is close to that of WalkSAT [7], a well regarded, efficient centralized CSP solver, while also possessing desirable features of Survey Propagation [8]. That is, despite its decentralized nature, the algorithm is fast. Fourthly, we demonstrate the solver's practical utility in a complex, wireless resource allocation case study.

The rest of the paper is organized as follows. In Section II we define decentralized CSP solvers and show that wellknown algorithms for solving CSPs fail to meet these criteria.

In Section III we introduce a decentralized CSP solver. We prove that it finds a solution in finite time with probability one whenever a feasible solution exists, obtaining an upper bound on the algorithm's convergence rate in the process. In Section IV we consider its speed at identifying solutions of instances of random k-SAT. In Section V we demonstrate the algorithm's utility in solving the problems that motivated its introduction. Section VI contains discussion and closing remarks.

## Ii. Decentralized Csp Solvers

We begin by formalizing the criteria that CSP solvers must possess to be of use for problems with communication constraints such as those outlined above. We call algorithms that meet these criteria decentralized CSP solvers.

Definition 1 (CSP): A CSP with N variables,
{x1*, . . . , x*N }, and M clauses is defined as follows. The variables each take values in a finite set D = {1*, . . . , D*} and
~x := (x1, . . . , xN ) ∈ DN . Each clause m ∈ M = {1*, . . . , M*}
is defined by a function Φm : DN *7→ {*0, 1} where for an assignment of variables, ~x, Φm(~x) = 1 if clause m is satisfied and Φm(~x) = 0 if clause m is not satisfied. An assignment
~x is a solution to the CSP if all clauses are simultaneously satisfied. That is,
~x is a satisfying assignment iff min m∈M

$$\operatorname*{min}_{x\in\Lambda^{4}}\Phi_{m}({\vec{x}})=1.\qquad0$$

This encompasses all of our examples of interest as well as k-SAT, the most well-studied general class of CSPs.

A CSP solver is an algorithm that can find a satisfying variable assignment for any solvable CSP.

Definition 2 (CSP Solver): A CSP solver takes a CSP as input and determines a sequence {~x(t)} such that for any CSP
that has satisfying assignments:
(D1) for all t sufficiently large ~x(t) = ~x for some satisfying assignment ~x;
(D2) if t 0is the first entry in the sequence {~x(t)} such that
~x(t 0) is a satisfying assignment, then ~x(t) = ~x(t 0) for all *t > t*0.

To provide criteria that classify CSP solvers as being decentralized, we begin with the following definition.

Definition 3 (Clause participation): We say that variable xi participates in clause Φm(~x) if the value of xi can influence the clause's satisfaction for at least one assignment of the rest of the variables in ~x.

For each variable xi, let Mi denote the set of clauses in which it participates:

$$\begin{array}{c}{{\mathcal{M}_{i}=\bigcup_{x_{i}\in\{1,\ldots,d\}}\left(\bigcup_{j\neq i}\bigcup_{x_{j}\in\{1,\ldots,d\}}\{m:\Phi_{m}(x_{i},\{x_{j}\})=0\}\right.}}\\ {{\left.\bigcap_{j\neq i}\bigcup_{x_{j}\in\{1,\ldots,d\}}\{m:\Phi_{m}(x_{i},\{x_{j}\})=1\}\right).}}\end{array}$$  Re-writing the left hand side of eq. (1) in a way that focuses.  
on the satisfaction of each variable we have:
~x is a satisfying assignment iff min imin m∈Mi Φm(~x) = 1. (2)
A decentralized CSP algorithm can be thought of as having intelligence co-located with each variable. The intelligence at variable xi can only determine whether all of the clauses that xi participates in are satisfied or that at least one clause