Backtracking in Distributed Constraint Networks

The adaptation of software technology to distributed environments will be an important challenge in the next few years. In the scope of constraint reasoning, few works have been published on the adaptation of algorithms searching for a solution in a constraint network to distributed constraint networks. This paper presents a new search procedure for finding a solution in a distributed constraint network. Although based on the principle of backtracking to ensure the completeness of search, this procedure allows a high level of asynchronism, i.e., simultaneous search on independent parts of the network. Furthermore, it fits its behavior to the structure of the constraint graph in order to minimize message passing and to avoid useless restorations when a dead-end is reached. We also present a generic distributed method for computing any variable ordering heuristic.