Book Chapter

Dynamic Distributed BackJumping

We consider Distributed Constraint Satisfaction Problems (DisCSP) when control of variables and constraints is distributed among a set of agents. This paper presents a distributed version of the centralized BackJumping algorithm, called the {
it Dynamic Distributed BackJumping} -
algoname{DDBJ} algorithm. The advantage is twofold:
algoname{DDBJ} inherits the strength of synchronous algorithms that enables it to easily combine with a powerful dynamic ordering of variables and values, and still it maintains some level of autonomy for the agents. Experimental results show that
algoname{DDBJ} outperforms the
algoname{DiDB} and
algoname{AFC} algorithms by a factor of {
it one to two} orders of magnitude on hard instances of randomly generated DisCSPs.


    Lecture Notes in Computer Science Series


    CSCLP04, Lausanne, Switzerland, 2004


    Record created on 2006-12-07, modified on 2016-08-08

Related material


EPFL authors