The computational power of population protocols
By Dana Angluin, James Aspnes, David Eisenstat, Eric Ruppert. Distributed computing, 2006
312 citations recorded by the source corpus.
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.
Subfields: Biomedical Engineering, Computational Theory and Mathematics, Computer Networks and Communications
View Paper: https://www.semanticscholar.org/paper/026a0f721c6e95ca2db9e52df215ab1078b1e7fa
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Biomedical Engineering
In Computational Theory and Mathematics
In Computer Networks and Communications
- Amirmojtaba Sabour
- Vitaly Aksenov
- Nicola Santoro
- Walter Quattrociocchi
- A. Casteigts
- Paola Flocchini
- Aditya Sharma
- Giorgi Nadiradze
Citations in the corpus
- PopSGD: Decentralized Stochastic Gradient Descent in the Population Model (2019, background): “Population protocols have a rich history in distributed computing (e.g. [8, 11, 10, 9, 12, 4, 5]), and are standard in modelling distributed systems with millions or billions of nodes, such as Chemical Reaction Networks (CRNs) [16, 18] and synthetic DNA strand displacement cascades [20].”
- Time-varying graphs and dynamic networks (2010, background): “, one of the TVG classes considered here coincides with the family of dynamic graphs over which population protocols ([2, 3]) are defined.”