Communication and Computation in Distributed CSP Algorithms
MetadataShow full item record
We introduce SensorDCSP, a naturally distributed benchmark based on a real-world application that arises in the context of networked distributed systems. In order to study the performance of Distributed CSP (DisCSP) algorithms in a truly distributed setting, we use a discrete-event network simulator, which allows us to model the impact of different network traffic conditions on the performance of the algorithms. We consider two complete DisCSP algorithms: asynchronous backtracking (ABT) and asynchronous weak commitment search (AWC). In our study of different network traffic distributions, we found that, random delays, in some cases combined with a dynamic decentralized restart strategy, can improve the performance of DisCSP algorithms. More interestingly, we also found that the active introduction of message delays by agents can improve performance and robustness, while reducing the overall network load. Finally, our work confirms that AWC performs better than ABT on satisfiable instances. However, on unsatisfiable instances, the performance of AWC is considerably worse than ABT.
Is part ofLecture Notes in Computer Science, 2005, vol. 2470, p. 664-679
European research projects
Showing items related by title, author, creator and subject.
Béjar Torres, Ramón; Domshlak, Carmel; Fernàndez Camon, César; Gomes, Carla; Krishnamachari, Bhaskar; Selman, Bart; Valls Marsal, Magda (Elsevier, 2005)We introduce SensorDCSP, a naturally distributed benchmark based on a real-world application that arises in the context of networked distributed systems. In order to study the performance of Distributed CSP (DisCSP) ...
Alsinet, Teresa; Ansótegui Gil, Carlos José; Béjar Torres, Ramón; Fernàndez Camon, César; Manyà Serres, Felip (Elsevier, 2003)The control of the right application of medical protocols is a key issue in hospital environments. For the automated monitoring of medical protocols, we need a domain-independent language for their representation and a ...
Mateu Piñol, Carles; Béjar Torres, Ramón; Fernàndez Camon, César (Springer, 2005)The goal of this work is to try to create a statistical model, based only on easily computable parameters from the CSP problem to predict runtime behaviour of the solving algorithms, and let us choose the best algorithm ...