Effects of Mediator Selection Strategies for Distributed
Constraint Satisfaction
Michael Benisch and Norman Sadeh
Abstract
Many successful algorithms, such as Asynchronous Partial
Overlay (APO), have recently been developed for cooperative distributed
problem solving based on the notion of coordinated mediation. In this
paper we examine the impact of different strategies for choosing
mediators with respect to the complexity of distributed problem solving
and the difficulty in merging decentralized solutions. We present
experimental results which challenge previously held beliefs suggesting
that the appointment of highly constrained agents leads to a decrease
in problem solving complexity. We show that, instead, choosing loosely
constrained agents as mediators in order to minimize the expected size
of mediation sessions can lead to an overall improvement in system
performance on problems with particular properties. Analysis with
respect to these properties is provided to explain the observed
improvement, and the analysis is confirmed experimentally.