More Web Proxy on the site http://driver.im/

research-article

Public Access

Solving DCSP problems in highly degraded communication environments

Authors:

Saeid Samadidana,

Roger MaillerAuthors Info & Claims

WI '17: Proceedings of the International Conference on Web Intelligence

Pages 348 - 355

https://doi.org/10.1145/3106426.3106445

Published: 23 August 2017 Publication History

Abstract

Although there have been tremendous gains in network communication reliability, many real world applications of distributed systems still face message loss, limitations, delay, and corruption. Yet despite this fact, most Distributed Constraint Satisfaction (DCSP) protocols assume that communication is perfect (messages that are sent will be received) although not ideal (not in a timely manner). As a result, many protocols are designed to exploit this assumption and are severely impacted when applied to real world conditions.

This study compares the performance of several leading DCSP protocols including the Distributed Stochastic Algorithm (DSA), Distributed Breakout Algorithm (DBA), Max-Gain Message (MGM) and Distributed Probabilistic Protocol (DPP) to analyse their behaviour in communication degraded environments. The analysis begins by comparing the performance of all of the protocols in a perfect communication environment. We then use a simulated communication degraded environment where messages are probabilistically lost. Finally, we compare their performance by limiting the communication rate, which introduces delay.

We show that DBA, once modified with a message timeout, is quite resistant to high message loss while DPP and DSA converge slower onto worse solutions. Our results also show that the setting of timeout value for DBA and MGM is an important factor in the convergence of these algorithms. Under conditions of message delay, DPP and DSA are less affected than DBA and MGM. Overall, DPP and DSA cause considerably less network load.

References

[1]

J. Braca, J. Bramel, B. Posner, and Simchi-Levi. 1997. A computerized approach to the New York Cityschool bus routing problem. IIE Transactions 29 (1997), 693--702. Issue 8.

[2]

A. R. Leite, F. Enembreck, and J.-P. A. Barthes. 2014. Distributed constraint optimization problems: Review and perspectives. Expert Systems with Applications (2014), 5139--5157.

[3]

Wahbi M., Ezzahir R., Bessiere C., Bouyakhf, and E.H. 2013. Nogood-Based Asynchronous Forward-Checking Algorithms. Constraints 18(3) (2013), 404--433.

Digital Library

[4]

R. T. Maheswaran, J. P. Pearce, and M. Tambe. D. 2004. Distributed algorithms for DCOP: A graphical-game-based approach. In Proc. Parallel and Distributed Computing Systems PDCS (September 2004), 432--439.

[5]

Roger Mailler. 2006. Using Prior Knowledge to Improve Distributed Hill Climbing. Proceedings of the IEEE/WIC/ACM international conference on Intelligent Agent Technology, 514--521.

Digital Library

[6]

R. Mailler and H. Zheng. 2014. A new analysis method for dynamic, distributed constraint satisfaction. In Proceedings of the 2014 International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS) 3, 901--908. Issue 1.

Digital Library

[7]

P.J. Modi, S.M. Ali, W. Shen, and M. Tambe. 2003. Distributed constraint reasoning under unreliable communication. Proceedings of Distributed Constraint Reasoning Workshop at Second International Joint Conference on Autonomous Agents and MultiAgent Systems.

[8]

R. Newton and W. Thomas. 1969. Design of school bus routes by computer. Socio-Economic Planning Sciences 3 (1969), 75--85. Issue 1.

[9]

J. Park and B. Kim. 2010. The school bus routing problem: a review. European Journal of Operational Research 202 (2010), 311--319. Issue 2.

[10]

Anton Ridgway and Roger Mailler. 2015. Dynamic Theoretical Analysis of the Distributed Stochastic and Distributed Breakout Algorithms. Proceedings of the 14th International Conference on Autonomous Agents and Multiagent System.

Digital Library

[11]

S. Samadidana, M.M Paydar, and Javid Jouzdani. 2017. A simulated annealing solution method for robust school bus routing. International Journal of Operational Research 28 (2017), 307--326. Issue 3.

[12]

Mohamed Wahbi and Kenneth N. Brown. 2014. The Impact of Wireless Communication on Distributed Constraint Satisfaction. In Proceedings of the 20th International Conference on Principles and Practice of Constraint Programming, 738--754.

[13]

Makoto Yokoo, Edmund H. Durfee, Toru Ishida, and Kazuhiro Kuwabara. 1992. Distributed constraint satisfaction for formalizing distributed problem solving. In International Conference on Distributed Computing Systems (1992), 614--621.

[14]

M. Yokoo and K.Hirayama. 1996. Distributed Breakout algorithm for solving distributed constraint satisfaction problems. International Conference on Multi-Agent Systems(ICMAS) (1996).

Digital Library

[15]

W. Zhang, G. Wang, and L.Wittenburg. 2002. Distributed stochastic search for constraint satisfaction and optimization:Parallelism, phase transitions and performance. In proceedings of the AAAI workshop on probabilistic Approaches in Search, 53--59.

Cited By

SamadiDana S(2021)Exploring the Effect of Noisy Environment on Distributed Problem Solving2021 IEEE 11th Annual Computing and Communication Workshop and Conference (CCWC)10.1109/CCWC51732.2021.9376129(0073-0080)Online publication date: 27-Jan-2021
https://doi.org/10.1109/CCWC51732.2021.9376129
Samadidana SMailler R(2019)Using Temporal Awareness to Improve Distributed Problem Solving2019 IEEE 9th Annual Computing and Communication Workshop and Conference (CCWC)10.1109/CCWC.2019.8666568(0342-0348)Online publication date: Jan-2019
https://doi.org/10.1109/CCWC.2019.8666568

Index Terms

Solving DCSP problems in highly degraded communication environments
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
      1. Multi-agent systems

Recommendations

Solving conditional and composite constraint satisfaction problems
SAC '07: Proceedings of the 2007 ACM symposium on Applied computing

Constraint Satisfaction Problems (CSPs) have been widely used to solve combinatorial problems. In order to deal with dynamic CSPs where the information regarding any possible change is known a priori and can thus be enumerated beforehand, conditional ...
A pre-processing algorithm for solving constraint satisfaction optimisation problems
SAICSIT '03: Proceedings of the 2003 annual research conference of the South African institute of computer scientists and information technologists on Enablement through technology

A constraint satisfaction problem (CSP) involves finding values, selected from a finite domain, for all variables such that all constraints on the variables are satisfied. A constraint satisfaction optimisation problem (CSOP) is a CSP that has some ...
Heuristics for Solving Fuzzy Constraint Satisfaction Problems
ANNES '95: Proceedings of the 2nd New Zealand Two-Stream International Conference on Artificial Neural Networks and Expert Systems

Work in the field of AI over the past twenty years has shown that many problems can be represented as constraint satisfaction problems and efficiently solved by constraint satisfaction algorithms. However, constraint satisfaction in its pure form isn't ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WI '17: Proceedings of the International Conference on Web Intelligence

August 2017

1284 pages

ISBN:9781450349512

DOI:10.1145/3106426

Conference Chair:
Amit Sheth
Wright State University GuoROLE@GENERAL CHAIR
,
General Chairs:
Axel Ngonga
Leipzig University, Germany
,
yin Wang
Chongqing University of Posts and Telecommunications, China
,
Elizabeth Chang
The University of New South Wales, Australia
,
Dominik Ślęzak
Infobright Inc. & University of Warsaw, Poland
,
Bogdan Franczyk
Leipzig University, Germany
,
Program Chairs:
Rainer Alt
Leipzig University, Germany
,
Xiaohui Tao
University of Southern Queensland, Australia

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAI: ACM Special Interest Group on Artificial Intelligence
TCII: IEEE Computer Society Technical Committee on Intelligent Informatics
Web Intelligence Consortium

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 August 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

WI '17

Sponsor:

SIGAI
TCII

WI '17: International Conference on Web Intelligence 2017

August 23 - 26, 2017

Leipzig, Germany

Acceptance Rates

WI '17 Paper Acceptance Rate 118 of 178 submissions, 66%;

Overall Acceptance Rate 118 of 178 submissions, 66%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
156
Total Downloads

Downloads (Last 12 months)36
Downloads (Last 6 weeks)7

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

SamadiDana S(2021)Exploring the Effect of Noisy Environment on Distributed Problem Solving2021 IEEE 11th Annual Computing and Communication Workshop and Conference (CCWC)10.1109/CCWC51732.2021.9376129(0073-0080)Online publication date: 27-Jan-2021
https://doi.org/10.1109/CCWC51732.2021.9376129
Samadidana SMailler R(2019)Using Temporal Awareness to Improve Distributed Problem Solving2019 IEEE 9th Annual Computing and Communication Workshop and Conference (CCWC)10.1109/CCWC.2019.8666568(0342-0348)Online publication date: Jan-2019
https://doi.org/10.1109/CCWC.2019.8666568

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents