Distributed singleton consistency
Ilias Sakellariou, Ioannis P. Vlahavas · Journal of Experimental & Theoretical Artificial Intelligence · 2004
Distributed constraint satisfaction has drawn much attention in the past years, with a number of algorithms proposed to tackle the problem. Research in the area has followed two directions: distributed search techniques and distributed filtering techniques. This paper presents a new distributed filtering algorithm, named Distributed Singleton Arc Consistency (Dis-SAC), which is based on the singleton consistency algorithm. Dis-SAC is a parallel, coarse-grain filtering algorithm aimed at improving the performance of singleton consistency by distributing the work to be done to a number of agents. The current paper presents the basic idea behind the algorithm and two versions of it that employ different communication policies along with experimental results obtained on a set of random binary CSP problems.