A DisCSP Solving Algorithm Based on Sessions
Arnaud Doniec, Sylvain Piechowiak, René Mandiau · 2005
For a few years, there is some interest about solving distributed problems. Particularly, many contributions have been brought in the resolution of distributed constraint satisfaction problems. Most of works tend to propose asynchronous search algorithms. These are always an adaptation of the backtracking principle well known for resolution of centralized CSP. Few interest has been shown about the spatial complexity of these algorithms and the way they are evaluated. Indeed, most of algorithms in literature use nogoods saving which can imply an exponential spatial complexity in the worst case. Then, these algorithms are evaluated by a discrete event simulator. Since these algorithms are designed to be used in real world problems, we think that a realistic evaluation (i.e. implementation and execution over physically distributed computer) is more adapted. In this article, we propose a simple algorithm avoiding the nogoods recording and consequently an exponential spatial complexity. We finish with realistic experiments of this algorithm. Distributed Constraint Satisfaction Problems A constraint satisfaction problem (CSP) can be viewed as a triplet (X, D, C) in which: X is a finite set of variables, each variable xi ∈ X is associated to a finite domain dom(xi) ∈ D and related to a finite set of constraints in C. Associating a value to a variable is called an assignation. When an assignation did not violate any constraint of C, assignation is qualified with consistent. So, a solution of a CSP (X, D, C) is a set of n assignations (n = card(X)) all consistent with C. The general framework of CSP has been enriched with many extensions such as dynamic CSP(Bessière 1992), max CSP(Freuder & Wallace 1989) and so on. The concept of distributed CSP has been introduced to formalize and resolve naturally distributed problems (Yokoo et al. 1992). Such problems generally deal with a set of data, shared out among many sites, whose a centralization is often impossible