Document Open Access Logo

The Effect of Asynchronous Execution and Message Latency on Max-Sum

Authors Roie Zivan , Omer Perry , Ben Rachmut , William Yeoh

PDF
Thumbnail PDF

File

LIPIcs.CP.2021.60.pdf
  • Filesize: 1.23 MB
  • 18 pages

Document Identifiers

Author Details

Roie Zivan
  • Ben Gurion University of the Negev, Beer Sheva, Israel
Omer Perry
  • Ben Gurion University of the Negev, Beer Sheva, Israel
Ben Rachmut
  • Ben Gurion University of the Negev, Beer Sheva, Israel
William Yeoh
  • Washington University in Saint Louis, MO, USA

Funding

This research is partially supported by US-Israel Binational Science Foundation (BSF) grant #2018081 and US National Science Foundation (NSF) grant #1838364.

Cite As Get BibTex

Roie Zivan, Omer Perry, Ben Rachmut, and William Yeoh. The Effect of Asynchronous Execution and Message Latency on Max-Sum. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 60:1-60:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CP.2021.60

Abstract

Max-sum is a version of belief propagation that was adapted for solving distributed constraint optimization problems (DCOPs). It has been studied theoretically and empirically, extended to versions that improve solution quality and converge rapidly, and is applicable to multiple distributed applications. The algorithm was presented both as a synchronous and an asynchronous algorithm, however, neither the differences in the performance of these two execution versions nor the implications of message latency on the two versions have been investigated to the best of our knowledge. 
We contribute to the body of knowledge on Max-sum by: (1) Establishing the theoretical differences between the two execution versions of the algorithm, focusing on the construction of beliefs; (2) Empirically evaluating the differences between the solutions generated by the two versions of the algorithm, with and without message latency; and (3) Establishing both theoretically and empirically the positive effect of damping on reducing the differences between the two versions. Our results indicate that in contrast to recent published results indicating the drastic effect that message latency has on distributed local search, damped Max-sum is robust to message latency.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Theory of computation → Constraint and logic programming
Keywords
  • Distributed constraints
  • Distributed problem solving

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Andy Bubune Amewuda, Ferdinand Apietu Katsriku, and Jamal-Deen Abdulai. Implementation and evaluation of wlan 802.11ac for residential networks in ns-3. Journal of Computer Networks and Communications, 2018, 2018. Google Scholar
  2. Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286(5439):509-512, 1999. Google Scholar
  3. Ziyu Chen, Yanchen Deng, Tengfei Wu, and Zhongshi He. A class of iterative refined max-sum algorithms via non-consecutive value propagation strategies. Auton. Agents Multi Agent Syst., 32(6):822-860, 2018. Google Scholar
  4. Liel Cohen, Rotem Galiki, and Roie Zivan. Governing convergence of max-sum on dcops through damping and splitting. Artificial Intelligence Journal (AIJ), 279, 2020. Google Scholar
  5. Yanchen Deng and Bo An. Speeding up incomplete gdl-based algorithms for multi-agent optimization with dense local utilities. In Proceedings of the 29th International Joint Conference on Artificial Intelligence, (IJCAI), pages 31-38, 2020. Google Scholar
  6. A. Farinelli, A. Rogers, A. Petcu, and N. R. Jennings. Decentralised coordination of low-power embedded devices using the max-sum algorithm. In Proceeding of the 7th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 639-646, 2008. Google Scholar
  7. Alessandro Farinelli, Alex Rogers, and Nick R. Jennings. Agent-based decentralised coordination for sensor networks using the max-sum algorithm. Journal of Autonomous Agents and Multi-Agent Systems (JAAMAS), 28(3):337-380, 2014. Google Scholar
  8. G David Forney, Frank R Kschischang, Brian Marcus, and Selim Tuncel. Iterative decoding of tail-biting trellises and connections with symbolic dynamics. In Brian Marcus and Joachim Rosenthal, editors, Codes, Systems, and Graphical Models, pages 239-264. Springer, 2001. Google Scholar
  9. C. Kiekintveld, Z. Yin, A. Kumar, and M. Tambe. Asynchronous algorithms for approximate distributed constraint optimization with quality bounds. In AAMAS, pages 133-140, 2010. Google Scholar
  10. F. R. Kschischang, B. J. Frey, and H. A. Loeliger. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 47:2:181-208, 2001. Google Scholar
  11. Radu Marinescu and Rina Dechter. AND/OR branch-and-bound search for combinatorial optimization in graphical models. Artif. Intell., 173(16-17):1457-1491, 2009. Google Scholar
  12. Lesly Mayuga-Marcillo, Luis Urquiza-Aguiar, and Martha Paredes-Paredes. Wireless channel 802.11 in ns-3, 2018. Google Scholar
  13. P. J. Modi, W. Shen, M. Tambe, and M. Yokoo. Adopt: asynchronous distributed constraints optimizationwith quality guarantees. Artificial Intelligence Journal (AIJ), 161:1-2:149-180, 2005. Google Scholar
  14. Arnon Netzer, Alon Grubshtein, and Amnon Meisels. Concurrent forward bounding for distributed constraint optimization problems. Artificial Intelligence Journal (AIJ), 193:186-216, 2012. Google Scholar
  15. Duc Thien Nguyen, William Yeoh, Hoong Chuin Lau, and Roie Zivan. Distributed Gibbs: A linear-space sampling-based DCOP algorithm. Journal of Artificial Intelligence Resesrch, 64:705-748, 2019. Google Scholar
  16. J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Francisco, California, 1988. Google Scholar
  17. A. Petcu and B. Faltings. A scalable method for multiagent constraint optimization. In Proceedings of the 21st International Joint Conference on Artificial Intelligence, (IJCAI), pages 266-271, 2005. URL: http://www.ijcai.org/papers/0445.pdf.
  18. Ben Rachmut, Roie Zivan, and William Yeoh. Latency-aware local search for distributed constraint optimization. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, pages 1019-1027, 2021. Google Scholar
  19. S. D. Ramchurn, A. Farinelli, K. S. Macarthur, and N. R. Jennings. Decentralized coordination in robocup rescue. Computer J., 53(9):1447-1461, 2010. Google Scholar
  20. Nicholas Ruozzi and Sekhar Tatikonda. Message-passing algorithms: Reparameterizations and splittings. IEEE Trans. Information Theory, 59(9):5860-5881, 2013. Google Scholar
  21. Pierre Rust, Gauthier Picard, and Fano Ramparany. Using message-passing DCOP algorithms to solve energy-efficient smart environment configuration problems. In Proceedings of the 25th International Joint Conference on Artificial Intelligence, (IJCAI), pages 468-474, 2016. Google Scholar
  22. R. Stranders, A. Farinelli, A. Rogers, and N. R. Jennings. Decentralised coordination of mobile sensors using the max-sum algorithm. In Proceedings of the 21st International Joint Conference on Artificial Intelligence, (IJCAI), pages 299-304, 2009. Google Scholar
  23. W. T. Luke Teacy, Alessandro Farinelli, N. J. Grabham, Paritosh Padhy, Alex Rogers, and Nicholas R. Jennings. Max-sum decentralized coordination for sensor systems. In Proceeding of the 7th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 1697-1698, 2008. Google Scholar
  24. Yair Weiss. Correctness of local probability propagation in graphical models with loops. Neural Computation, 12(1):1-41, 2000. Google Scholar
  25. Chen Yanover, Talya Meltzer, and Yair Weiss. Linear programming relaxations and belief propagation - an empirical study. Journal of Machine Learning Research, 7:1887-1907, 2006. Google Scholar
  26. William Yeoh, Ariel Felner, and Sven Koenig. BnB-ADOPT: An asynchronous branch-and-bound DCOP algorithm. Journal of Artificial Intelligence Research, 38:85-133, 2010. Google Scholar
  27. W. Zhang, Z. Xing, G. Wang, and L. Wittenburg. Distributed stochastic search and distributed breakout: properties, comparishon and applications to constraints optimization problems in sensor networks. Artificial Intelligence, 161:1-2:55-88, January 2005. Google Scholar
  28. Roie Zivan, Omer Lev, and Rotem Galiki. Beyond trees: Analysis and convergence of belief propagation in graphs with multiple cycles. In Proceedings of the 34th International Conference of the Association for the Advancement of Artificial Intelligence (AAAI), pages 7333-7340, 2020. Google Scholar
  29. Roie Zivan and Amnon Meisels. Message delay and discsp search algorithms. Annals of Mathematics and Artificial Intelligence (AMAI), 46:415-439, 2006. Google Scholar
  30. Roie Zivan, Tomer Parash, Liel Cohen, Hilla Peled, and Steven Okamoto. Balancing exploration and exploitation in incomplete min/max-sum inference for distributed constraint optimization. Journal of Autonomous Agents and Multi-Agent Systems (JAAMAS), 31(5):1165-1207, 2017. Google Scholar
  31. Roie Zivan, Tomer Parash, Liel Cohen-Lavi, and Yarden Naveh. Applying max-sum to asymmetric distributed constraint optimization problems. Journal of Autonomous Agents and Multi Agent Systems (JAAMAS), 34(1):13, 2020. Google Scholar
  32. Roie Zivan, Tomer Parash, and Yarden Naveh. Applying max-sum to asymmetric distributed constraint optimization. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, pages 432-439, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact