Vidal's library
Title: Synchronous vs Asynchronous search on DisCSPs
Author: Roie Zivan and Amnon Meisels
Book Tittle: Proceedings of the First European Workshop on Multi-Agent Systems (EUMA)
Year: 2003
Abstract: Distributed constraint satisfaction problems (DisCSPs) 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.

Cited by 10  -  Google Scholar

@InProceedings{zivan03,
  author =	 {Roie Zivan and Amnon Meisels},
  title =	 {Synchronous vs Asynchronous search on {DisCSP}s},
  year =	 {2003},
  booktitle =	 {Proceedings of the First European Workshop on Multi-Agent Systems (EUMA)},
  abstract =	 {Distributed constraint satisfaction problems
                  (DisCSPs) 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. },
  keywords =     {multiagent dcsp distributed-search},
  url = 	 {http://jmvidal.cse.sc.edu/library/zivan03.pdf},
  googleid = 	 {0UaCeiCqudMJ:scholar.google.com/},
  cluster = 	 {15256412269165299409}
}
Last modified: Wed Mar 9 10:16:02 EST 2011