Synchronizing for Performance - DCOP Algorithms

Or Peri, Amnon Meisels

2013

Abstract

The last decade has given rise to a large variety of search algorithms for distributed constraints optimization problems (DCOPs). All of these distributed algorithms operate among agents in an asynchronous environment. The present paper presents a categorization of DCOP algorithms into several classes of synchronization. Algorithms of different classes of synchronization are shown to behave differently with respect to idle time of agents and to irrelevant computation. To enable the investigation of the relation between the classes of synchronization of algorithms and their run-time performance, one can control the asynchronous behavior of the multi-agent system by changing the amount of message delays. A preliminary probabilistic model for computing the expected performance of DCOP algorithms of different synchronization classes is presented. These expectations are realized in experiments on delayed message asynchronous systems. It turns out that the performance of algorithms of a weaker synchronization class deteriorates much more when the system becomes asynchronous than the performance of more synchronized DCOP algorithms. The notable exception is that concurrent algorithms, that run multiple search processes, are much more robust to message delays than all other DCOP algorithms.

Paper Citation

in Harvard Style

Peri O. and Meisels A. (2013). Synchronizing for Performance - DCOP Algorithms . In Proceedings of the 5th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART, ISBN 978-989-8565-38-9, pages 5-14. DOI: 10.5220/0004179100050014

in Bibtex Style

@conference{icaart13,
author={Or Peri and Amnon Meisels},
title={Synchronizing for Performance - DCOP Algorithms},
booktitle={Proceedings of the 5th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,},
year={2013},
pages={5-14},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004179100050014},
isbn={978-989-8565-38-9},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 5th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,
TI - Synchronizing for Performance - DCOP Algorithms
SN - 978-989-8565-38-9
AU - Peri O.
AU - Meisels A.
PY - 2013
SP - 5
EP - 14
DO - 10.5220/0004179100050014