Interleaved backtracking in distributed constraint networks

Abstract

The adaptation of software technology to distributed environments is an important challenge today. In this work we combine parallel and distributed search. By this way we add the potential speed-up of a parallel exploration in the processing of distributed problems. This paper extends DIBT a distributed search procedure operating in distributed constraint networks. The extension is twofold. First the procedure is updated to face delayed information problems upcoming in heterogeneous systems. Second, the search is extended to simultaneously explore independent parts of a distributed search tree. By this way we introduce parallelism into distributed search, which brings to interleaved distributed intelligent backtracking (IDIBT). Our results show that 1) insoluble problems do not greatly degrade performance over DIBT and 2) superlinear speed-up can be achieved when the distribution of solution is nonuniform.