Algorithms in open multi-agent systems : gossiping with random replacements

A multi-agent system is a loosely coupled network of problem solving entities (agents) that work together to find answers to problems that are beyond the scope of the individual capabilities of each entity. Such systems already represent an established and promising research and application field. The absence of a central controller coordinating the tasks leads indeed to interesting advantages such as the robustness and scalability. Two reasons to cause people to study multi-agent systems are the technological and application needs and the natural view of intelligent systems. In this master thesis, we consider open multi-agent systems such that the agents can join or leave the system. We focus here on the scenario where the leaving agents are immediately replaced, leading to a constant size of the systems. The objective of this master thesis is firstly to analyze and evaluate two algorithms meant to solve the average seeking through pairwise gossips in such system: on the one hand, there is the uncorrected gossip strategy where the leaving agents do not announce their departure, and on the other hand, the last message strategy where the agents send a well chosen last message to a random agent in the system in order to avoid the loss of information due to a replacement. Secondly, given undesired characteristics of both algorithms, there comes the will to design a strategy that would erase them.