Publication Details

This article was originally published as: Harvey, P., Chang, C. F. & 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.


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.



Link to publisher version (DOI)