{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T17:03:16Z","timestamp":1780074196090,"version":"3.54.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T00:00:00Z","timestamp":1699833600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T00:00:00Z","timestamp":1699833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"ANR","award":["DESCARTES and FREDDA and DUCAT (ANR-20-CE48-0006)"],"award-info":[{"award-number":["DESCARTES and FREDDA and DUCAT (ANR-20-CE48-0006)"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1078\/17"],"award-info":[{"award-number":["1078\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2020277"],"award-info":[{"award-number":["2020277"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Appl. and Comput. Topology"],"published-print":{"date-parts":[[2024,9]]},"DOI":"10.1007\/s41468-023-00150-9","type":"journal-article","created":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T16:01:55Z","timestamp":1699891315000},"page":"909-940","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The topology of randomized symmetry-breaking distributed computing"],"prefix":"10.1007","volume":"8","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3615-3239","authenticated-orcid":false,"given":"Ran","family":"Gelles","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zvi","family":"Lotker","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,11,13]]},"reference":[{"issue":"1","key":"150_CR1","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1137\/0218002","volume":"18","author":"K Abrahamson","year":"1989","unstructured":"Abrahamson, K., Adler, A., Gelbart, R., Higham, L., Kirkpatrick, D.: The bit complexity of randomized leader election on a ring. SIAM J. Comput. 18(1), 12\u201329 (1989). https:\/\/doi.org\/10.1137\/0218002","journal-title":"SIAM J. Comput."},{"issue":"2","key":"150_CR2","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1006\/inco.1994.1075","volume":"113","author":"Y Afek","year":"1994","unstructured":"Afek, Y., Matias, Y.: Elections in anonymous networks. Inf. Comput. 113(2), 312\u2013330 (1994). https:\/\/doi.org\/10.1006\/inco.1994.1075","journal-title":"Inf. Comput."},{"key":"150_CR3","doi-asserted-by":"publisher","unstructured":"Angluin, D.: Local and global properties in networks of processors (extended abstract). In: Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, STOC \u201980, pp. 82\u201393. Association for Computing Machinery, New York, NY, USA (1980). https:\/\/doi.org\/10.1145\/800141.804655","DOI":"10.1145\/800141.804655"},{"issue":"4","key":"150_CR4","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1145\/48014.48247","volume":"35","author":"H Attiya","year":"1988","unstructured":"Attiya, H., Snir, M., Warmuth, M.K.: Computing on an anonymous ring. J. ACM 35(4), 845\u2013875 (1988). https:\/\/doi.org\/10.1145\/48014.48247","journal-title":"J. ACM"},{"key":"150_CR5","unstructured":"Boldi, P., Shammah, S., Vigna, S., Codenotti, B., Gemmell, P., Simon, J.: Symmetry breaking in anonymous networks: characterizations. In: Fourth Israel Symposium on Theory of Computing and Systems, ISTCS 1996, pp. 16\u201326. IEEE Computer Society (1996)"},{"key":"150_CR6","doi-asserted-by":"publisher","unstructured":"Borowsky, E., Gafni, E.: Generalized FLP impossibility result for t-resilient asynchronous computations. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC \u201993, pp. 91\u2013100. Association for Computing Machinery, New York, NY, USA (1993). https:\/\/doi.org\/10.1145\/167088.167119","DOI":"10.1145\/167088.167119"},{"issue":"4","key":"150_CR7","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/s00446-012-0163-y","volume":"25","author":"J Chalopin","year":"2012","unstructured":"Chalopin, J., Godard, E., M\u00e9tivier, Y.: Election in partially anonymous networks with arbitrary knowledge in message passing systems. Distrib. Comput. 25(4), 297\u2013311 (2012). https:\/\/doi.org\/10.1007\/s00446-012-0163-y","journal-title":"Distrib. Comput."},{"key":"150_CR8","unstructured":"Codenotti, B., Gemmell, P., Pudl\u00e1k, P., Simon, J.: On the amount of randomness needed in distributed computations. In: OPODIS \u201997 (1997)"},{"key":"150_CR9","doi-asserted-by":"publisher","DOI":"10.1145\/1326554.1326557","author":"Y Dinitz","year":"2008","unstructured":"Dinitz, Y., Moran, S., Rajsbaum, S.: Bit complexity of breaking and achieving symmetry in chains and rings. J. ACM (2008). https:\/\/doi.org\/10.1145\/1326554.1326557","journal-title":"J. ACM"},{"key":"150_CR10","doi-asserted-by":"publisher","unstructured":"Emek, Y., Pfister, C., Seidel, J., Wattenhofer, R.: Anonymous networks: randomization = 2-hop coloring. In: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC \u201914, pp. 96\u2013105. Association for Computing Machinery, New York, NY, USA (2014). https:\/\/doi.org\/10.1145\/2611462.2611478","DOI":"10.1145\/2611462.2611478"},{"key":"150_CR11","unstructured":"Euclid. $$\\Sigma T\\!Oi\\chi \\epsilon \\tilde{\\iota }\\alpha $$ (Elements). 300(?) BC. Book 7"},{"key":"150_CR12","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1002\/9781118593103.ch02","volume-title":"Handbook of Probability, Chap. Two: Probability Measure","year":"2014","unstructured":"Florescu, I., Tudor, C. (eds.): Handbook of Probability, Chap. Two: Probability Measure, pp. 15\u201362. Wiley, New York (2014). https:\/\/doi.org\/10.1002\/9781118593103.ch02"},{"key":"150_CR13","doi-asserted-by":"publisher","unstructured":"Fraigniaud, P., Gelles, R., Lotker, Z.: The topology of randomized symmetry-breaking distributed computing. In: PODC \u201921: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26\u201330, 2021, pp. 415\u2013425 (2021). https:\/\/doi.org\/10.1145\/3465084.3467936","DOI":"10.1145\/3465084.3467936"},{"issue":"1","key":"150_CR14","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/357195.357200","volume":"5","author":"RG Gallager","year":"1983","unstructured":"Gallager, R.G., Humblet, P.A., Spira, P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst. 5(1), 66\u201377 (1983). https:\/\/doi.org\/10.1145\/357195.357200","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"150_CR15","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-404578-1","volume-title":"Distributed Computing Through Combinatorial Topology","author":"M Herlihy","year":"2014","unstructured":"Herlihy, M., Kozlov, D., Rajsbaum, S.: Distributed Computing Through Combinatorial Topology. Morgan Kaufmann, Boston (2014). https:\/\/doi.org\/10.1016\/B978-0-12-404578-1"},{"key":"150_CR16","doi-asserted-by":"publisher","unstructured":"Herlihy, M., Shavit, N.: The asynchronous computability theorem for t-resilient tasks. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC \u201993, pp. 111\u2013120. Association for Computing Machinery, New York, NY, USA (1993). https:\/\/doi.org\/10.1145\/167088.167125","DOI":"10.1145\/167088.167125"},{"issue":"1","key":"150_CR17","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/0890-5401(90)90004-2","volume":"88","author":"A Itai","year":"1990","unstructured":"Itai, A., Rodeh, M.: Symmetry breaking in distributed networks. Inf. Comput. 88(1), 60\u201387 (1990). https:\/\/doi.org\/10.1016\/0890-5401(90)90004-2","journal-title":"Inf. Comput."},{"key":"150_CR18","doi-asserted-by":"publisher","unstructured":"Johnson, R.E., Schneider, F.B.: Symmetry and similarity in distributed systems. In: Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, PODC \u201985, pp. 13\u201322. Association for Computing Machinery, New York, NY, USA (1985). https:\/\/doi.org\/10.1145\/323596.323598","DOI":"10.1145\/323596.323598"},{"key":"150_CR19","doi-asserted-by":"crossref","unstructured":"Kilgallin, J., Vasko, R.: Factoring RSA keys in the IoT era. In: 2019 First IEEE International Conference on Trust, Privacy and Security in Intelligent Systems and Applications (TPS-ISA), pp. 184\u2013189 (2019)","DOI":"10.1109\/TPS-ISA48467.2019.00030"},{"key":"150_CR20","doi-asserted-by":"publisher","DOI":"10.1145\/2699440","author":"S Kutten","year":"2015","unstructured":"Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., Trehan, A.: On the complexity of universal leader election. J. ACM (2015). https:\/\/doi.org\/10.1145\/2699440","journal-title":"J. ACM"},{"key":"150_CR21","unstructured":"Le\u00a0Lann, G.: Distributed systems-towards a formal approach. In: Proceedings of the 7th IFIP Congress, pp. 155\u2013160. International Federation for Information Processing (1977)"},{"key":"150_CR22","unstructured":"Matherly, J.: Duplicate SSH Keys Everywhere (2015). https:\/\/blog.shodan.io\/duplicate-ssh-keys-everywhere\/"},{"key":"150_CR23","doi-asserted-by":"publisher","unstructured":"Mendes, H., Tasson, C., Herlihy, M.: Distributed computability in byzantine asynchronous systems. In: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC \u201914, pp. 704\u2013713. Association for Computing Machinery, New York, NY, USA (2014). https:\/\/doi.org\/10.1145\/2591796.2591853","DOI":"10.1145\/2591796.2591853"},{"issue":"1","key":"150_CR24","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0743-7315(90)90074-Y","volume":"8","author":"D Peleg","year":"1990","unstructured":"Peleg, D.: Time-optimal leader election in general networks. J. Parallel Distrib. Comput. 8(1), 96\u201399 (1990). https:\/\/doi.org\/10.1016\/0743-7315(90)90074-Y","journal-title":"J. Parallel Distrib. Comput."},{"key":"150_CR25","doi-asserted-by":"publisher","unstructured":"Saks, M., Zaharoglou, F.: Wait-free k-set agreement is impossible: the topology of public knowledge. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC \u201993, pp. 101\u2013110. Association for Computing Machinery, New York, NY, USA (1993). https:\/\/doi.org\/10.1145\/167088.167122","DOI":"10.1145\/167088.167122"},{"issue":"1","key":"150_CR26","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1006\/inco.1994.1065","volume":"113","author":"B Schieber","year":"1994","unstructured":"Schieber, B., Snir, M.: Calling names on nameless networks. Inf. Comput. 113(1), 80\u2013101 (1994). https:\/\/doi.org\/10.1006\/inco.1994.1065","journal-title":"Inf. Comput."},{"issue":"345\u2013363","key":"150_CR27","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1112\/plms\/s2-42.1.230","volume":"58","author":"AM Turing","year":"1936","unstructured":"Turing, A.M.: On computable numbers, with an application to the entscheidungsproblem. J. Math. 58(345\u2013363), 5 (1936). https:\/\/doi.org\/10.1112\/plms\/s2-42.1.230","journal-title":"J. Math."},{"issue":"1","key":"150_CR28","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1109\/71.481599","volume":"7","author":"M Yamashita","year":"1996","unstructured":"Yamashita, M., Kameda, T.: Computing on anonymous networks. I. Characterizing the solvable cases. IEEE Trans. Parallel Distrib. Syst. 7(1), 69\u201389 (1996). https:\/\/doi.org\/10.1109\/71.481599","journal-title":"IEEE Trans. Parallel Distrib. Syst."}],"container-title":["Journal of Applied and Computational Topology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41468-023-00150-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41468-023-00150-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41468-023-00150-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T12:08:08Z","timestamp":1728389288000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41468-023-00150-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,13]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["150"],"URL":"https:\/\/doi.org\/10.1007\/s41468-023-00150-9","relation":{},"ISSN":["2367-1726","2367-1734"],"issn-type":[{"value":"2367-1726","type":"print"},{"value":"2367-1734","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,13]]},"assertion":[{"value":"2 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 September 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 October 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 November 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"P.\u00a0Fraigniaud is supported in part by ANR projects DESCARTES and FREDDA, and additional support from the ANR Project DUCAT (ref. ANR-20-CE48-0006). R.\u00a0Gelles is supported in part by ISF Grant No.\u00a01078\/17 and BSF Grant No.\u00a02020277. R.\u00a0Gelles would like to thank Paderborn University and CISPA\u2013Helmholtz Center for Information Security for hosting him. Z.\u00a0Lotker declares no financial interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}