{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T19:47:09Z","timestamp":1791316029473,"version":"4.3.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2007,8,23]],"date-time":"2007-08-23T00:00:00Z","timestamp":1187827200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2007,10,23]]},"DOI":"10.1007\/s00446-007-0040-2","type":"journal-article","created":{"date-parts":[[2007,8,22]],"date-time":"2007-08-22T17:46:56Z","timestamp":1187804816000},"page":"279-304","source":"Crossref","is-referenced-by-count":210,"title":["The computational power of population protocols"],"prefix":"10.1007","volume":"20","author":[{"given":"Dana","family":"Angluin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James","family":"Aspnes","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Eisenstat","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eric","family":"Ruppert","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2007,8,23]]},"reference":[{"key":"40_CR1","doi-asserted-by":"crossref","unstructured":"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\u201374. Springer, Berlin (2005)","DOI":"10.1007\/11502593_8"},{"key":"40_CR2","unstructured":"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)"},{"key":"40_CR3","doi-asserted-by":"crossref","unstructured":"Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. In: PODC \u201904: Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, pp. 290\u2013299. ACM, New York (2004)","DOI":"10.1145\/1011767.1011810"},{"issue":"4","key":"40_CR4","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/s00446-005-0138-3","volume":"18","author":"D. Angluin","year":"2006","unstructured":"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\u2013253","journal-title":"Distrib. Comput."},{"key":"40_CR5","doi-asserted-by":"crossref","unstructured":"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\u201375 (2006)","DOI":"10.1007\/11864219_5"},{"key":"40_CR6","doi-asserted-by":"crossref","unstructured":"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\u2013299 (2006)","DOI":"10.1145\/1146381.1146425"},{"key":"40_CR7","doi-asserted-by":"crossref","unstructured":"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\u2013411 (2005)","DOI":"10.1007\/11795490_30"},{"key":"40_CR8","doi-asserted-by":"crossref","unstructured":"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\u2013117 (2005)","DOI":"10.1007\/11795490_10"},{"key":"40_CR9","doi-asserted-by":"crossref","unstructured":"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\u201350 (2006)","DOI":"10.1007\/11776178_3"},{"issue":"2","key":"40_CR10","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1006\/inco.2001.3119","volume":"173","author":"H. Attiya","year":"2002","unstructured":"Attiya H., Gorbach A. and Moran S. (2002). Computing in totally anonymous asynchronous shared memory systems. Inform. Comput. 173(2): 162\u2013183","journal-title":"Inform. Comput."},{"key":"40_CR11","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processors. In: Proceedings of the 12th ACM Symposium on Theory of Computing, pp. 82\u201393 (1980)","DOI":"10.1145\/800141.804655"},{"key":"40_CR12","doi-asserted-by":"crossref","unstructured":"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\u2013533 (2002)","DOI":"10.1145\/509907.509983"},{"key":"40_CR13","volume-title":"The Mathematical Theory of Infectious Diseases, Second Edition","author":"N.T.J. Bailey","year":"1975","unstructured":"Bailey N.T.J. (1975). The Mathematical Theory of Infectious Diseases, Second Edition. Charles Griffin & Co., London"},{"issue":"3","key":"40_CR14","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/s00446-005-0121-z","volume":"18","author":"H. Buhrman","year":"2006","unstructured":"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\u2013176","journal-title":"Distrib. Comput."},{"key":"40_CR15","doi-asserted-by":"crossref","unstructured":"Boldi, P., Vigna, S.: Computing anonymously with arbitrary knowledge. In: Proceedings of the 18th ACM Symposium on Principles of Distributed Computing, pp. 173\u2013179 (1999)","DOI":"10.1145\/301308.301355"},{"key":"40_CR16","doi-asserted-by":"crossref","unstructured":"Boldi, P., Vigna, S.: An effective characterization of computability in anonymous networks. In: Distributed Computing, 15th International Conference, pp. 33\u201347 (2001)","DOI":"10.1007\/3-540-45414-4_3"},{"key":"40_CR17","doi-asserted-by":"crossref","unstructured":"Diamadi, Z., Fischer, M.J.: A simple game for the study of trust in distributed systems. Wuhan Univ. J. Natural Sci. 6(1\u20132), 72\u201382 (2001). Also appears as Yale Technical Report TR\u20131207, January 2001","DOI":"10.1007\/BF03160228"},{"key":"40_CR18","doi-asserted-by":"crossref","unstructured":"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 \u201906), pp. 51\u201366 (2006)","DOI":"10.1007\/11776178_4"},{"issue":"4","key":"40_CR19","doi-asserted-by":"crossref","first-page":"413","DOI":"10.2307\/2370405","volume":"35","author":"L.E. Dickson","year":"1913","unstructured":"Dickson L.E. (1913). Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors. Am. J. Math. 35(4): 413\u2013422","journal-title":"Am. J. Math."},{"key":"40_CR20","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1093\/imamat\/1.1.42","volume":"1","author":"D.J. Daley","year":"1965","unstructured":"Daley D.J. and Kendall D.G. (1965). Stochastic rumours. J. Inst. Math. Appl. 1: 42\u201355","journal-title":"J. Inst. Math. Appl."},{"issue":"1","key":"40_CR21","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF02283568","volume":"8","author":"\u00d6. E\u011fecio\u011flu","year":"1994","unstructured":"E\u011fecio\u011flu \u00d6. and Singh A.K. (1994). Naming symmetric processes using shared variables. Distrib. Comput. 8(1): 19\u201338","journal-title":"Distrib. Comput."},{"key":"40_CR22","doi-asserted-by":"crossref","unstructured":"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\u2013409 (2006)","DOI":"10.1007\/11945529_28"},{"issue":"2\u20133","key":"40_CR23","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/s00446-003-0091-y","volume":"16","author":"F. Fich","year":"2003","unstructured":"Fich F. and Ruppert E. (2003). Hundreds of impossibility results for distributed computing. Distrib. Comput. 16(2\u20133): 121\u2013163","journal-title":"Distrib. Comput."},{"key":"40_CR24","doi-asserted-by":"crossref","first-page":"1876","DOI":"10.1021\/jp993732q","volume":"104","author":"M.A. Gibson","year":"2000","unstructured":"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\u20131880","journal-title":"J. Phys. Chem. A"},{"key":"40_CR25","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1016\/0378-4371(92)90283-V","volume":"188","author":"D.T. Gillespie","year":"1992","unstructured":"Gillespie D.T. (1992). A rigorous derivation of the chemical master equation. Physica A 188: 404\u2013425","journal-title":"Physica A"},{"key":"40_CR26","doi-asserted-by":"crossref","unstructured":"Guerraoui, R., Ruppert, E.: Anonymous and fault-tolerant shared-memory computing. Distrib. Comput. (2007, in press)","DOI":"10.1007\/s00446-007-0042-0"},{"issue":"2","key":"40_CR27","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1112\/plms\/s3-2.1.326","volume":"3","author":"G. Higman","year":"1952","unstructured":"Higman G. (1952). Ordering by divisibility in abstract algebras. Proc. Lond. Math. Soc. 3(2): 326\u2013336","journal-title":"Proc. Lond. Math. Soc."},{"issue":"2","key":"40_CR28","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0304-3975(79)90041-0","volume":"8","author":"J. Hopcroft","year":"1978","unstructured":"Hopcroft J. and Pansiot J. (1978). On the reachability problem for 5-dimensional vector addition systems. Theoret. Comput. Sci. 8(2): 135\u2013159","journal-title":"Theoret. Comput. Sci."},{"issue":"2\u20133","key":"40_CR29","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/j.tcs.2003.10.028","volume":"312","author":"O.H. Ibarra","year":"2004","unstructured":"Ibarra O.H., Dang Z. and Egecioglu O. (2004). Catalytic P systems, semilinear sets, and vector addition systems. Theor. Comput. Sci. 312(2\u20133): 379\u2013399","journal-title":"Theor. Comput. Sci."},{"key":"40_CR30","unstructured":"Jiang, H.: Distributed Systems of Simple Interacting Agents. PhD thesis, Yale University (2007)"},{"key":"40_CR31","doi-asserted-by":"crossref","unstructured":"Jayanti, P., Toueg, S.: Wakeup under read\/write atomicity. In: Distributed Algorithms, 4th International Workshop, volume 486 of LNCS, pp. 277\u2013288 (1990)","DOI":"10.1007\/3-540-54099-7_19"},{"issue":"2","key":"40_CR32","doi-asserted-by":"crossref","first-page":"468","DOI":"10.1006\/jagm.2000.1110","volume":"37","author":"S. Kutten","year":"2000","unstructured":"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\u2013494","journal-title":"J. Algorithms"},{"key":"40_CR33","volume-title":"Algebra (revised third edition)","author":"S. Lang","year":"2002","unstructured":"Lang S. (2002). Algebra (revised third edition). Springer, Berlin"},{"key":"40_CR34","unstructured":"Lay, S.R.: Convex Sets and their Applications. Krieger Publishing Company, (1992)"},{"issue":"2","key":"40_CR35","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0020-0190(90)90103-5","volume":"36","author":"R.J. Lipton","year":"1990","unstructured":"Lipton R.J. and Park A. (1990). The processor identity problem. Inform. Process. Lett. 36(2): 91\u201394","journal-title":"Inform. Process. Lett."},{"issue":"4","key":"40_CR36","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"R.J. Parikh","year":"1966","unstructured":"Parikh R.J. (1966). On context-free languages. J. ACM 13(4): 570\u2013581","journal-title":"J. ACM"},{"issue":"3","key":"40_CR37","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/s004460050045","volume":"11","author":"A. Panconesi","year":"1998","unstructured":"Panconesi A., Papatriantafilou M., Tsigas P. and Vit\u00e1nyi P. (1998). Randomized naming using wait-free shared variables. Distrib. Comput. 11(3): 113\u2013124","journal-title":"Distrib. Comput."},{"key":"40_CR38","unstructured":"Presburger, M.: \u00dcber die Vollst\u00e4ndigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. In: Comptes-Rendus du I Congr\u00e8s de Math\u00e9maticiens des Pays Slaves, pp. 92\u2013101, Warszawa (1929)"},{"key":"40_CR39","doi-asserted-by":"crossref","unstructured":"Sakamoto, N.: Comparison of initial conditions for distributed algorithms on anonymous networks. In: Proc. 18th ACM Symposium on Principles of Distributed Computing, pp. 173\u2013179 (1999)","DOI":"10.1145\/301308.301352"},{"issue":"3","key":"40_CR40","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0020-0190(90)90094-E","volume":"34","author":"S.-H. Teng","year":"1990","unstructured":"Teng S.-H. (1990). Space efficient processor identity protocol. Inform. Process. Lett. 34(3): 147\u2013154","journal-title":"Inform. Process. Lett."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-007-0040-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-007-0040-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-007-0040-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:26:36Z","timestamp":1559136396000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-007-0040-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8,23]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,10,23]]}},"alternative-id":["40"],"URL":"https:\/\/doi.org\/10.1007\/s00446-007-0040-2","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,8,23]]}}}