1 Search Results for "Zivan, Roie"

Document
DOI: 10.4230/LIPIcs.CP.2021.60
The Effect of Asynchronous Execution and Message Latency on Max-Sum

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

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{zivan_et_al:LIPIcs.CP.2021.60,
  author =	{Zivan, Roie and Perry, Omer and Rachmut, Ben and Yeoh, William},
  title =	{{The Effect of Asynchronous Execution and Message Latency on Max-Sum}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{60:1--60:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.60},
  URN =		{urn:nbn:de:0030-drops-153518},
  doi =		{10.4230/LIPIcs.CP.2021.60},
  annote =	{Keywords: Distributed constraints, Distributed problem solving}
}
  • Refine by Author
  • 1 Perry, Omer
  • 1 Rachmut, Ben
  • 1 Yeoh, William
  • 1 Zivan, Roie

  • Refine by Classification
  • 1 Theory of computation → Constraint and logic programming
  • 1 Theory of computation → Distributed algorithms

  • Refine by Keyword
  • 1 Distributed constraints
  • 1 Distributed problem solving

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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 Imprint Privacy Contact