A coordination-based framework for parallel constraint solving

In this talk, I will present a framework for the configuration of parallel constraint solvers. The framework is implemented in the Manifold coordination language, and provides coordination services to software components in four categories: domain types for the variables of a constraint satisfaction problem (CSP), (incomplete) constraint solvers that reduce the domains of CSP variables, schemes for splitting the domains of variables, and search strategies.

The coordination services implement a distributed constraint propagation algorithm, a distributed termination detection algorithm, and a mechanism for splitting the domains of CSP variables in order to facilitate search.

The constraint propagation algorithm applies (incomplete) solvers until none of the domains of the CSP variables can be reduced any further. In general, this will not lead to a solution to the CSP, and propagation has to be interleaved with splitting the domain of a variable in order to systematicaly search for solutions. Termination detection is needed because most obvious strategies will not want to consider splitting the domain of a variable until constraint propagation has finished.

In addition to the three algorithmic ingredients of a complete distributed solver that are implemented by the coordination services, we will discuss the component model of the framework, the set of components that are currently available, and the input language used for the configuration of solvers.  

hosted by