Distributed Constraint Satisfaction for Formalizing Distributed Problem Solving
Makoto Yokoo, Edmund H. Durfee, Toru Ishida, Kazuhiro Kuwabara
12th International Conference on Distributed Computing Systems (ICDCS-92), pp. 614-621, 1992.

Viewing cooperative distributed problem solving (CDPS) as distributed constraint satisfaction provides a useful formalism for characterizing CDPS techniques. In this paper, we describe this formalism and compare algorithms for solving distributed constraint satisfaction problems (DCSPs). In particular, we present our newly developed technique called asynchronous backtracking that allows agents to act asynchronously and concurrently, in contrast to the traditional sequential backtracking techniques employed in constraint satisfaction problems. Our experimental results show that solving DCSPs in a distributed fashion is worthwhile when the problems solved by individual agents are loosely-coupled.