Stably computable predicates are semilinear

Dana Angluin, James Aspnes, and David Eisenstat. Stably computable predicates are semilinear. Twenty-Fifth ACM Symposium on Principles of Distributed Computing, July 2006, pp. 292–299.

Abstract

We consider the model of population protocols introduced by Angluin et. al., in which anonymous finite-state agents stably compute a predicate 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.

BibTeX

Download
@inproceedings{AngluinAE2006semilinear,
 author = {Dana Angluin and James Aspnes and David Eisenstat},
 title = {Stably computable predicates are semilinear},
 booktitle = {PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing},
 year = {2006},
 isbn = {1-59593-384-0},
 pages = {292--299},
 location = {Denver, Colorado, USA},
 doi = {http://doi.acm.org/10.1145/1146381.1146425},
 publisher = {ACM Press},
 address = {New York, NY, USA},
 }

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page