{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T04:26:18Z","timestamp":1747196778315,"version":"3.40.5"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2014,12,5]],"date-time":"2014-12-05T00:00:00Z","timestamp":1417737600000},"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":["Distrib. Comput."],"published-print":{"date-parts":[[2015,8]]},"DOI":"10.1007\/s00446-014-0237-0","type":"journal-article","created":{"date-parts":[[2014,12,4]],"date-time":"2014-12-04T13:07:48Z","timestamp":1417698468000},"page":"221-232","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Knowledge, level of symmetry, and time of leader election"],"prefix":"10.1007","volume":"28","author":[{"given":"Emanuele G.","family":"Fusco","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,12,5]]},"reference":[{"key":"237_CR1","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processors (Extended Abstract). In: Proceeding of the 12th Annual ACM Symposium on Theory of Computing (STOC 1980), pp. 82\u201393","DOI":"10.1145\/800141.804655"},{"key":"237_CR2","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1145\/48014.48247","volume":"35","author":"H Attiya","year":"1988","unstructured":"Attiya, H., Snir, M., Warmuth, M.: Computing on an anonymous ring. J. ACM 35, 845\u2013875 (1988)","journal-title":"J. ACM"},{"key":"237_CR3","doi-asserted-by":"crossref","unstructured":"Attiya, H., Snir, M.: Better computing on the anonymous ring. J. Algorithms 12, 204\u2013238 (1991)","DOI":"10.1016\/0196-6774(91)90002-G"},{"key":"237_CR4","unstructured":"Boldi, P., Shammah, S., Vigna, S., Codenotti, B., Gemmell, P., Simon, J.: Symmetry breaking in anonymous networks: characterizations. In: Proceedings of the 4th Israel Symposium on Theory of Computing and Systems, (ISTCS 1996), pp. 16\u201326"},{"key":"237_CR5","doi-asserted-by":"crossref","unstructured":"Boldi, P., Vigna, S.: Computing anonymously with arbitrary knowledge. In: Proceedings of the 18th ACM Symposium on Principles of Distributed Computing, pp. 181\u2013188 (1999)","DOI":"10.1145\/301308.301355"},{"key":"237_CR6","unstructured":"Burns, J.E.: A formal model for message passing systems. Technical Report TR-91, Computer Science Department, Indiana University, Bloomington, September (1980)"},{"key":"237_CR7","doi-asserted-by":"crossref","unstructured":"Chalopin, J.: Local computations on closed unlabelled edges: the election problem and the naming problem. In: Proceedings of the SOFSEM 2005: Theory and Practice of Computer Science, pp. 82\u201391","DOI":"10.1007\/978-3-540-30577-4_11"},{"key":"237_CR8","doi-asserted-by":"crossref","unstructured":"Chalopin, J., Mazurkiewicz, A.W., M\u00e9tivier, Y.: Labelled (Hyper) graphs, negotiations and the naming problem. In: Proceedings of the 4th International Conference on Graph Transformations (ICGT 2008), pp. 54\u201368","DOI":"10.1007\/978-3-540-87405-8_5"},{"key":"237_CR9","doi-asserted-by":"crossref","unstructured":"Chalopin, J., M\u00e9tivier, Y.: Election and local computations on edges. In: Proceedings of the Foundations of Software Science and Computation Structures (FoSSaCS 2004), pp. 90\u2013104","DOI":"10.1007\/978-3-540-24727-2_8"},{"key":"237_CR10","unstructured":"Dereniowski, D., Kosowski, A., Pajak, D.: Distinguishing views in symmetric networks: a tight lower bound. Technical Report hal-00875370, version 2, Inria, October (2013)"},{"key":"237_CR11","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0304-3975(94)00178-L","volume":"145","author":"K Diks","year":"1995","unstructured":"Diks, K., Kranakis, E., Malinowski, A., Pelc, A.: Anonymous wireless rings. Theor. Comput. Sci. 145, 95\u2013109 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"237_CR12","doi-asserted-by":"crossref","first-page":"333","DOI":"10.3233\/FUN-2004-59402","volume":"59","author":"S Dobrev","year":"2004","unstructured":"Dobrev, S., Pelc, A.: Leader election in rings with nonunique labels. Fundam. Inform. 59, 333\u2013347 (2004)","journal-title":"Fundam. Inform."},{"issue":"2","key":"237_CR13","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/j.jpdc.2003.11.007","volume":"64","author":"P Flocchini","year":"2004","unstructured":"Flocchini, P., Kranakis, E., Krizanc, D., Luccio, F.L., Santoro, N.: Sorting and election in anonymous asynchronous rings. J. Parallel Distrib. Comput. 64(2), 254\u2013265 (2004)","journal-title":"J. Parallel Distrib. Comput."},{"key":"237_CR14","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1145\/7531.7919","volume":"34","author":"GN Fredrickson","year":"1987","unstructured":"Fredrickson, G.N., Lynch, N.A.: Electing a leader in a synchronous ring. J. ACM 34, 98\u2013115 (1987)","journal-title":"J. ACM"},{"key":"237_CR15","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/s00446-011-0131-y","volume":"24","author":"E Fusco","year":"2011","unstructured":"Fusco, E., Pelc, A.: How much memory is needed for leader election. Distrib. Comput. 24, 65\u201378 (2011)","journal-title":"Distrib. Comput."},{"key":"237_CR16","doi-asserted-by":"crossref","unstructured":"Haddar, M.A., Kacem, A.H., M\u00e9tivier, Y., Mosbah, M., Jmaiel, M.: Electing a leader in the local computation model using mobile agents. In: Proceedings of the 6th ACS\/IEEE International Conference on Computer Systems and Applications (AICCSA 2008), pp. 473\u2013480","DOI":"10.1109\/AICCSA.2008.4493575"},{"key":"237_CR17","doi-asserted-by":"crossref","unstructured":"Hendrickx, J.M.: Views in a graph: To which depth must equality be checked? IEEE Trans. Parallel Distrib. Syst. 25, 1907\u20131912 (2014)","DOI":"10.1109\/TPDS.2013.232"},{"key":"237_CR18","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1145\/359024.359029","volume":"23","author":"DS Hirschberg","year":"1980","unstructured":"Hirschberg, D.S., Sinclair, J.B.: Decentralized extrema-finding in circular configurations of processes. Commun. ACM 23, 627\u2013628 (1980)","journal-title":"Commun. ACM"},{"key":"237_CR19","doi-asserted-by":"crossref","unstructured":"Jurdzinski, T., Kutylowski, M., Zatopianski, J.: Efficient algorithms for leader election in radio networks. In: Proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC 2002), pp. 51\u201357","DOI":"10.1145\/571825.571833"},{"key":"237_CR20","doi-asserted-by":"crossref","first-page":"1164","DOI":"10.1016\/j.jcss.2013.04.003","volume":"79","author":"D Kowalski","year":"2013","unstructured":"Kowalski, D., Pelc, A.: Leader election in ad hoc radio networks: a keen ear helps. J. Comput. Syst. Sci. 79, 1164\u20131180 (2013)","journal-title":"J. Comput. Syst. Sci."},{"key":"237_CR21","unstructured":"Kranakis, E.: Symmetry and computability in anonymous networks: a brief survey. In: Proceedings of the 3rd International Conference on Structural Information and Communication Complexity, pp. 1\u201316 (1997)"},{"key":"237_CR22","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1006\/inco.1994.1086","volume":"114","author":"E Kranakis","year":"1994","unstructured":"Kranakis, E., Krizanc, D., van der Berg, J.: Computing boolean functions on anonymous networks. Inform. Comput. 114, 214\u2013236 (1994)","journal-title":"Inform. Comput."},{"key":"237_CR23","unstructured":"Le Lann, G.: Distributed systems\u2014towards a formal approach. In: Proceedings of the IFIP Congress, North Holland, pp. 155\u2013160 (1977)"},{"key":"237_CR24","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1109\/TPDS.2002.1003864","volume":"13","author":"K Nakano","year":"2002","unstructured":"Nakano, K., Olariu, S.: Uniform leader election protocols for radio networks. IEEE Trans. Parallel Distrib. Syst. 13, 516\u2013526 (2002)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"issue":"1","key":"237_CR25","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0166-218X(93)E0133-J","volume":"56","author":"N Norris","year":"1995","unstructured":"Norris, N.: Universal covers of graphs: isomorphism to depth $$N-1$$ N - 1 implies isomorphism to all depths. Discret. Appl. Math. 56(1), 61\u201374 (1995)","journal-title":"Discret. Appl. Math."},{"key":"237_CR26","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed computing, a locality-sensitive approach. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"237_CR27","doi-asserted-by":"crossref","first-page":"758","DOI":"10.1145\/69622.357194","volume":"4","author":"GL Peterson","year":"1982","unstructured":"Peterson, G.L.: An $$O(n \\log n)$$ O ( n log n ) unidirectional distributed algorithm for the circular extrema problem. ACM Trans. Program. Lang. Syst. 4, 758\u2013762 (1982)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"237_CR28","doi-asserted-by":"crossref","unstructured":"Sakamoto, N.: Comparison of initial conditions for distributed algorithms on anonymous networks. In: Proceedings of the 18th ACM Symposium on Principles of Distributed Computing (PODC 1999), pp. 173\u2013179","DOI":"10.1145\/301308.301352"},{"key":"237_CR29","doi-asserted-by":"crossref","first-page":"468","DOI":"10.1137\/0215032","volume":"15","author":"DE Willard","year":"1986","unstructured":"Willard, D.E.: Log-logarithmic selection resolution protocols in a multiple access channel. SIAM J. Comput. 15, 468\u2013477 (1986)","journal-title":"SIAM J. Comput."},{"key":"237_CR30","doi-asserted-by":"crossref","unstructured":"Yamashita, M., Kameda, T.: Computing on anonymous networks. In: Proceedings of the 7th ACM Symposium on Principles of Distributed Computing (PODC 1988), pp. 117\u2013130","DOI":"10.1145\/62546.62568"},{"key":"237_CR31","doi-asserted-by":"crossref","unstructured":"Yamashita, M., Kameda, T.: Electing a leader when processor identity numbers are not distinct. In: Proceedings of the 3rd Workshop on Distributed Algorithms, LNCS Vol 392, Springer, (WDAG 1989), 303\u2013314","DOI":"10.1007\/3-540-51687-5_52"},{"key":"237_CR32","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1109\/71.481599","volume":"7","author":"M Yamashita","year":"1996","unstructured":"Yamashita, M., Kameda, T.: Computing on anonymous networks: part I\u2013characterizing the solvable cases. IEEE Trans. Parallel Distrib. Syst. 7, 69\u201389 (1996)","journal-title":"IEEE Trans. Parallel Distrib. Syst."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-014-0237-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-014-0237-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-014-0237-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T23:02:24Z","timestamp":1747177344000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-014-0237-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,5]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["237"],"URL":"https:\/\/doi.org\/10.1007\/s00446-014-0237-0","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2014,12,5]]}}}