We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
The computational power of population protocols.
- Authors
Angluin, Dana; Aspnes, James; Eisenstat, David; Ruppert, Eric
- Abstract
We consider the model of population protocols introduced by Angluin et al. (Computation in networks of passively mobile finite-state sensors, pp. 290–299. ACM, New York, 2004), in which anonymous finite-state agents stably compute a predicate of the multiset of their inputs via two-way interactions in the family of all-pairs 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.
- Subjects
POPULATION; MOBILE communication systems; COMMUNICATION; TELECOMMUNICATION systems; COMMUNICATION policy
- Publication
Distributed Computing, 2007, Vol 20, Issue 4, p279
- ISSN
0178-2770
- Publication type
Article
- DOI
10.1007/s00446-007-0040-2