Distributed Singleton Consistency

I. Sakellariou, I. Vlahavas, “Distributed Singleton Consistency”, Journal of Experimental and Theoretical Artificial Intelligence, Taylor and Francis, 16(2), pp. 107-124, 2004.

Journal of Experimental and Theoretical Artificial Intelligence, Taylor and Francis, 16(2), pp. 107-124, 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 (DSAC), which is based on the singleton consistency algorithm. DSAC is a parallel coarse grain filtering algorithm aiming 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.