  Local consistencies stronger than arc consistency have received a lot of
attention since the early days of CSP research. %because of the strong pruning
they can achieve. However, they have not been widely adopted by CSP solvers.
This is because applying such consistencies can sometimes result in
considerably smaller search tree sizes and therefore in important speed-ups,
but in other cases the search space reduction may be small, causing severe run
time penalties. Taking advantage of recent advances in parallelization, we
propose a novel approach for the application of strong local consistencies
(SLCs) that can improve their performance by largely preserving the speed-ups
they offer in cases where they are successful, and eliminating the run time
penalties in cases where they are unsuccessful. This approach is presented in
the form of two search algorithms. Both algorithms consist of a master search
process, which is a typical CSP solver, and a number of slave processes, with
each one implementing a SLC method. The first algorithm runs the different SLCs
synchronously at each node of the search tree explored in the master process,
while the second one can run them asynchronously at different nodes of the
search tree. Experimental results demonstrate the benefits of the proposed
method.
