Practical Application of Support-Based Distributed Search

P. Harvey, University of Wollongong
C. F. Chang, University of Wollongong
A. Ghose, University of Wollongong

Article comments

This article was originally published as: Harvey, P, Chang, CF & Ghose, A, Practical Application of Support-Based Distributed Search, 17th IEEE International Conference on Tools with Artificial Intelligence, 14-16 November 2005, 34-38. Copyright IEEE 2005.

Abstract

Algorithms for Distributed Constraint Satisfaction Problems have tended to mirror existing non-distributed global-search or local-search 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. A meeting scheduling problem translates to a DisCSP where a global ordering is difficult to maintain and creates undesirable behaviours. We present a practical demonstration of an algorithm in which a global ordering is not required, while avoiding the problems of local-search algorithms.