A Tagging Method for Distributed Constraint Satisfaction

Local propagation algorithms such as Waltz' filtering and Mackworth's AC-x algorithms have been successfully applied in AI for solving constraint satisfaction problems (CSPs). In general, these algorithms can only be used as preprocessing methods as they do not compute a global consistent solution for a CSP; they result in local consistency also known as arc consistency. In this paper, we introduce an extension of local constraint propagation to overcome this drawback, i.e., to compute global consistent solutions for a CSP. The advantage over backtracking approaches is that the method introduced here is easy to implement on parallel machines with an arbitrary number of processors. The underlying idea is to associate recursive tags with the values during the propagation process so that global relationships among the values are maintained.

ICSI Technical Report TR-89-037

Technical Report