Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Issue title: Principles and Practice of Multi-Agent Systems
Guest editors: Michael Winikoffx, Nirmit Desaiy and Alan Liuz
Article type: Research Article
Authors: Mailler, Roger
Affiliations: Department of Computer Science, University of Tulsa, Tulsa, OK, USA. Tel.: +1 918 631 3140; Fax: +1 918 631 3077; E-mail: mailler@utulsa.edu | [x] Department of Information Science, University of Otago, Dunedin, New Zealand | [y] IBM Research, Bangalore, India | [z] Department of Electrical Engineering, National Chung Cheng University, Chiayi, Taiwan
Abstract: Dynamic, partial centralization has received a considerable amount of attention in the distributed problem solving community. As the name implies, this technique works by dynamically identifying portions of a shared problem to centralize in order to speed the problem solving process. Currently, a number of algorithms have been created which employ this simple, yet powerful technique to solve problems such as distributed constraint satisfaction (DCSP), distributed constraint optimization (DCOP), and distributed resource allocation. In fact, one such algorithm, Asynchronous Partial Overlay (APO), was shown to outperform the Asynchronous Weak Commitment (AWC) protocol, which is one of the best known methods for solving DCSPs. One of the key differences between these two algorithms is that APO, as part of the centralization process, uses explicit constraint passing. AWC, on the other hand, passed nogoods because it tries to provide security and privacy. Because of these differences in underlying assumptions, a number of researchers have criticized the comparison between these two protocols. This article attempts to resolve this disparity by introducing a new AWC/APO algorithm called Nogood-APO that like AWC uses nogood passing to provide privacy and like APO uses dynamic, partial centralization to speed the problem solving process. Like its parent algorithms, this new protocol is sound and complete and performs nearly as well as APO, while still outperforming AWC, on distributed 3-coloring problems. In addition, this paper shows that Nogood-APO provides more privacy to the agents than both APO and AWC on all but the sparsest problems. These findings demonstrate that a dynamic, partial centralization-based protocol can provide privacy and that even when operating with the same assumptions as AWC still solves problems in fewer cycles using less computation and communication.
Keywords: Distributed constraint satisfaction, cooperative mediation, dynamic partial centralization
DOI: 10.3233/MGS-2012-0191
Journal: Multiagent and Grid Systems , vol. 8, no. 2, pp. 165-186, 2012
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
sales@iospress.com
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
info@iospress.nl
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office info@iospress.nl
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
china@iospress.cn
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
如果您在出版方面需要帮助或有任何建, 件至: editorial@iospress.nl