We present in this paper a parallel execution model of arc-consistency
for Constraint Satisfaction Problems (CSP), implemented on a scaleable
MIMD distributed memory machine. We have adopted the indexical scheme,
an adequate approach to arc-consistency for functional constraints. The
CSP is partitioned into N partitions, which are executed in parallel
on N processors. Each processor applies sequential arc-consistency to
its subset of constraints, updating remote domains of variables shared
by any other processor.
The parallel algorithm we propose is embedded in the constraint solver
PCSOS (Parallel Constraint Satisfaction and Optimisation System). PCSOS
invokes the parallel arc-consistency algorithm when performing labelling
to obtain the solutions of a CSP. PCSOS is written in C, and it has been
developed and tested on a CRAY T3E distributed memory multiprocessor with
up to twenty-six processors. Results on speedup and behaviour of the system
are reported for the search of the first solution of different CSPs.