{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:39:27Z","timestamp":1742913567183,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642148484"},{"type":"electronic","value":"9783642148491"}],"license":[{"start":{"date-parts":[[2010,11,8]],"date-time":"2010-11-08T00:00:00Z","timestamp":1289174400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2010,11,8]],"date-time":"2010-11-08T00:00:00Z","timestamp":1289174400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-14849-1_5","type":"book-chapter","created":{"date-parts":[[2011,4,27]],"date-time":"2011-04-27T15:47:28Z","timestamp":1303919248000},"page":"109-159","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Population Protocols and Related Models"],"prefix":"10.1007","author":[{"given":"Paul G.","family":"Spirakis","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,11,8]]},"reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"D. Angluin, J. Aspnes, M. Chan, M. J. Fischer, H. Jiang, and R. Peralta. Stably computable properties of network graphs. In Proceedings Distributed Computing in Sensor Systems: 1st IEEE International Conference, pages 63\u201374, Marina del Ray, California, USA, 2005.","DOI":"10.1007\/11502593_8"},{"issue":"4","key":"5_CR2","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s00446-005-0138-3","volume":"18","author":"D. Angluin","year":"2006","unstructured":"D. Angluin, J. Aspnes, Z. Diamadi, M. J. Fischer, and R. Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 18(4):235\u2013253, 2006. Also in 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 290\u2013299, ACM, New York, NY, USA, 2004.","journal-title":"Distributed Computing"},{"key":"5_CR3","unstructured":"D. Angluin, J. Aspnes, Z. Diamadi, M. J. Fischer, and R. Peralta. Urn automata. Technical Report YALEU\/DCS\/TR-1280, Yale University Department of Computer Science, Nov. 2003."},{"issue":"3","key":"5_CR4","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/s00446-008-0067-z","volume":"21","author":"D. Angluin","year":"2008","unstructured":"D. Angluin, J. Aspnes, and D. Eisenstat. Fast computation by population protocols with a leader. Distributed Computing, 21(3):183\u2013199, September 2008.","journal-title":"Distributed Computing"},{"key":"5_CR5","doi-asserted-by":"crossref","unstructured":"D. Angluin, J. Aspnes, and D. Eisenstat. Stably computable predicates are semilinear. In Proc. 25th Annual ACM Symposium on Principles of Distributed Computing, pages 292\u2013299, Denver, Colorado, USA, 2006.","DOI":"10.1145\/1146381.1146425"},{"issue":"4","key":"5_CR6","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s00446-007-0040-2","volume":"20","author":"D. Angluin","year":"2007","unstructured":"D. Angluin, J. Aspnes, D. Eisenstat, and E. Ruppert. The computational power of population protocols. Distributed Computing, 20(4): 279\u2013304, November 2007.","journal-title":"Distributed Computing"},{"key":"5_CR7","first-page":"98","volume":"93","author":"J. Aspnes","year":"2007","unstructured":"J. Aspnes and E. Ruppert. An introduction to population protocols. Bulletin of the European Association for Theoretical Computer Science, 93:98\u2013117, October, 2007. Columns: Distributed Computing, Editor: M. Mavronicolas.","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"issue":"5","key":"5_CR8","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1145\/1317379.1317385","volume":"41","author":"R. Bakhshi","year":"2007","unstructured":"R. Bakhshi, F. Bonnet, W. Fokkink, and B. Haverkort. Formal analysis techniques for gossiping protocols. In ACM SIGOPS Operating Systems Review, 41(5):28\u201336, Special Issue on Gossip-Based Networking, October 2007.","journal-title":"ACM SIGOPS Operating Systems Review"},{"key":"5_CR9","doi-asserted-by":"crossref","unstructured":"J. Beauquier, J. Clement, S. Messika, L. Rosaz, and B. Rozoy. Self-stabilizing counting in mobile sensor networks. Technical Report 1470, LRI, Universit\u00e9 Paris-Sud 11, 2007.","DOI":"10.1145\/1281100.1281191"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"G. Behrmann, A. David, and K. G. Larsen. A tutorial on Uppaal. In Formal Methods for the Design of Real-Time Systems: Proceedings of the 4th International School on Formal Methods for the Design of Comput., Commun. and Software Syst. (SFM-RT 2004), number 3185 in LNCS, pages 200\u2013236, Springer, 2004.","DOI":"10.1007\/978-3-540-30080-9_7"},{"issue":"4","key":"5_CR11","doi-asserted-by":"publisher","first-page":"1340","DOI":"10.1016\/j.amc.2009.04.056","volume":"215","author":"O. Bournez","year":"2009","unstructured":"O. Bournez, P. Chassaing, J. Cohen, L. Gerin, and X. Koegler. On the convergence of population protocols when population goes to infinity. In Applied Mathematics and Computation, 215(4):1340\u20131350, 2009.","journal-title":"Applied Mathematics and Computation"},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"I. Chatzigiannakis, S. Dolev, S. P. Fekete, O. Michail, and P. G. Spirakis. Not all fair probabilistic schedulers are equivalent. In 13th International Conference On Principles Of DIstributed Systems (OPODIS), pages 33\u201347, Nimes, France, December 15\u201318, 2009.","DOI":"10.1007\/978-3-642-10877-8_5"},{"key":"5_CR13","unstructured":"I. Chatzigiannakis, O. Michail, S. Nikolaou, A. Pavlogiannis, and P. G. Spirakis. Algorithmic verification of population protocols. FRONTS Technical Report FRONTS-TR-2010-12, http:\/\/fronts.cti.gr\/aigaion\/?TR=148, Jan. 2010."},{"key":"5_CR14","unstructured":"I. Chatzigiannakis, O. Michail, S. Nikolaou, A. Pavlogiannis, and P. G. Spirakis. Passively mobile communicating logarithmic space machines. FRONTS Technical Report FRONTS-TR-2010-16, http:\/\/fronts.cti.gr\/aigaion\/?TR=154, Feb. 2010."},{"key":"5_CR15","unstructured":"I. Chatzigiannakis, O. Michail, and P. G. Spirakis. Decidable graph languages by mediated population protocols. In 23rd International Symposium on Distributed Computing (DISC), Elche, Spain, Sept. 2009. (Also FRONTS Technical Report FRONTS-TR-2009-16, http:\/\/fronts.cti.gr\/aigaion\/?TR=80)"},{"key":"5_CR16","unstructured":"I. Chatzigiannakis, O. Michail, and P. G. Spirakis. Experimental verification and performance study of extremely large sized population protocols. FRONTS Technical Report FRONTS-TR-2009-3, http:\/\/fronts.cti.gr\/aigaion\/?TR=61, Jan. 2009."},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"I. Chatzigiannakis, O. Michail, and P. G. Spirakis. Mediated population protocols. In 36th International Colloquium on Automata, Languages and Programming (ICALP), pages 363\u2013374, Rhodes, Greece, 2009.","DOI":"10.1007\/978-3-642-02930-1_30"},{"key":"5_CR18","unstructured":"I. Chatzigiannakis, O. Michail, and P. G. Spirakis. Recent advances in population protocols. In 34th International Symposium on Mathematical Foundations of Computer Science (MFCS), August 24\u201328, 2009, Novy Smokovec, High Tatras, Slovakia."},{"key":"5_CR19","doi-asserted-by":"crossref","unstructured":"I. Chatzigiannakis and P. G. Spirakis. The dynamics of probabilistic population protocols. In Distributed Computing, 22nd International Symposium, DISC, vol. 5218, Lecture Notes in Computer Science, pages 498\u2013499, 2008.","DOI":"10.1007\/978-3-540-87779-0_35"},{"key":"5_CR20","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/BF01940880","volume":"15","author":"J. Cheriyan","year":"1996","unstructured":"J. Cheriyan and K. Mehlhorn. Algorithms for dense graphs and networks on the random access computer. Algorithmica, 15: 521\u2013549, 1996.","journal-title":"Algorithmica"},{"key":"5_CR21","volume-title":"Model checking","author":"E. M. Clarke","year":"2000","unstructured":"E. M. Clarke, O. Grumberg, and D. A. Peled. Model checking. MIT Press, New York, NY, 2000."},{"key":"5_CR22","doi-asserted-by":"crossref","unstructured":"C. Delporte-Gallet, H. Fauconnier, R. Guerraoui, and E. Ruppert. When birds die: Making population protocols fault-tolerant. In Proc. 2nd IEEE International Conference on Distributed Computing in Sensor Systems, pages 51\u201366, 2006.","DOI":"10.1007\/11776178_4"},{"issue":"1-2","key":"5_CR23","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/BF03160228","volume":"6","author":"Z. Diamadi","year":"2001","unstructured":"Z. Diamadi and M. J. Fischer. A simple game for the study of trust in distributed systems. Wuhan University Journal of Natural Sciences, 6(1-2):72\u201382, Mar. 2001. Also appears as Yale Technical Report TR-1207, Jan. 2001.","journal-title":"Wuhan University Journal of Natural Sciences"},{"issue":"6","key":"5_CR24","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1145\/363347.363390","volume":"11","author":"R. Fenichel","year":"1968","unstructured":"R. Fenichel. Distribution of Indistinguishable Objects into Distinguishable Slots. Communications of the ACM, 11(6): 430, June 1968.","journal-title":"Communications of the ACM"},{"key":"5_CR25","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0020-0190(00)00051-X","volume":"74","author":"H. N. Gabow","year":"2000","unstructured":"H. N. Gabow. Path-based depth-first search for strong and biconnected components. Information Processing Letters, 74:107\u2013114, 2000.","journal-title":"Information Processing Letters"},{"key":"5_CR26","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1016\/0378-4371(92)90283-V","volume":"188","author":"D. T. Gillespie","year":"1992","unstructured":"D. T. Gillespie. A rigorous derivation of the chemical master equation. Physica A, 188:404\u2013425, 1992.","journal-title":"Physica A"},{"issue":"25","key":"5_CR27","doi-asserted-by":"publisher","first-page":"2340","DOI":"10.1021\/j100540a008","volume":"81","author":"D. T. Gillespie","year":"1977","unstructured":"D. T. Gillespie. Exact stochastic simulation of coupled chemical reactions. Journal of Physical Chemistry, 81(25):2340\u20132361, 1977.","journal-title":"Journal of Physical Chemistry"},{"key":"5_CR28","doi-asserted-by":"crossref","first-page":"285","DOI":"10.2140\/pjm.1966.16.285","volume":"16","author":"S. Ginsburg","year":"1966","unstructured":"S. Ginsburg and E. H. Spanier. Semigroups, Presburger formulas, and languages. Pacific Journal of Mathematics, 16:285\u2013296, 1966.","journal-title":"Pacific Journal of Mathematics"},{"key":"5_CR29","doi-asserted-by":"crossref","unstructured":"R. Guerraoui and E. Ruppert. Names trump malice: Tiny mobile agents can tolerate byzantine failures. In 36th International Colloquium on Automata, Languages and Programming (ICALP), pages 484\u2013495, Rhodes, Greece, 2009.","DOI":"10.1007\/978-3-642-02930-1_40"},{"key":"5_CR30","doi-asserted-by":"crossref","unstructured":"A. Hinton, M. Z. Kwiatkowska, G. Norman, and D. Parker. Prism: A tool for automatic verification of probabilistic systems. In Proceedings of 2nd International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS \u201906), vol. 3920, LNCS, pages 441\u2013444. Springer, 2006.","DOI":"10.1007\/11691372_29"},{"key":"5_CR31","volume-title":"The Spin Model Checker, Primer and Reference Manual","author":"G. Holzmann","year":"2003","unstructured":"G. Holzmann. The Spin Model Checker, Primer and Reference Manual. Addison-Wesley, New York, NY, 2003."},{"key":"5_CR32","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511810275","volume-title":"Logic in Computer Science: Modelling and Reasoning About Systems","author":"M. Huth","year":"2004","unstructured":"M. Huth and M. Ryan. Logic in Computer Science: Modelling and Reasoning About Systems. Cambridge University Press, Cambridge, UK, 2004."},{"key":"5_CR33","unstructured":"T. G. Kurtz. Approximation of population processes. Number 36 in CBMS-NSF Regional Conference Series in Applied Mathematics, Society for Industrial and Applied Mathematics, Philadelphia, 1981."},{"key":"5_CR34","doi-asserted-by":"crossref","unstructured":"P. C. Olveczky and S. Thorvaldsen. Formal modeling and analysis of wireless sensor network algorithms in Real-Time Maude. Parallel and Distributed Processing Symposium, International, p. 157, Proceedings 20th IEEE International Parallel % Distributed Processing Symposium, Rhodes, Greece, 2006.","DOI":"10.1109\/IPDPS.2006.1639414"},{"key":"5_CR35","volume-title":"Computational Complexity","author":"C. H. Papadimitriou","year":"1994","unstructured":"C. H. Papadimitriou. Computational Complexity. Addison-Wesley, New York, NY, 1994."},{"issue":"2","key":"5_CR36","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R. Tarjan","year":"1972","unstructured":"R. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146\u2013160, 1972.","journal-title":"SIAM Journal on Computing"}],"container-title":["Monographs in Theoretical Computer Science. An EATCS Series","Theoretical Aspects of Distributed Computing in Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14849-1_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,18]],"date-time":"2023-02-18T03:51:21Z","timestamp":1676692281000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-14849-1_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11,8]]},"ISBN":["9783642148484","9783642148491"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14849-1_5","relation":{},"ISSN":["1431-2654"],"issn-type":[{"type":"print","value":"1431-2654"}],"subject":[],"published":{"date-parts":[[2010,11,8]]},"assertion":[{"value":"8 November 2010","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}