Self-stabilizing Population of Mobile Agents
 Zbigniew Golebiewski(1), Miroslaw Kutylowski(2), Tomasz Luczak(3), Filip Zagorski(4)

             (1) University of Wroclaw, (2) Wroclaw University of Technology, 
                    (3) Adam Mickiewicz University Poznan   
 
We investigate a problem of maintaining a target population of  mobile agents in 
a distributed system. The purpose of the agents is to perform certain activities, 
so the goal is to avoid overpopulation (leading to waste of resources) as well 
as underpopulation (resulting in a poor service). We assume that there must be 
no centralized control over the number of agents, since it might result in 
system's vulnerability. 

We analyze a simple protocol in which each node keeps at most one copy of an agent and 
if there is a single agent in a node, a new agent is born with a certain probability p. 
At each time step the agents migrate independently at random to chosen locations. 

We show that during a protocol execution the number of agents stabilizes around 
a level depending on p. We derive analytically simple formulas that determine 
probability p based on the target  fraction of nodes holding an agent.
The previous proposals of this type were based on experimental data  only. 

Keywords: mobile agents, worms, distributed computing, combinatorial analysis, stochastic analysis