With the dissemination of aordable parallel and distributed hardware, parallel and distributed constraint solving has lately been the focus of some attention. To eectually apply the power of distributed computational systems, there must be an eective sharing of the work involved in the search for a solution to a Constraint Satisfaction Problem (CSP) between all the participating agents, and it must happen dynami- cally, since it is hard to predict the eort associated with the exploration of some part of the search space. We describe and provide an experimen- tal assessment of an implementation of a work stealing-based approach to parallel CSP solving in a distributed setting.
The most popular architecture for parallel search is work stealing: threads that have run out of work (nodes to be searched) steal from threads that still have work. Work stealing not only allows for dynamic load balancing, but also determines which parts of the search tree are searched next. Thus the place from where work is stolen has a dramatic effect on the efficiency of a parallel search algorithm. This paper examines quantitatively how optimal work stealing can be performed given an estimate of the relative solution densities of the subtrees at each search tree node and relates it to the branching heuristic strength. An adaptive work stealing algorithm is presented that automatically performs different work stealing strategies based on the confidence of the branching heuristic at each node. Many parallel depth-first search patterns arise naturally from this algorithm. The algorithm produces near perfect or super linear algorithmic efficiencies on all problems tested. Real speedups using 8 threads range from 7 times to super linear. A distributed concurrent search algorithm for distributed constraint satisfaction problems (DisCSPs) is presented. Concurrent search algorithms are composed of multiple search processes (SPs) that operate concurrently and scan non-intersecting parts of the global search space. Each SP is represented by a unique data structure, containing a current partial assignment (CPA), that is circulated among the different agents. Search processes are generated dynamically, started by the initializing agent, and by any number of agents during search.In the proposed, ConcDB, algorithm, all search processes perform dynamic backtracking. As a consequence of backjumping, a search space can be found unsolvable by a different search process. This enhances the efficiency of the ConcDB algorithm. Concurrent Dynamic Backtracking is an asynchronous distributed algorithm and is shown to be faster than former algorithms for solving DisCSPs. Experimental evaluation of ConcDB, on randomly generated DisCSPs demonstrates that the network load of ConcDB is similar to the network load of synchronous backtracking and is much lower than that of asynchronous backtracking. The advantage of Concurrent Search is more pronounced in the presence of imperfect communication, when messages are randomly delayed. Program parallelization and distribution becomes increasingly important when new multi-core architectures and cheaper cluster technology provide ways to improve performance. Using declarative languages, such as constraint programming, can make the transition to parallelism easier for the programmer. In this paper, we address parallel and distributed search in constraint programming (CP) by proposing several load-balancing methods. We show how these methods improve the execution-time scalability of constraint programs. Scalability is the greatest challenge of parallelism and it is particularly an issue in constraint programming, where load-balancing is difficult. We address this problem by proposing CP-specific load-balancing methods and evaluating them on a cluster by using benchmark problems. Our experimental results show that the methods behave differently well depending on the type of problem and the type of search. This gives the programmer the opportunity to optimize the performance for a particular problem. 