A distributed arc-consistency algorithm

Consistency techniques are an efficient way of tackling constraint satisfaction problems (CSP). In particular, various arc-consistency algorithms have been designed such as the time optimal AC-4 sequential algorithm of Mohr and Henderson (1986). In this paper, we present a new distributed arc-consistency algorithm, called DisAC-4. DisAC-4 is based on AC-4, and is a coarse-grained parallel algorithm designed for distributed memory computers using message passing communication. Termination and correctness of the algorithm are proven. Theoretical complexities and experimental results are given. Both show linear speedup with respect to the number of processors. The strong point of DisAC-4 is its suitability to be implemented on very common hardware infrastructures like networks of workstations and/or PCs as well as on intensive computing parallel mainframes.