  We consider the model of population protocols introduced by Angluin et al.,
in which anonymous finite-state agents stably compute a predicate of the
multiset of their inputs via two-way interactions in the all-pairs family of
communication networks. We prove that all predicates stably computable in this
model (and certain generalizations of it) are semilinear, answering a central
open question about the power of the model. Removing the assumption of two-way
interaction, we also consider several variants of the model in which agents
communicate by anonymous message-passing where the recipient of each message is
chosen by an adversary and the sender is not identified to the recipient. These
one-way models are distinguished by whether messages are delivered immediately
or after a delay, whether a sender can record that it has sent a message, and
whether a recipient can queue incoming messages, refusing to accept new
messages until it has had a chance to send out messages of its own. We
characterize the classes of predicates stably computable in each of these
one-way models using natural subclasses of the semilinear predicates.
