Arnaud Doniec, Sylvain Piechowiak, and René Mandiau, Université de Valenciennes
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.