B. Related work - existing algorithms are not decentralized The literature on general purpose CSP solvers is vast, typically focusing on solving k-SAT problems in conjunctive normal form, but they can be broadly classified into those based on: (i) the Davis-Putnam-Logemann-Loveland (DPLL)
algorithm [16], [17]; (ii) Survey Propagation [8]; and (iii) on Stochastic Local Search (SLS) [7]. Each of these approaches has experienced substantial development and has its own merits, but none were motivated by problems where variables have a geographical sense of locality.

Algorithms developed from the DPLL approach have proved to be the quickest at SAT-Race and SAT Competition in recent years, e.g. ManySAT [18]. The DPLL approach ultimately guarantees a complete search of the solution space and so meets the (D1) and (D2) criteria. They are, however, based on a branching rule methodology, e.g. [19], that assumes the existence of a centralized intelligence that employs a backtracking search. The implicit assumptions of the information available to this intelligence breaks the conditions (D3) (D4)
(D5) and so they are not decentralized CSP solvers.

Survey propagation, a development of belief propagation
[20] from trees to general graphs, has proved effective in graphs that do not contain small loops [21]. For a given CSP,
the fundamental structure of study is a called a factor graph. In order to generate this, it is necessary to know what clauses each variable participates in and the nature of each of the clauses, breaking the (D4) and (D5) criteria and so these are not decentralized CSP solvers.

SLS algorithms also depend fundamentally upon the exchange of information, mostly in an explicit manner breaking the (D3) condition by basing update decisions on relative rankings of the constraint variables but also in a more subtle fashion. To see this implicit requirement, consider the following algorithm for binary valued variables originally proposed by Papadimitriou [22] and developed further by Schoning [23]. Pick a random assignment of values for the ¨
constraint variables. Repeat the following: from all of the unsatisfied clauses, pick one uniformly at random, select one of the variables participating in that clause and negate its value, breaking the (D4) and (D5) conditions. The algorithm halts when all clauses are satisfied or a specified time limit expires. Although simple, this forms the basic building block for all SLS algorithms, including the well-studied WalkSAT
algorithm [7]. It is important that a single unsatisfied clause is selected at each step and that a single variable within the clause is adjusted as it is this that leads to the algorithm behaving as a random walk [23]. Thus, again, solvers in this class are not decentralized.

## Iii. A Decentralized Csp Solver

We now introduce an algorithm that satisfies the decentralized CSP solver criteria.

## A. Communication-Free Learning Algorithm

An instance of the following Communication-Free Learning
(CFL) algorithm is run in parallel for every variable. For each variable, i ∈ {1, 2*, ..., N*} it keeps a probability distribution, pi,j over j ∈ D as well as the current variable value xi. In pseudocode, the CFL algorithm is:
ALGORITHM 1: Communication-Free Learning

1: Initialize pi,j = 1/d, j ∈ {1*, ..., D*}.

2: **loop**
3: Realize a random variable, selecting xi = j with probability pi,j .

4: Evaluate minm∈Mi Φm(~x), returning *satisfied* if its value is 1, as this indicates all of variable i's clauses are satisfied given the present assignment, and *unsatisfied* otherwise.

5: Update: If *satisfied*,
5
pi,j = 1 if j = xi 0 otherwise. If unsatisfied,
$$p_{i,j}=\begin{cases}(1-b)p_{i,j}+a/(D-1+a/b)&\text{if}j=x_{i}\\ (1-b)p_{i,j}+b/(D-1+a/b)&\text{otherwise,}\end{cases}$$  where $a,b\in(0,1]$ are design parameters.  6: **end loop**
To understand the logic behind CFL, note that for each variable a probability distribution over all possible variablevalues is kept. The variable's value is then selected from this distribution. Should all the clauses that the variable participates in be satisfied with its current value, the associated probability distribution is updated to ensure that the variable value remains unchanged. If at least one clause is unsatisfied, then the probability distribution evolves by interpolating between it and a distribution that is uniform on all values apart from on the one that is presently generating dissatisfaction. Thus if all of a variable's clauses were once satisfied, the algorithm retains memory of this into the future. This has the effect that if a collection of variables are content, they can be resistant, but not impervious, to propagation of dissatisfaction from other variables.

CFL possesses two parameters. The parameter b determines how quickly the past is forgotten, while a determines the algorithm's aversion to a variable value should it be found to cause dissatisfaction. Even though an instance of CFL is run for each variable, we shall show that this completely decentralized solution is a CSP solver.

From here on we will assume that the update Step 5 is performed in a synchronized fashion across variables. Without synchronization, the fundamental character of the algorithm doesn't change, but the analysis becomes more involved.

Synchronization solely requires that algorithm instances each have access to a shared sense of time and that this can be achieved without information-sharing or other communication between variables, i.e. between algorithm instances. A suitable clock is, for example, available to any Internet connected device via the Network Time Protocol (NTP).

## B. Cfl Is A Decentralized Csp Solver

By construction, the only information used by the algorithm is minm∈Mi Φi(~x) in Step 4 and thus it satisfies the criteria
(D3) , (D4) and (D5) . That is, it only needs to know if all