Maintaining local consistency during backtrack search is one of the most powerful techniques for solving centralized constraint satisfaction problems (CSPs). Yet, no work has been reported on such a combination in asynchronous settings. The difficulty in this case is that, in the usual algorithms, the instantiation and consistency enforcement steps must alternate sequentially. When brought to a distributed setting, a similar approach forces the search algorithm to be synchronous in order to benefit from consistency maintenance. Asynchronism is highly desirable since it increases parallelism and makes the solving process robust against timing variations. This paper shows how an asynchronous algorithm for maintaining consistency during distributed search can be designed. The proposed algorithm is complete and has polynomial-space complexity. Experimental evaluations show that it brings substantial gains in computational power compared with existing asynchronous algorithms.
展开▼
