{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:13:07Z","timestamp":1760202787528},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030032319"},{"type":"electronic","value":"9783030032326"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-03232-6_11","type":"book-chapter","created":{"date-parts":[[2018,10,19]],"date-time":"2018-10-19T07:44:48Z","timestamp":1539935088000},"page":"154-169","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Simple and Fast Approximate Counting and Leader Election in Populations"],"prefix":"10.1007","author":[{"given":"Othon","family":"Michail","sequence":"first","affiliation":[]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[]},{"given":"Michail","family":"Theofilatos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,10,20]]},"reference":[{"issue":"4","key":"11_CR1","doi-asserted-by":"publisher","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., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18(4), 235\u2013253 (2006)","journal-title":"Distrib. Comput."},{"issue":"3","key":"11_CR2","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s00446-015-0257-4","volume":"29","author":"O Michail","year":"2016","unstructured":"Michail, O., Spirakis, P.G.: Simple and efficient local codes for distributed stable network construction. Distrib. Comput. 29(3), 207\u2013237 (2016)","journal-title":"Distrib. Comput."},{"issue":"3","key":"11_CR3","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/s00446-008-0067-z","volume":"21","author":"D Angluin","year":"2008","unstructured":"Angluin, D., Aspnes, J., Eisenstat, D.: Fast computation by population protocols with a leader. Distrib. Comput. 21(3), 183\u2013199 (2008)","journal-title":"Distrib. Comput."},{"key":"11_CR4","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1007\/s11047-008-9067-y","volume":"7","author":"D Soloveichik","year":"2008","unstructured":"Soloveichik, D., Cook, M., Winfree, E., Bruck, J.: Computation with finite stochastic chemical reaction networks. Nat. Comput. 7, 615\u2013633 (2008)","journal-title":"Nat. Comput."},{"key":"11_CR5","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/s11047-013-9393-6","volume":"7","author":"H-L Chen","year":"2014","unstructured":"Chen, H.-L., Doty, D., Soloveichik, D.: Deterministic function computation with chemical reaction networks. Nat. Comput. 7, 517\u2013534 (2014)","journal-title":"Nat. Comput."},{"key":"11_CR6","first-page":"772","volume-title":"Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"David Doty","year":"2013","unstructured":"Doty, D.: Timing in chemical reaction networks. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 772\u2013784 (2014)"},{"issue":"4","key":"11_CR7","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s00446-007-0040-2","volume":"20","author":"D Angluin","year":"2007","unstructured":"Angluin, D., Aspnes, J., Eisenstat, D., Ruppert, E.: The computational power of population protocols. Distrib. Comput. 20(4), 279\u2013304 (2007)","journal-title":"Distrib. Comput."},{"issue":"46","key":"11_CR8","doi-asserted-by":"publisher","first-page":"6469","DOI":"10.1016\/j.tcs.2011.07.001","volume":"412","author":"I Chatzigiannakis","year":"2011","unstructured":"Chatzigiannakis, I., Michail, O., Nikolaou, S., Pavlogiannis, A., Spirakis, P.G.: Passively mobile communicating machines that use restricted space. Theor. Comput. Sci. 412(46), 6469\u20136483 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"Michail, O., Chatzigiannakis, I., Spirakis, P.G.: New models for population protocols. In: Lynch, N.A. (ed.) Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool (2011)","DOI":"10.2200\/S00328ED1V01Y201101DCT006"},{"key":"11_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1007\/978-3-642-02930-1_40","volume-title":"Automata, Languages and Programming","author":"R Guerraoui","year":"2009","unstructured":"Guerraoui, R., Ruppert, E.: Names trump malice: tiny mobile agents can tolerate byzantine failures. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5556, pp. 484\u2013495. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-02930-1_40"},{"key":"11_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89707-1_5","volume-title":"Middleware for Network Eccentric and Mobile Applications","author":"J Aspnes","year":"2009","unstructured":"Aspnes, J., Ruppert, E.: An introduction to population protocols. In: Garbinato, B., Miranda, H., Rodrigues, L. (eds.) Middleware for Network Eccentric and Mobile Applications. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-540-89707-1_5"},{"issue":"2","key":"11_CR12","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1145\/3156693","volume":"61","author":"O Michail","year":"2018","unstructured":"Michail, O., Spirakis, P.G.: Elements of the theory of dynamic networks. Commun. ACM 61(2), 72 (2018)","journal-title":"Commun. ACM"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processors. In: Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC). ACM (1980)","DOI":"10.1145\/800141.804655"},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"Attiya, C., Snir, M., Warmuth, M: Computing on an anonymous ring. In: PODC 1985. ACM (1985)","DOI":"10.1145\/323596.323614"},{"key":"11_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/978-3-662-47666-6_38","volume-title":"Automata, Languages, and Programming","author":"D Alistarh","year":"2015","unstructured":"Alistarh, D., Gelashvili, R.: Polylogarithmic-time leader election in population protocols. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9135, pp. 479\u2013491. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47666-6_38"},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"2653","DOI":"10.1137\/1.9781611975031.169","volume-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Leszek G\u0105sieniec","year":"2018","unstructured":"Gasieniec, L., Stachowiak, G.: Fast space optimal leader election in population protocols. In: SODA 2018, ACM-SIAM Symposium on Discrete Algorithms (2018, to appear)"},{"key":"11_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/11945529_28","volume-title":"Principles of Distributed Systems","author":"M Fischer","year":"2006","unstructured":"Fischer, M., Jiang, H.: Self-stabilizing leader election in networks of finite-state anonymous agents. In: Shvartsman, M.M.A.A. (ed.) OPODIS 2006. LNCS, vol. 4305, pp. 395\u2013409. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11945529_28"},{"key":"11_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1007\/978-3-319-57586-5_38","volume-title":"Algorithms and Complexity","author":"GA Luna Di","year":"2017","unstructured":"Di Luna, G.A., Flocchini, P., Izumi, T., Izumi, T., Santoro, N., Viglietta, G.: Population protocols with faulty interactions: the impact of a leader. In: Fotakis, D., Pagourtzis, A., Paschos, V.T. (eds.) CIAC 2017. LNCS, vol. 10236, pp. 454\u2013466. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-57586-5_38"},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"Angluin, D., Aspnes, J., Eisenstat, D.: Stably computable predicates are semilinear. In: PODC 2006, New York. ACM Press (2006)","DOI":"10.1145\/1146381.1146425"},{"key":"11_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1007\/978-3-662-48653-5_40","volume-title":"Distributed Computing","author":"D Doty","year":"2015","unstructured":"Doty, D., Soloveichik, D.: Stable leader election in population protocols requires linear time. In: Moses, Y. (ed.) DISC 2015. LNCS, vol. 9363, pp. 602\u2013616. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48653-5_40"},{"key":"11_CR21","unstructured":"Belleville, A., Doty, D., Soloveichik, D.: Hardness of computing and approximating predicates and functions with leaderless population protocols. In: ICALP 2017, Leibniz International Proceedings in Informatics (LIPIcs), vol. 80. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)"},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Alistarh, D., Aspnes, J., Eisenstat, D., Gelashvili, R., Rivest, R.L.: Time-space trade-offs in population protocols. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2560\u20132579. SIAM (2017)","DOI":"10.1137\/1.9781611974782.169"},{"issue":"6","key":"11_CR23","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s00446-012-0173-9","volume":"25","author":"R Mizoguchi","year":"2012","unstructured":"Mizoguchi, R., Ono, H., Kijima, S., Yamashita, M.: On space complexity of self-stabilizing leader election in mediated population protocol. Distrib. Comput. 25(6), 451\u2013460 (2012)","journal-title":"Distrib. Comput."},{"key":"11_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/978-3-319-55911-7_13","volume-title":"Theory and Applications of Models of Computation","author":"S Das","year":"2017","unstructured":"Das, S., Di Luna, G.A., Flocchini, P., Santoro, N., Viglietta, G.: Mediated population protocols: leader election and applications. In: Gopal, T.V., J\u00e4ger, G., Steila, S. (eds.) TAMC 2017. LNCS, vol. 10185, pp. 172\u2013186. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-55911-7_13"},{"key":"11_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/978-3-540-75142-7_8","volume-title":"Distributed Computing","author":"J Beauquier","year":"2007","unstructured":"Beauquier, J., Clement, J., Messika, S., Rosaz, L., Rozoy, B.: Self-stabilizing counting in mobile sensor networks with a base station. In: Pelc, A. (ed.) DISC 2007. LNCS, vol. 4731, pp. 63\u201376. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-75142-7_8"},{"key":"11_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1007\/978-3-662-48653-5_42","volume-title":"Distributed Computing","author":"J Beauquier","year":"2015","unstructured":"Beauquier, J., Burman, J., Clavi\u00e8re, S., Sohier, D.: Space-optimal counting in population protocols. In: Moses, Y. (ed.) DISC 2015. LNCS, vol. 9363, pp. 631\u2013646. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48653-5_42"},{"key":"11_CR27","unstructured":"Aspnes, J., Beauquier, J., Burman, J., Sohier, D.: Time and space optimal counting in population protocols. In: OPODIS 2016, vol. 70 (2017)"},{"key":"11_CR28","doi-asserted-by":"crossref","unstructured":"Michail, O.: Terminating distributed construction of shapes and patterns in a fair solution of automata. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pp. 37\u201346 (2015). Also in Distributed Computing (2017)","DOI":"10.1145\/2767386.2767402"},{"key":"11_CR29","unstructured":"Doty, D., Eftekhari, M., Michail, O., Spirakis, P.G., Theofilatos, M.: Exact size counting in uniform population protocols in nearly logarithmic time. CoRR, abs\/1805.04832 (2018)"},{"key":"11_CR30","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.tcs.2014.07.028","volume":"552","author":"T Izumi","year":"2014","unstructured":"Izumi, T., Kinpara, K., Izumi, T., Wada, K.: Space-efficient self-stabilizing counting population protocols on mobile sensor networks. Theor. Comput. Sci. 552, 99\u2013108 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"11_CR31","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: Proceedings of the 42nd ACM Symposium on Theory of computing (STOC), pp. 513\u2013522. ACM (2010)","DOI":"10.1145\/1806689.1806760"},{"key":"11_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/978-3-319-03089-0_20","volume-title":"Stabilization, Safety, and Security of Distributed Systems","author":"O Michail","year":"2013","unstructured":"Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Naming and counting in anonymous unknown dynamic networks. In: Higashino, T., Katayama, Y., Masuzawa, T., Potop-Butucaru, M., Yamashita, M. (eds.) SSS 2013. LNCS, vol. 8255, pp. 281\u2013295. Springer, Cham (2013). https:\/\/doi.org\/10.1007\/978-3-319-03089-0_20"},{"key":"11_CR33","doi-asserted-by":"crossref","unstructured":"Di Luna, G.A., Baldoni, R., Bonomi, S., Chatzigiannakis, I.: Counting in anonymous dynamic networks under worst-case adversary. In: IEEE 34th International Conference on Distributed Computing Systems (ICDCS) (2014)","DOI":"10.1109\/ICDCS.2014.42"},{"issue":"5","key":"11_CR34","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1080\/17445760.2012.668546","volume":"27","author":"A Casteigts","year":"2012","unstructured":"Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel Emerg. Distrib. Syst. 27(5), 387\u2013408 (2012)","journal-title":"Int. J. Parallel Emerg. Distrib. Syst."}],"container-title":["Lecture Notes in Computer Science","Stabilization, Safety, and Security of Distributed Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-03232-6_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,27]],"date-time":"2019-10-27T03:42:44Z","timestamp":1572147764000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-03232-6_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030032319","9783030032326"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-03232-6_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"SSS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Stabilizing, Safety, and Security of Distributed Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Tokyo","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Japan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 November 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 November 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sss2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.coord.c.titech.ac.jp\/symp\/sss2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}