Support-based
Distributed Search
Peter Harvey, Chee Fon Chang, and
Aditya Ghose
Abstract
Algorithms for Distributed Constraint Satisfaction Problems have tended
to mirror existing non-distributed global-search or localsearch
algorithms. Unfortunately, existing distributed global-search
algorithms derive from classical backtracking search methods and
require a total ordering over variables for completeness. Distributed
variants of local-search algorithms (such as distributed breakout)
inherit the incompleteness properties of their predecessors. We will
provide an example of a naturally-occurring DisCSP where a global
ordering is di cult to maintain and creates undesirable behaviours. We
will present an algorithm which blends local and global search in such
a way that a global ordering is not required. It demonstrates a new
direction for DisCSP research, avoiding any notion of
authority between variables while appearing to achieve
completeness.