Optimal Distributed Arc-Consistency

摘要

This paper presents DisAC-9, the first optimal distributed algorithm performing the arc-consistency of a constraint network. Our method is optimal according to the number of message passing operations. This algorithm can firstly, give speed-up over the fastest central arc-consistency algorithms; secondly, achieve the fast processing of distributed constraint satisfaction problems (DCSP). Experimental results include classical benchmark and large hard randoms problems. These results allow us to show that the phase transition phenomenon of distributed arc-consistency is closely related to the granularity of the distributed system. The consequences of this analysis are showed to be very important for the future of distributed constraint satisfaction.