{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T13:13:00Z","timestamp":1742994780597,"version":"3.40.3"},"publisher-location":"Cham","reference-count":45,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031744976"},{"type":"electronic","value":"9783031744983"}],"license":[{"start":{"date-parts":[[2024,10,20]],"date-time":"2024-10-20T00:00:00Z","timestamp":1729382400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,10,20]],"date-time":"2024-10-20T00:00:00Z","timestamp":1729382400000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-74498-3_9","type":"book-chapter","created":{"date-parts":[[2024,10,19]],"date-time":"2024-10-19T11:02:30Z","timestamp":1729335750000},"page":"126-140","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Complete Graph Identification in\u00a0Population Protocols"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-8102-0280","authenticated-orcid":false,"given":"Haruki","family":"Kanaya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4442-1750","authenticated-orcid":false,"given":"Yuichi","family":"Sudo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,10,20]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"Alistarh, D., Aspnes, J., Eisenstat, D., Gelashvili, R., Rivest, R.L.: Time-space trade-offs in population protocols. In: SODA. pp. 2560\u20132579 (2017)","DOI":"10.1137\/1.9781611974782.169"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Alistarh, D., Aspnes, J., Gelashvili, R.: Space-optimal majority in population protocols. In: SODA, pp. 2221\u20132239 (2018)","DOI":"10.1137\/1.9781611975031.144"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Alistarh, D., Gelashvili, R.: Polylogarithmic-time leader election in population protocols. In: ICALP, pp. 479\u2013491 (2015)","DOI":"10.1007\/978-3-662-47666-6_38"},{"key":"9_CR4","unstructured":"Alistarh, D., Gelashvili, R., Rybicki, J.: Fast graphical population protocols. In: OPODIS 2021, pp. 14:1\u201314:18 (2022)"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"Alistarh, D., Gelashvili, R., Vojnovi\u0107, M.: Fast and exact majority in population protocols. In: PODC, pp. 47\u201356 (2015)","DOI":"10.1145\/2767386.2767429"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"Alistarh, D., Rybicki, J., Voitovych, S.: Near-optimal leader election in population protocols on graphs. In: PODC, pp. 246\u2013256 (2022)","DOI":"10.1145\/3519270.3538435"},{"key":"9_CR7","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: DCOSS, pp. 63\u201374 (2005)","DOI":"10.1007\/11502593_8"},{"issue":"4","key":"9_CR8","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":"9_CR9","doi-asserted-by":"crossref","unstructured":"Angluin, D., Aspnes, J., Eisenstat, D.: Stably computable predicates are semilinear. In: PODC, pp. 292\u2013299 (2006)","DOI":"10.1145\/1146381.1146425"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Angluin, D., Aspnes, J., Eisenstat, D.: A simple population protocol for fast robust approximate majority. In: DISC, pp. 20\u201332 (2007)","DOI":"10.1007\/978-3-540-75142-7_5"},{"issue":"3","key":"9_CR11","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."},{"issue":"4","key":"9_CR12","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":"9_CR13","doi-asserted-by":"crossref","unstructured":"Angluin, D., Aspnes, J., Fischer, M.J., Jiang, H.: Self-stabilizing population protocols. ACM Trans. Auton. Adapt. Syst. 3(4) (2008)","DOI":"10.1145\/1452001.1452003"},{"key":"9_CR14","unstructured":"Aspnes, J., Beauquier, J., Burman, J., Sohier, D.: Time and space optimal counting in population protocols. In: OPODIS, pp. 13:1\u201313:17 (2017)"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Beauquier, J., Blanchard, P., Burman, J.: Self-stabilizing leader election in population protocols over arbitrary communication graphs. In: OPODIS, pp. 38\u201352 (2013)","DOI":"10.1007\/978-3-319-03850-6_4"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"Beauquier, J., Burman, J., Clavi\u00e8re, S., Sohier, D.: Space-optimal counting in population protocols. In: DISC, pp. 631\u2013646 (2015)","DOI":"10.1007\/978-3-662-48653-5_42"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"Ben-Nun, S., Kopelowitz, T., Kraus, M., Porat, E.: An o(log3\/2 n) parallel time population protocol for majority with o(log n) states. In: PODC, pp. 191\u2013199 (2020)","DOI":"10.1145\/3382734.3405747"},{"key":"9_CR18","unstructured":"Berenbrink, P., Els\u00e4sser, R., Friedetzky, T., Kaaser, D., Kling, P., Radzik, T.: A population protocol for exact majority with O(log5\/3 n) stabilization time and theta(log n) states. In: DISC, pp. 10:1\u201310:18 (2018)"},{"issue":"2","key":"9_CR19","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s00446-020-00385-0","volume":"34","author":"P Berenbrink","year":"2021","unstructured":"Berenbrink, P., Els\u00e4sser, R., Friedetzky, T., Kaaser, D., Kling, P., Radzik, T.: Time-space trade-offs in population protocols for the majority problem. Distrib. Comput. 34(2), 91\u2013111 (2021)","journal-title":"Distrib. Comput."},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"Berenbrink, P., Giakkoupis, G., Kling, P.: Optimal time and space leader election in population protocols. In: STOC, pp. 119\u2013129 (2020)","DOI":"10.1145\/3357713.3384312"},{"key":"9_CR21","doi-asserted-by":"crossref","unstructured":"Bilke, A., Cooper, C., Els\u00e4sser, R., Radzik, T.: Brief announcement: Population protocols for leader election and exact majority with o(log2 n) states and o(log2 n) convergence time. In: PODC, pp. 451\u2013453 (2017)","DOI":"10.1145\/3087801.3087858"},{"key":"9_CR22","doi-asserted-by":"crossref","unstructured":"Chen, H.P., Chen, H.L.: Self-stabilizing leader election. In: PODC, pp. 53\u201359 (2019)","DOI":"10.1145\/3293611.3331616"},{"key":"9_CR23","doi-asserted-by":"crossref","unstructured":"Chen, H.P., Chen, H.L.: Self-stabilizing leader election in regular graphs. In: PODC, pp. 210\u2013217 (2020)","DOI":"10.1145\/3382734.3405733"},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"Doty, D., Eftekhari, M.: Efficient size estimation and impossibility of termination in uniform dense population protocols. In: PODC, pp. 34\u201342 (2019)","DOI":"10.1145\/3293611.3331627"},{"key":"9_CR25","doi-asserted-by":"crossref","unstructured":"Doty, D., Eftekhari, M., Gasieniec, L., Severson, E., Uznanski, P., Stachowiak, G.: A time and space optimal stable population protocol solving exact majority. In: FOCS, pp. 1044\u20131055 (2022)","DOI":"10.1109\/FOCS52979.2021.00104"},{"issue":"4","key":"9_CR26","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/s00446-016-0281-z","volume":"31","author":"D Doty","year":"2018","unstructured":"Doty, D., Soloveichik, D.: Stable leader election in population protocols requires linear time. Distrib. Comput. 31(4), 257\u2013271 (2018)","journal-title":"Distrib. Comput."},{"key":"9_CR27","doi-asserted-by":"crossref","unstructured":"Ga\u0328asieniec, L., Stachowiak, G., Uznanski, P.: Almost logarithmic-time space optimal leader election in population protocols. In: SPAA, pp. 93\u2013102 (2019)","DOI":"10.1145\/3323165.3323178"},{"key":"9_CR28","doi-asserted-by":"crossref","unstructured":"Ga\u0328sieniec, L., Stachowiak, G.: Fast space optimal leader election in population protocols. In: SODA, pp. 265\u2013266 (2018)","DOI":"10.1137\/1.9781611975031.169"},{"key":"9_CR29","doi-asserted-by":"crossref","unstructured":"Kanaya, H., Sudo, Y.: Complete graph identification in population protocols (2024). https:\/\/arxiv.org\/abs\/2408.12862","DOI":"10.1007\/978-3-031-74498-3_9"},{"key":"9_CR30","doi-asserted-by":"crossref","unstructured":"Mertzios, G.B., Nikoletseas, S.E., Raptopoulos, C.L., Spirakis, P.G.: Determining majority in networks with local interactions and very small local memory. In: ICALP, pp. 871\u2013882 (2014)","DOI":"10.1007\/978-3-662-43948-7_72"},{"key":"9_CR31","doi-asserted-by":"crossref","unstructured":"Mertzios, G.B., Nikoletseas, S.E., Raptopoulos, C.L., Spirakis, P.G.: Population protocols for majority in arbitrary networks. In: Extended Abstracts Summer 2015, pp. 77\u201382 (2017)","DOI":"10.1007\/978-3-319-51753-7_13"},{"issue":"22","key":"9_CR32","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. Theoret. Comput. Sci. 412(22), 2434\u20132450 (2011)","journal-title":"Theoret. Comput. Sci."},{"key":"9_CR33","doi-asserted-by":"crossref","unstructured":"Michail, O., Spirakis, P.G.: Simple and efficient local codes for distributed stable network construction. In: PODC, pp. 76\u201385 (2014)","DOI":"10.1145\/2611462.2611466"},{"key":"9_CR34","doi-asserted-by":"crossref","unstructured":"Michail, O., Spirakis, P.G., Theofilatos, M.: Simple and fast approximate counting and leader election in populations. Inform. Comput. 285(A), 104698 (2022)","DOI":"10.1016\/j.ic.2021.104698"},{"key":"9_CR35","doi-asserted-by":"crossref","unstructured":"Mocquard, Y., Anceaume, E., Aspnes, J., Busnel, Y., Sericola, B.: Counting with population protocols. In: NCA, pp. 35\u201342 (2015)","DOI":"10.1109\/NCA.2015.35"},{"key":"9_CR36","doi-asserted-by":"crossref","unstructured":"Mocquard, Y., Anceaume, E., Sericola, B.: Optimal proportion computation with population protocols. In: NCA, pp. 216\u2013223 (2016)","DOI":"10.1109\/NCA.2016.7778621"},{"issue":"01","key":"9_CR37","doi-asserted-by":"publisher","first-page":"2050005","DOI":"10.1142\/S012962642050005X","volume":"30","author":"Y Sudo","year":"2020","unstructured":"Sudo, Y., Masuzawa, T.: Leader election requires logarithmic time in population protocols. Parallel Proces. Lett. 30(01), 2050005 (2020)","journal-title":"Parallel Proces. Lett."},{"key":"9_CR38","doi-asserted-by":"crossref","unstructured":"Sudo, Y., Nakamura, J., Yamauchi, Y., Ooshita, F., Kakugawa, H., Masuzawa, T.: Loosely-stabilizing leader election in population protocol model. In: SIROCCO, pp. 295\u2013308 (2010)","DOI":"10.1007\/978-3-642-11476-2_23"},{"issue":"11","key":"9_CR39","doi-asserted-by":"publisher","first-page":"2620","DOI":"10.1109\/TPDS.2020.2991771","volume":"31","author":"Y Sudo","year":"2020","unstructured":"Sudo, Y., Ooshita, F., Izumi, T., Kakugawa, H., Masuzawa, T.: Time-optimal leader election in population protocols. IEEE Trans. Parallel Distrib. Syst. 31(11), 2620\u20132632 (2020)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"9_CR40","doi-asserted-by":"crossref","unstructured":"Sudo, Y., Ooshita, F., Kakugawa, H., Masuzawa, T.: Loosely stabilizing leader election on arbitrary graphs in population protocols without identifiers or random numbers. IEICE Trans. Inform. Syst. E103.D(3), 489\u2013499 (2020)","DOI":"10.1587\/transinf.2019FCP0003"},{"issue":"12","key":"9_CR41","doi-asserted-by":"publisher","first-page":"3011","DOI":"10.1109\/TPDS.2021.3076769","volume":"32","author":"Y Sudo","year":"2021","unstructured":"Sudo, Y., Shibata, M., Nakamura, J., Kim, Y., Masuzawa, T.: Self-stabilizing population protocols with global knowledge. IEEE Trans. Parallel Distrib. Syst. 32(12), 3011\u20133023 (2021)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"9_CR42","unstructured":"Yasumi, H., Ooshita, F., Inoue, M.: Population protocols for graph class identification problems. In: OPODIS, pp. 13:1\u201313:19 (2021)"},{"key":"9_CR43","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.tcs.2021.09.020","volume":"892","author":"H Yasumi","year":"2021","unstructured":"Yasumi, H., Ooshita, F., Inoue, M., Tixeuil, S.: Uniform bipartition in the population protocol model with arbitrary graphs. Theoret. Comput. Sci. 892, 187\u2013207 (2021)","journal-title":"Theoret. Comput. Sci."},{"key":"9_CR44","doi-asserted-by":"crossref","unstructured":"Yokota, D., Sudo, Y., Masuzawa, T.: Time-optimal self-stabilizing leader election on rings in population protocols. IEICE Trans. Fundament. Electron. Commun. Comput. Sci. E104.A(12), 1675\u20131684 (2021)","DOI":"10.1587\/transfun.2020EAP1125"},{"key":"9_CR45","doi-asserted-by":"crossref","unstructured":"Yokota, D., Sudo, Y., Ooshita, F., Masuzawa, T.: A near time-optimal population protocol for self-stabilizing leader election on rings with a poly-logarithmic number of states. In: PODC, pp. 2\u201312 (2023)","DOI":"10.1145\/3583668.3594586"}],"container-title":["Lecture Notes in Computer Science","Stabilization, Safety, and Security of Distributed Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-74498-3_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,30]],"date-time":"2024-12-30T22:03:20Z","timestamp":1735596200000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-74498-3_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,20]]},"ISBN":["9783031744976","9783031744983"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-74498-3_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024,10,20]]},"assertion":[{"value":"20 October 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"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":"Nagoya","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":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 October 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 October 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sss2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sss2024.github.io\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}