### Distributed Constraint Satisfaction Problem: Formalization and
Algorithms

Makoto Yokoo, Edmund H. Durfee, Toru Ishida, and Kazuhiro Kuwabara

IEEE Trans. on Knowledge and Data Engineering, vol.10, No.5,
1998.

In this paper, we develop a formalism called a distributed
constraint satisfaction problem
(distributed CSP) and algorithms for solving distributed CSPs.
A distributed CSP
is a constraint satisfaction problem in which variables and constraints are distributed among
multiple agents.
Various application problems in Distributed Artificial Intelligence can
be formalized as distributed CSPs.
We present our newly developed technique called
asynchronous backtracking that allows agents to act
asynchronously and concurrently without any global control,
while guaranteeing the completeness of the algorithm.
Furthermore, we describe how the asynchronous backtracking algorithm can be modified into
a more efficient algorithm called asynchronous weak-commitment
search, which
can revise a bad decision without exhaustive search
by changing the priority order of agents dynamically.
The experimental results on various example problems
show that the asynchronous weak-commitment search algorithm is by far more efficient than
the asynchronous backtracking algorithm and can solve fairly
large-scale problems.