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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Angluin, D., Aspnes, J., Chan, M., Fischer, M.J., Jiang, H., Peralta, R.: Stably computable properties of network graphs. In: Prasanna, V.K., Iyengar, S., Spirakis, P., Welsh, M. (eds) Distributed Computing in Sensor Systems: First IEEE International Conference, DCOSS 2005, Marina del Rey, CA, USA, June/July, 2005, Proceedings, volume 3560 of Lecture Notes in Computer Science, pp. 63–74. Springer, Berlin (2005)
Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Urn automata. Technical Report YALEU/DCS/TR-1280, Yale University Department of Computer Science (2003)
Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. In: PODC ’04: Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, pp. 290–299. ACM, New York (2004)
Angluin D., Aspnes J., Diamadi Z., Fischer M.J. and Peralta R. (2006). Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18(4): 235–253
Angluin, D., Aspnes, J., Eisenstat, D.: Fast computation by population protocols with a leader. In: Distributed Computing: 20th International Symposium, DISC 2006: Stockholm, Sweden, September 2006: Proceedings, pp. 61–75 (2006)
Angluin, D., Aspnes, J., Eisenstat, D.: Stably computable predicates are semilinear. In: Proceedings of the 25th ACM Symposium on Principles of Distributed Computing, pp. 292–299 (2006)
Angluin, D., Aspnes, J., Eisenstat, D., Ruppert, E.: On the power of anonymous one-way communication. In: Principles of Distributed Systems; 9th International Conference, OPODIS 2005; Pisa, Italy; December 2005; Revised Selected Papers, volume 3974 of Lecture Notes in Computer Science, pp. 396–411 (2005)
Angluin, D., Aspnes, J., Fischer, M.J., Jiang, H.: Self-stabilizing population protocols. In: Principles of Distributed Systems; 9th International Conference, OPODIS 2005; Pisa, Italy; December 2005; Revised Selected Papers, volume 3974 of Lecture Notes in Computer Science. pp. 103–117 (2005)
Angluin, D., Fischer, M.J., Jiang, H.: Stabilizing consensus in mobile networks. In: Proceedings of Distributed Computing in Sensor Systems: Second IEEE International Conference, volume 4026 of Lecture Notes in Computer Science, pp. 37–50 (2006)
Attiya H., Gorbach A. and Moran S. (2002). Computing in totally anonymous asynchronous shared memory systems. Inform. Comput. 173(2): 162–183
Angluin, D.: Local and global properties in networks of processors. In: Proceedings of the 12th ACM Symposium on Theory of Computing, pp. 82–93 (1980)
Aspnes, J., Shah, G., Shah, J.: Wait-free consensus with infinite arrivals. In: Proceedings of the 34th ACM Symposium on Theory of Computing, pp. 524–533 (2002)
Bailey N.T.J. (1975). The Mathematical Theory of Infectious Diseases, Second Edition. Charles Griffin & Co., London
Buhrman H. (2006). Alessandro Panconesi, Riccardo Silvestri and Paul Vitanyi. On the importance of having an identity or, is consensus really universal?. Distrib. Comput. 18(3): 167–176
Boldi, P., Vigna, S.: Computing anonymously with arbitrary knowledge. In: Proceedings of the 18th ACM Symposium on Principles of Distributed Computing, pp. 173–179 (1999)
Boldi, P., Vigna, S.: An effective characterization of computability in anonymous networks. In: Distributed Computing, 15th International Conference, pp. 33–47 (2001)
Diamadi, Z., Fischer, M.J.: A simple game for the study of trust in distributed systems. Wuhan Univ. J. Natural Sci. 6(1–2), 72–82 (2001). Also appears as Yale Technical Report TR–1207, January 2001
Delporte-Gallet, C., Fauconnier, H., Guerraoui, R., Ruppert, E.: When birds die: Making population protocols fault-tolerant. In: Proceedings of the Second IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS ’06), pp. 51–66 (2006)
Dickson L.E. (1913). Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors. Am. J. Math. 35(4): 413–422
Daley D.J. and Kendall D.G. (1965). Stochastic rumours. J. Inst. Math. Appl. 1: 42–55
Eğecioğlu Ö. and Singh A.K. (1994). Naming symmetric processes using shared variables. Distrib. Comput. 8(1): 19–38
Fischer, M.J., Jiang, H.: Self-stabilizing leader election in networks of finite-state anonymous agents. In: Tenth International Conference on Principles of Distributed Systems, volume 4305 of Lecture Notes in Computer Science, pp. 395–409 (2006)
Fich F. and Ruppert E. (2003). Hundreds of impossibility results for distributed computing. Distrib. Comput. 16(2–3): 121–163
Gibson M.A. and Bruck J. (2000). Efficient exact stochastic simulation of chemical systems with many species and many channels. J. Phys. Chem. A 104: 1876–1880
Gillespie D.T. (1992). A rigorous derivation of the chemical master equation. Physica A 188: 404–425
Guerraoui, R., Ruppert, E.: Anonymous and fault-tolerant shared-memory computing. Distrib. Comput. (2007, in press)
Higman G. (1952). Ordering by divisibility in abstract algebras. Proc. Lond. Math. Soc. 3(2): 326–336
Hopcroft J. and Pansiot J. (1978). On the reachability problem for 5-dimensional vector addition systems. Theoret. Comput. Sci. 8(2): 135–159
Ibarra O.H., Dang Z. and Egecioglu O. (2004). Catalytic P systems, semilinear sets, and vector addition systems. Theor. Comput. Sci. 312(2–3): 379–399
Jiang, H.: Distributed Systems of Simple Interacting Agents. PhD thesis, Yale University (2007)
Jayanti, P., Toueg, S.: Wakeup under read/write atomicity. In: Distributed Algorithms, 4th International Workshop, volume 486 of LNCS, pp. 277–288 (1990)
Kutten S., Ostrovsky R. and Patt-Shamir B. (2000). The Las-Vegas processor identity problem (How and when to be unique). J. Algorithms 37(2): 468–494
Lang S. (2002). Algebra (revised third edition). Springer, Berlin
Lay, S.R.: Convex Sets and their Applications. Krieger Publishing Company, (1992)
Lipton R.J. and Park A. (1990). The processor identity problem. Inform. Process. Lett. 36(2): 91–94
Parikh R.J. (1966). On context-free languages. J. ACM 13(4): 570–581
Panconesi A., Papatriantafilou M., Tsigas P. and Vitányi P. (1998). Randomized naming using wait-free shared variables. Distrib. Comput. 11(3): 113–124
Presburger, M.: Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. In: Comptes-Rendus du I Congrès de Mathématiciens des Pays Slaves, pp. 92–101, Warszawa (1929)
Sakamoto, N.: Comparison of initial conditions for distributed algorithms on anonymous networks. In: Proc. 18th ACM Symposium on Principles of Distributed Computing, pp. 173–179 (1999)
Teng S.-H. (1990). Space efficient processor identity protocol. Inform. Process. Lett. 34(3): 147–154
Author information
Authors and Affiliations
Corresponding author
Additional information
James Aspnes was supported in part by NSF grants CNS-0305258 and CNS-0435201.
David Eisenstat was supported in part by a National Defense Science and Engineering Graduate Fellowship and by a Gordon Y. S. Wu Graduate Fellowship.
Eric Ruppert was supported in part by the Natural Sciences and Engineering Research Council of Canada.
Rights and permissions
About this article
Cite this article
Angluin, D., Aspnes, J., Eisenstat, D. et al. The computational power of population protocols. Distrib. Comput. 20, 279–304 (2007). https://doi.org/10.1007/s00446-007-0040-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00446-007-0040-2