Parallel and Distributed Algorithms for Constraint Networks

This paper develops two new algorithms for solving a finite constraint satisfaction problem (FCSP) in parallel. In particular, we give a parallel algorithm for the EREW PRAM model and a distributed algorithm for networks of interconnected processors. Both of these algorithms are derived from arc consistency algorithms which are preprocessing algorithms in general, but can be used to solve an FCSP when it is represented by an acyclic constraint network. If an FCSP can be represented by an acyclic constraint network of size n with width bounded by a constant then (1) the parallel algorithm takes O(log n) time using O(n) processors and (2) there is a mapping of this problem to a distributed computing network of poly(n) processors which stabilizes in O(log n) time.