Self-stabilizing population of mobile agents

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.