Effects of Mediator Selection Strategies for Distributed Constraint Satisfaction

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.