"State-copying and Recomputation in Parallel Constraint Programming  
with Global Constraints"

In this paper we discuss parallelization and distribution of problems  
modeled in a constraint programming (CP) framework, we focus on  
paralleization of depth first search (DFS) methods, since search is  
the most time-consuming task in CP. The current hardware development  
is moving towards multi-core processors and the cost of building  
distributed systems is shrinking. Hence, parallelization and  
distribution of constraint solvers is of increasing interest when  
trying to improve performance.

One of the most important issues that arises in parallel computing is  
load balancing, which requires a trade-off between processor load and  
communication. In this paper we present how reduced communication, at  
the cost of increased computation, can improve performance. Our  
experiments include global constraints, which are more powerful than  
binary constraints, but significantly more expensive to recompute.  
Our results show that recomputing data, rather than copying it, is  
faster even for problems that use global constraints. We also present  
a method for combining copying and recomputation to create an even  
more powerful communication model.