Synchronous vs asynchronous search on DisCSPs Academic Article uri icon


  • Distributed constraint satisfaction problems (¢ £ ¤ ¥ ¦ ¤) are com-posed of agents, each holding its variables, that are connected by constraints to variables of other agents. There are two known measures of performance for distributed search -the computational effort which represents the total search time and the number of messages sent which represents the network load. Due to the distributed nature of the problem, the behavior of the experimental envi-ronment is extremely important. However, most experimental studies have used a perfect simulator with instantaneous message delivery. The present paper inves-tigates two families of distributed search algorithms on DisCSPs, Synchronous and Asynchronous search. Improved versions of the two families of algorithms are presented and investigated. The performance of the algorithms of these two extended families is measured on randomly generated instances of DisCSPs. The results of the investigation are twofold. First, the delay of messages is found to de-teriorate the performance of asynchronous search by a large margin. This shows that a correct (and realistic) experimental scenario is important. Second, when messages are delayed, synchronous search performs better than asynchronous search in terms of computational effort as well as in network load. It turns out that asynchronous search fails to use its multiple computing power to an advan-tage.

publication date

  • December 1, 2003