A distributed algorithm solving CSPs with a low communication cost

We present a distributed algorithm which finds all solutions of constraint satisfaction problems. Based on the backtrack algorithm, it spreads subtrees of the search tree over processes running in parallel. The work is equitably shared among the processes while the communication cost remains low. We show that the speedup of the resolution is asymptotically linear as the number of variables increases.