James Aspnes and Eric Ruppert. An introduction to population protocols. Bulletin of the European Association for Theoretical Computer Science, Distributed Computing Column, 93:98–117, October 2007. An updated and extended version appears in Middleware for Network Eccentric and Mobile Applications, Benoît Garbinato, Hugo Miranda, and Luís Rodrigues, eds., Springer-Verlag, 2009, pp. 97–120.
The population protocol model describes a collection of tiny mobile agents that interact with one another to carry out a computation. The agents are identically programmed finite state machines. Interactions between pairs of agents cause the two agents to update their states. These interactions are scheduled by an adversary, subject to a fairness constraint. Input values are initially distributed to the agents, and the agents must eventually converge to the correct output value. This framework can be used to model mobile ad hoc networks of tiny devices or collections of molecules undergoing chemical reactions. We survey results that describe what can be computed in various versions of the population protocol model.
@article{AspnesR2007,
author = {James Aspnes and Eric Ruppert},
title = {An introduction to population protocols},
journal = {Bulletin of the European Association for Theoretical Computer Science},
volume=93,
pages={98--117},
month=oct,
year = 2007}
@incollection{AspnesR2009,
author = {James Aspnes and Eric Ruppert},
title = {An introduction to population protocols},
booktitle = {Middleware for Network Eccentric and Mobile Applications},
editor = {Beno\^it Garbinato and Hugo Miranda and Lu\'is Rodrigues},
pages={97--120},
publisher = {Springer-Verlag},
year = 2009}