Synchronous vs Asynchronous search on DisCSPs
Roie Zivan, Amnon Meisels · 2003
Abstract. Distributed constraint satisfaction problems (DisCSP s) are composed 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 environment is extremely important. However, most experimental studies have used a perfect simulator with instantaneous message delivery. The present paper investigates 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 deteriorate 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 advantage. 1