Population protocols (PP) is a model proposed recently for networks with a very large, possibly unknown, number of resource-limited mobile agents. Agents are sensors attached to animals, humans or some mobile apparatus. When two agents come close to each other, they can exchange information. The agents are asynchronous and move arbitrary. PP has certain advantages over alternative models of mobile agents (such as DTN). However, it was shown that the computational power of PP is rather limited.

We propose a model that extends the original PP by introducing a (weak) notion of "speed" of the agents. According to this notion, each agent is associated with a property called cover time. The cover time is an abstraction of agentâ'€'™s interaction/mobility characteristics such as physical speed, movement pattern, frequencies to visit different places or its communication range.

The extension by the notion of "speed" allows the design of fast converging protocols and the evaluation of their convergence time. This is impossible in the original model.

Using the new model, we study a basic problem in sensor networks - the problem of information gathering. Protocols are developed step by step when searching for an optimal solution, adapting to the size of the available agentsâ'€'™ memory, making protocols fault-tolerant and, in particular, self-stabilizing. In addition, a lower bound on the length of the worst case execution for any information gathering protocol is presented. Â' Next, a generic self-stabilizing transformer is developed. This is an automatic technique to convert a protocol to its self-stabilizing version. As a further extension and as another basic tool, a self-stabilizing phase-clock algorithm is developed. This is a synchronization tool that simulates logical time in an asynchronous system. It enables a protocol designer to organize a protocol execution into phases and thus, simplifies the designer's task.

Joint work with Shay Kutten (Technion, Israel) and Joffroy Beauquier (LRI, University Paris-Sud 11)