SensorDCSP swMATH ID: 30992 Software Authors: Béjar, Ramón; Domshlak, Carmel; Fernández, Cèsar; Gomes, Carla; Krishnamachari, Bhaskar; Selman, Bart; Valls, Magda Description: Sensor networks and distributed CSP: communication, computation and complexity. 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), and perform performance comparison for these algorithms on both satisfiable and unsatisfiable instances of SensorDCSP. We found that random delays (due to network traffic or in some cases actively introduced by the agents) combined with a dynamic decentralized restart strategy can improve the performance of DisCSP algorithms. In addition, we introduce GSensorDCSP, a plain-embedded version of SensorDCSP that is closely related to various real-life dynamic tracking systems. We perform both analytical and empirical study of this benchmark domain. In particular, this benchmark allows us to study the attractiveness of solution repairing for solving a sequence of DisCSPs that represent the dynamic tracking of a set of moving objects. Homepage: https://www.sciencedirect.com/science/article/pii/S000437020400150X Keywords: distributed CSP benchmark; phase transitions; randomized combinatorial search; communication network delays; NP-completeness Related Software: DisChoco; CSPLib; PRMLT; Algorithm 97; CNCL; SATLIB Cited in: 4 Publications Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Sensor networks and distributed CSP: communication, computation and complexity. Zbl 1132.68688Béjar, Ramón; Domshlak, Carmel; Fernández, Cèsar; Gomes, Carla; Krishnamachari, Bhaskar; Selman, Bart; Valls, Magda 2005 all top 5 Cited by 15 Authors 2 Bessiere, Christian 2 Wahbi, Mohamed 1 Béjar, Ramón 1 Bouyakhf, El Houssine 1 Brown, Kenneth N. 1 Domshlak, Carmel 1 Ezzahir, Redouane 1 Fernández, César C. 1 Gomes, Carla P. 1 Krishnamachari, Bhaskar 1 Mechqrane, Younes 1 Meisels, Amnon 1 Selman, Bart 1 Valls, Magda 1 Zivan, Roie Cited in 3 Serials 2 Artificial Intelligence 1 Annals of Mathematics and Artificial Intelligence 1 Constraints Cited in 2 Fields 3 Computer science (68-XX) 1 Operations research, mathematical programming (90-XX) Citations by Year