
## 2 Background

The parallelisation of depth-first search has been the subject of much research in the past. The first papers on the subject study the distribution over various specific hardware architectures and investigate how to achieve good load balancing [13, 7]. Distributed solving of constraint problems specifically was first explored only a few years later [2].

Backtracking search in a distributed setting has also been investigated by several authors [12, 15]. A special variant for distributed scenarios, asynchronous backtracking, was proposed in [17]. Yokoo *et al* formalise the distributed constraint satisfaction problem and present algorithms for solving it [18].

Schulte presents the architecture of a system that uses networked computers [16]. The focus of his approach is to provide a high-level and reusable design for parallel search and achieve a good speedup compared to sequential solving rather than good resource utilisation. More recent papers have explored how to transparently parallelise search without having to modify existing code [10].

Most of the existing work is concerned with the problem of effectively distributing the workload such that every compute node is kept busy. The most prevalent technique used to achieve this is work stealing. The compute nodes communicate with each other and nodes which are idle request a part of the work that a busy node is doing. Blumofe and Leiserson propose and discuss a work stealing scheduler for multithreaded computations in [1]. Rolf and Kuchcinski investigate different algorithms for load balancing and work stealing in the specific context of distributed constraint solving [14].

Several frameworks for distributed constraint solving have been proposed and implemented, e.g. FRODO [11], DisChoco [3] and Disolver [6]. All of these approaches have in common that the systems to solve constraint problems are modified or augmented to support distribution of parts of the problem across and communication between multiple compute nodes. The constraint model of the problem remains unchanged however; no special constructs have to be used to take advantage of distributed solving. All parallelisation is handled in the respective solver. This does not preclude the use of an entirely different model of the problem to be solved for the distributed case in order to improve efficiency, but in general these solvers are able to solve the same model both with a single executor and distributed across several executors.

The decomposition of constraint problems into subproblems which can be solved independently has been proposed in [9], albeit in a different context. In this work, we explore the use of this technique for parallelisation. A similar approach was taken in [14], but requires parallelisation support in the solver.

## 3 Model Splitting

We now describe our new approach to the distributed solving of constraint problems which modifies the constraint solver to modify the constraint model and does not require explicit parallelisation support in the solver.