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.