Message delay and asynchronous discsp search Academic Article uri icon


  • Distributed constraint satisfaction problems (DisCSPs) are composed of agents, each holding its own variables, that are connected by constraints to vari-ables of other agents. Due to the distributed nature of the problem, message delay can have unexpected effects on the behavior of distributed search algorithms on DisCSPs. This has been shown in experimental studies of asynchronous back-tracking algorithms [1, 9]. To evaluate the impact of message delay on the run of DisCSP search algorithms, a model for distributed performance measures is presented. The model counts the number of non concurrent constraints checks, to arrive at a solution, as a non concurrent measure of distributed computation. A simpler version measures dis-tributed computation cost by the number of non-concurrent steps of computation. An algorithm for computing these distributed measures of computational effort is described. The realization of the model for measuring performance of distributed search algorithms is a simulator which includes the cost of message delays. The performance of two asynchronous search algorithms is measured on ran-domly generated instances of DisCSPs with delayed messages. The Asynchronous Weak Commitment (AW C) algorithm and Asynchronous Backtracking (ABT). The intrinsic reordering process of AW C dictates a need for a more complex count of non-concurrent steps of computation. The improved counting algorithm is also needed for Dynamic ordered ABT . The delay of messages is found to have a strong negative effect on AW C and a smaller effect on dynamically or-dered ABT .

publication date

  • January 1, 2006