Population Stability: Regulating Size in the Presence of an Adversary
Adam Sealfon, Massachusetts Institute of Technology
Consider a system of agents, each with limited memory and communication and with the ability to replicate and self-destruct, that is subjected to continual attacks from an adversary that at bounded rate can delete or insert agents into the system. We study the problem of perpetually maintaining a population whose size is close to the target size N. This coordination problem is inspired by the ability of complex biological systems composed of a multitude of memory-limited individual cells to maintain a stable population size in an adverse environment. Such biological mechanisms allow organisms to heal after trauma or to recover from excessive cell proliferation caused by inflammation, disease or normal development.
We present a protocol for achieving population stability in a variant of the population model of Angluin <em>et al</em> (PODC, 2004). Our protocol uses three-bit messages and slightly more than log<sub>2</sub> N states per agent. The protocol relies on a novel coloring strategy in which the population size is encoded in the variance of the distribution of colors. Individual agents can locally obtain a weak estimate of the population size by sampling from the distribution and make individual decisions that robustly maintain a stable global population size.
Abstract Author(s): Shafi Goldwasser, Rafael Ostrovsky, Alessandra Scafuro, Adam Sealfon