{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T23:22:18Z","timestamp":1784676138484,"version":"3.55.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2020,4,25]],"date-time":"2020-04-25T00:00:00Z","timestamp":1587772800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,4,25]],"date-time":"2020-04-25T00:00:00Z","timestamp":1587772800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"name":"University Research Chair"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2020,12]]},"DOI":"10.1007\/s00446-020-00377-0","type":"journal-article","created":{"date-parts":[[2020,4,25]],"date-time":"2020-04-25T05:03:03Z","timestamp":1587790983000},"page":"561-578","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Fault-tolerant simulation of population protocols"],"prefix":"10.1007","volume":"33","author":[{"given":"Giuseppe A.","family":"Di Luna","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paola","family":"Flocchini","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Taisuke","family":"Izumi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tomoko","family":"Izumi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicola","family":"Santoro","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giovanni","family":"Viglietta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,4,25]]},"reference":[{"key":"377_CR1","doi-asserted-by":"crossref","unstructured":"Alistarh, D., Aspens, J., Gelashvili, R.: Space-optimal majority in population protocols. In: 29th Symposium on Discrete Algorithms (SODA), pp. 2221\u20132239 (2018)","DOI":"10.1137\/1.9781611975031.144"},{"key":"377_CR2","doi-asserted-by":"crossref","unstructured":"Alistarh, D., Gelashvili, R.: Polylogarithmic-time leader election in population protocols. In: 42nd International Colloquium on Automata, Languages and Programming (ICALP), pp. 479\u2013491 (2015)","DOI":"10.1007\/978-3-662-47666-6_38"},{"key":"377_CR3","doi-asserted-by":"crossref","unstructured":"Alistarh, D., Gelashvili, R., Vojnovic, M.: Fast and exact majority in population protocols. In: 34th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 47\u201356 (2015)","DOI":"10.1145\/2767386.2767429"},{"issue":"4","key":"377_CR4","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."},{"key":"377_CR5","doi-asserted-by":"crossref","unstructured":"Angluin, D., Aspnes, J., Eisenstat, D.: On the power of anonymous one-way communication. In: 9th International Conference on Principles of Distributed Systems (OPODIS), pp.\u00a0396\u2013411 (2005)","DOI":"10.1007\/11795490_30"},{"key":"377_CR6","doi-asserted-by":"crossref","unstructured":"Angluin, D., Aspnes, J., Eisenstat, D.: Stably computable predicates are semilinear. In: 25th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 292\u2013299 (2006)","DOI":"10.1145\/1146381.1146425"},{"issue":"2","key":"377_CR7","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s00446-008-0059-z","volume":"21","author":"D Angluin","year":"2008","unstructured":"Angluin, D., Aspnes, J., Eisenstat, D.: A simple population protocol for fast robust approximate majority. Distrib. Comput. 21(2), 87\u2013102 (2008)","journal-title":"Distrib. Comput."},{"issue":"3","key":"377_CR8","doi-asserted-by":"publisher","first-page":"61","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), 61\u201375 (2008)","journal-title":"Distrib. Comput."},{"issue":"4","key":"377_CR9","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."},{"key":"377_CR10","first-page":"98","volume":"93","author":"J Aspnes","year":"2007","unstructured":"Aspnes, J., Ruppert, E.: An introduction to population protocols. Bull. Eur. Assoc. Theor. Comput. Sci. 93, 98\u2013117 (2007)","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"key":"377_CR11","doi-asserted-by":"crossref","unstructured":"Beauquier, J., Burman, J., Clavi\u00e8re, S., Sohier, D.: Space-optimal counting in population protocols. In: 29th International Symposium on Distributed Computing (DISC), pp. 631\u2013649 (2015)","DOI":"10.1007\/978-3-662-48653-5_42"},{"issue":"33","key":"377_CR12","doi-asserted-by":"publisher","first-page":"4247","DOI":"10.1016\/j.tcs.2010.09.016","volume":"412","author":"J Beauquier","year":"2011","unstructured":"Beauquier, J., Burman, J., Kutten, S.: A self-stabilizing transformer for population protocols with covering. Theor. Comput. Sci. 412(33), 4247\u20134259 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"377_CR13","first-page":"1340","volume":"215","author":"O Bournez","year":"2009","unstructured":"Bournez, O., Chassaing, P., Cohen, J., Gerin, L., Koegler, X.: On the convergence of population protocols when population goes to infinity. Appl. Math. Comput. 215(4), 1340\u20131350 (2009)","journal-title":"Appl. Math. Comput."},{"issue":"3","key":"377_CR14","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/s00224-011-9313-z","volume":"50","author":"S Cai","year":"2012","unstructured":"Cai, S., Izumi, T., Wada, K.: How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model. Theory Comput. Syst. 50(3), 433\u2013445 (2012)","journal-title":"Theory Comput. Syst."},{"key":"377_CR15","doi-asserted-by":"crossref","unstructured":"Canepa, D., Gradinariu Potop-Butucaru, M.: Self-stabilizing tiny interaction protocols. In: 3rd International Workshop on Reliability, Availability, and Security (WRAS), pp.\u00a01\u20136 (2010)","DOI":"10.1145\/1953563.1953572"},{"key":"377_CR16","doi-asserted-by":"crossref","unstructured":"Chatzigiannakis, I., Dolev, S., Fekete, S.P., Michail, O., Spirakis, P.G.: Not all fair probabilistic schedulers are equivalent. In: 13th International Conference on Principles of Distributed Systems (OPODIS), pp.\u00a033\u201347 (2009)","DOI":"10.1007\/978-3-642-10877-8_5"},{"issue":"46","key":"377_CR17","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.: Passively mobile communicating machines that use restricted space. Theor. Comput. Sci. 412(46), 6469\u20136483 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"377_CR18","doi-asserted-by":"crossref","unstructured":"Chatzigiannakis, I., Michail, O., Nikolaou, S., Pavlogiannis, A., Spirakis, P.G.: All symmetric predicates in NSPACE($$n^2$$) are stably computable by the mediated population protocol model. In: 35th International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 270\u2013281 (2010)","DOI":"10.1007\/978-3-642-15155-2_25"},{"key":"377_CR19","doi-asserted-by":"crossref","unstructured":"Chatzigiannakis, I., Michail, O., Spirakis, P.G.: Stably decidable graph languages by mediated population protocols. In: 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp. 252\u2013266 (2010)","DOI":"10.1007\/978-3-642-16023-3_21"},{"key":"377_CR20","doi-asserted-by":"crossref","unstructured":"Chatzigiannakis, I., Spirakis, P.G.: The dynamics of probabilistic population protocols. In: 22nd International Symposium on Distributed Computing (DISC), pp. 498\u2013499 (2008)","DOI":"10.1007\/978-3-540-87779-0_35"},{"key":"377_CR21","doi-asserted-by":"crossref","unstructured":"Chen, H.-L., Cummings, R., Doty, D., Soloveichik, D.: Speed faults in computation by chemical reaction networks. In: 28th International Symposium on Distributed Computing (DISC), pp. 16\u201330 (2014)","DOI":"10.1007\/978-3-662-45174-8_2"},{"key":"377_CR22","doi-asserted-by":"crossref","unstructured":"Das, S., Di Luna, G.A., Flocchini, P., Santoro, N., Viglietta, G.: Mediated population protocols: leader election and applications. In: 14th Annual Conference on Theory and Applications of Models of Computation (TAMC), pp.\u00a0172\u2013186 (2017)","DOI":"10.1007\/978-3-319-55911-7_13"},{"key":"377_CR23","unstructured":"Delporte-Gallet, C., Fauconnier, H., Guerraoui, R.: What dependability for networks of mobile sensors? In: 1st Workshop on Hot Topics in System Dependability (HotDep), p. 8 (2005)"},{"key":"377_CR24","doi-asserted-by":"crossref","unstructured":"Delporte-Gallet, C., Fauconnier, H., Guerraoui, R., Ruppert, E.: When birds die: making population protocols fault-tolerant. In: 2nd IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS), pp.\u00a051\u201366 (2006)","DOI":"10.1007\/11776178_4"},{"key":"377_CR25","doi-asserted-by":"crossref","unstructured":"Di Luna, G.A., Flocchini, P., Izumi, T., Izumi, T., Santoro, N., Viglietta, G.: On the power of weaker pairwise interaction: fault-tolerant simulation of population protocols. In: 37th IEEE International Conference on Distributed Computing Systems (ICDCS), pp.\u00a02472\u20132477 (2017)","DOI":"10.1109\/ICDCS.2017.50"},{"key":"377_CR26","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/j.tcs.2018.09.005","volume":"754","author":"GA Di Luna","year":"2019","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. Theor. Comput. Sci. 754, 35\u201349 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"377_CR27","doi-asserted-by":"crossref","unstructured":"Fischer, M., Jiang, H.: Self-stabilizing leader election in networks of finite-state anonymous agents. In: 10th International Conference on Principles of Distributed Systems (OPODIS), pp.\u00a0395\u2013409 (2006)","DOI":"10.1007\/11945529_28"},{"key":"377_CR28","unstructured":"Guerraoui, R., Ruppert, E.: Even Small Birds are Unique: Population Protocols With Identifiers. Technical Report CSE-2007-04. York University (2007)"},{"key":"377_CR29","doi-asserted-by":"crossref","unstructured":"Guerraoui, R., Ruppert, E.: Names trump malice: tiny mobile agents can tolerate byzantine failures. In: 36th International Colloquium on Automata, Languages and Programming (ICALP), Vol. 16(No. 2), pp. 484\u2013495 (2009)","DOI":"10.1007\/978-3-642-02930-1_40"},{"key":"377_CR30","unstructured":"Kosowski, A., Uznanski, P.: Population Protocols are fast, ArXiv e-prints (2018). arXiv:1802.06872"},{"issue":"22","key":"377_CR31","doi-asserted-by":"publisher","first-page":"2434","DOI":"10.1016\/j.tcs.2011.02.003","volume":"412","author":"O Michail","year":"2011","unstructured":"Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Mediated population protocols. Theor. Comput. Sci. 412(22), 2434\u20132450 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"377_CR32","volume-title":"New Models for Population Protocols, Synthesis Lectures on Distributed Computing Theory","author":"O Michail","year":"2011","unstructured":"Michail, O., Chatzigiannakis, I., Spirakis, P.G.: New Models for Population Protocols, Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool, New York (2011)"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00377-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-020-00377-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00377-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,25]],"date-time":"2021-04-25T10:25:57Z","timestamp":1619346357000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-020-00377-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,25]]},"references-count":32,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["377"],"URL":"https:\/\/doi.org\/10.1007\/s00446-020-00377-0","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,25]]},"assertion":[{"value":"29 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 March 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}