The computational power of population protocols
| dc.creator | Angluin, Dana | |
| dc.creator | Aspnes, James | |
| dc.creator | Eisenstat, David | |
| dc.creator | Ruppert, Eric | |
| dc.date | 2006-08-21 | |
| dc.date.accessioned | 2026-07-07T07:20:03Z | |
| dc.date.available | 2026-07-07T07:20:03Z | |
| dc.description | 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. | |
| dc.description | Combined version of OPODIS 2005 and PODC 2006 papers; submitted to Distributed Computing | |
| dc.identifier | https://arxiv.org/abs/cs/0608084 | |
| dc.identifier | http://arxiv.org/abs/cs/0608084 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/114846 | |
| dc.subject | Computational Complexity | |
| dc.subject | Distributed, Parallel, and Cluster Computing | |
| dc.title | The computational power of population protocols | |
| dc.type | text |