@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}
}