HP Labs Technical Reports

An Adaptive Choice of Messaging Protocol in Multi- Agent Systems

Preist, Chris; Pearson, Siani

HPL-98-08

Keyword(s): decentralised systems; communication protocols

Abstract: There are a variety of choices which need to be made when setting up a multi-agent community. In particular, which agents communicate with which, what protocols they use, and what information flows from one to another. Such design choices will affect the efficiency of the community with respect to several parameters - accuracy, speed of solution, and message load. In this paper, we consider one class of problems in which multi-agent systems engage - service provision. Using a simple, abstract, form of this problem, we use a mathematical analysis to show that three different messaging protocols result in varying message loads, depending on certain parameters such as number of agents and frequency of request. If the parameters are fixed, we can conclude that one of these three protocols is better than the others. However, these parameters will usually vary over time, and hence the best of the three protocols will vary. We show that the community can adopt the best protocol if each individual agent makes a local decision based on which protocol will minimise its own message load. Hence, local decisions lead to globally good behaviour. We demonstrate this both mathematically and experimentally.

21 Pages

Back to Index