Communication and Computation in Distributed CSP Algorithms

dc.contributor.authorFernàndez Camon, César
dc.contributor.authorBéjar Torres, Ramón
dc.contributor.authorKrishnamachari, Bhaskar
dc.contributor.authorGomes, Carla
dc.date.accessioned2016-07-13T10:53:56Z
dc.date.issued2005
dc.description.abstractWe 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.ca_ES
dc.description.sponsorshipResearch supported by AFOSR, grant F49620-01-1-0076 (Intelligent Information Systems Institute) and F49620-01-1-0361 (MURI grant on Cooperative Control of Distributed Autonomous Vehicles in Adversarial Environments), CICYT, TIC2001- 1577-C03-03 and DARPA, F30602-00-2-0530 (Controlling Computational Cost: Structure, Phase Transitions and Randomization) and F30602-00-2-0558 (Configuring Wireless Transmission and Decentralized Data Processing for Generic Sensor Networks). The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of AFOSR, DARPA, or the U.S. Government.ca_ES
dc.identifier.doihttps://doi.org/10.1007/3-540-46135-3_44
dc.identifier.idgrec008218
dc.identifier.issn0302-9743
dc.identifier.urihttp://hdl.handle.net/10459.1/57610
dc.language.isoengca_ES
dc.publisherSpringer Verlagca_ES
dc.relationMICYT/PN2000-2003/TIC2001-1577-C03-03ca_ES
dc.relation.isformatofVersió postprint del document publicat a https://doi.org/10.1007/3-540-46135-3_44ca_ES
dc.relation.ispartofLecture Notes in Computer Science, 2005, vol. 2470, p. 664-679ca_ES
dc.rights(c) Springer-Verlag Berlin Heidelberg, 2005ca_ES
dc.rights.accessRightsinfo:eu-repo/semantics/openAccessca_ES
dc.titleCommunication and Computation in Distributed CSP Algorithmsca_ES
dc.typearticleca_ES
dc.type.versionacceptedVersionca_ES
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
008218.pdf
Size:
545.49 KB
Format:
Adobe Portable Document Format
Description:
Postprint
License bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description: