A. Ruiz-Andino, L. Araujo, F. Sáez, J. J. Ruz.

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.