{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:48:37Z","timestamp":1770994117486,"version":"3.50.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,3,6]],"date-time":"2017-03-06T00:00:00Z","timestamp":1488758400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSERC Discovery","award":["8136-2013"],"award-info":[{"award-number":["8136-2013"]}]},{"name":"ANR project DISPLEXITY","award":["ANR-11BS02-014"],"award-info":[{"award-number":["ANR-11BS02-014"]}]},{"name":"Research Chair in Distributed Computing at the Universit\u00e9 du Qu\u00e9bec en Outaouais"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,7,31]]},"abstract":"\n Leader election is one of the fundamental problems in distributed computing. It calls for all nodes of a network to agree on a single node, called the\n leader<\/jats:italic>\n . If the nodes of the network have distinct labels, then agreeing on a single node means that all nodes have to output the label of the elected leader. If the nodes of the network are anonymous, the task of leader election is formulated as follows: every node\n v<\/jats:italic>\n of the network must output a simple path, which is coded as a sequence of port numbers, such that all these paths end at a common node, the leader. In this article, we study deterministic leader election in anonymous trees.\n <\/jats:p>\n \n Our aim is to establish tradeoffs between the allocated time \u03c4 and the amount of information that has to be given\n a priori<\/jats:italic>\n to the nodes to enable leader election in time \u03c4 in all trees for which leader election in this time is at all possible. Following the framework of\n algorithms with advice<\/jats:italic>\n , this information (a single binary string) is provided to all nodes at the start by an oracle knowing the entire tree. The length of this string is called the\n size of advice<\/jats:italic>\n . For a given time \u03c4 allocated to leader election, we give upper and lower bounds on the minimum size of advice sufficient to perform leader election in time \u03c4.\n <\/jats:p>\n \n For most values of \u03c4, our upper and lower bounds are either tight up to multiplicative constants, or they differ only by a logarithmic factor. Let\n T<\/jats:italic>\n be an\n n<\/jats:italic>\n -node tree of diameter\n diam<\/jats:italic>\n \u2a7d\n D<\/jats:italic>\n . While leader election in time\n diam<\/jats:italic>\n can be performed without any advice, for time\n diam<\/jats:italic>\n \u2212 1 we give tight upper and lower bounds of \u0398(log\n D<\/jats:italic>\n ). For time\n diam<\/jats:italic>\n \u2212 2 we give tight upper and lower bounds of \u0398(log\n D<\/jats:italic>\n ) for even values of\n diam<\/jats:italic>\n , and tight upper and lower bounds of \u0398(log\n n<\/jats:italic>\n ) for odd values of\n diam<\/jats:italic>\n . Moving to shorter time, in the interval [\u03b2 \u00b7\n diam<\/jats:italic>\n ,\n diam<\/jats:italic>\n \u2212 3] for constant \u03b2 > 1\/2, we prove an upper bound of\n O<\/jats:italic>\n (\n n<\/jats:italic>\n log\n n<\/jats:italic>\n \/\n D<\/jats:italic>\n ) and a lower bound of \u03a9(\n n<\/jats:italic>\n \/\n D<\/jats:italic>\n ), the latter being valid whenever\n diam<\/jats:italic>\n is odd or when the time is at most\n diam<\/jats:italic>\n \u2212 4. Hence, with the exception of the special case when\n diam<\/jats:italic>\n is even and time is exactly\n diam<\/jats:italic>\n \u2212 3, our bounds leave only a logarithmic gap in this time interval. Finally, for time \u03b1 \u00b7\n diam<\/jats:italic>\n for any constant \u03b1 < 1\/2 (except for the case of very small diameters), we again give tight upper and lower bounds, this time \u0398(\n n<\/jats:italic>\n ).\n <\/jats:p>","DOI":"10.1145\/3039870","type":"journal-article","created":{"date-parts":[[2017,3,7]],"date-time":"2017-03-07T19:12:04Z","timestamp":1488913924000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Time vs. Information Tradeoffs for Leader Election in Anonymous Trees"],"prefix":"10.1145","volume":"13","author":[{"given":"Christian","family":"Glacet","sequence":"first","affiliation":[{"name":"CNR -IEIIT, Torino, Italy"}]},{"given":"Avery","family":"Miller","sequence":"additional","affiliation":[{"name":"Universit\u00e9 du Qu\u00e9bec en Outaouais"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[{"name":"Universit\u00e9 du Qu\u00e9bec en Outaouais"}]}],"member":"320","published-online":{"date-parts":[[2017,3,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703437211"},{"key":"e_1_2_1_2_1","volume-title":"Ullman","author":"Aho Alfred V.","year":"1983","unstructured":"Alfred V. Aho , John E. Hopcroft , and Jeffrey D . Ullman . 1983 . Data Structures and Algorithms. Addison-Wesley . Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. 1983. Data Structures and Algorithms. Addison-Wesley."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804655"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90002-G"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.48247"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_35"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 4th Israel Symposium on Theory of Computing and Systems (ISTCS\u201996)","author":"Boldi Paolo","year":"1996","unstructured":"Paolo Boldi , Shella Shammah , Sebastiano Vigna , Bruno Codenotti , Peter Gemmell , and Janos Simon . 1996 . Symmetry breaking in anonymous networks: characterizations . In Proceedings of the 4th Israel Symposium on Theory of Computing and Systems (ISTCS\u201996) . 16--26. Paolo Boldi, Shella Shammah, Sebastiano Vigna, Bruno Codenotti, Peter Gemmell, and Janos Simon. 1996. Symmetry breaking in anonymous networks: characterizations. In Proceedings of the 4th Israel Symposium on Theory of Computing and Systems (ISTCS\u201996). 16--26."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/301308.301355"},{"key":"e_1_2_1_10_1","unstructured":"Flavio Chierichetti. 2012. Personal communication. Flavio Chierichetti. 2012. Personal communication."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2011.10.004"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-013-0196-x"},{"key":"e_1_2_1_13_1","first-page":"585","article-title":"Measuring the problem-relevant information in input","volume":"43","author":"Dobrev Stefan","year":"2009","unstructured":"Stefan Dobrev , Rastislav Kr\u00e1lovic , and Dana Pardubsk\u00e1 . 2009 . Measuring the problem-relevant information in input . ITA 43 , 3 (2009), 585 -- 613 . Stefan Dobrev, Rastislav Kr\u00e1lovic, and Dana Pardubsk\u00e1. 2009. Measuring the problem-relevant information in input. ITA 43, 3 (2009), 585--613.","journal-title":"ITA"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2371077.2371079"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.007"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2003.11.007"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-008-0076-y"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.07.005"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.07.002"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9280-9"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/7531.7919"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118756.3119007"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-014-0237-0"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41527-2_3"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.05.002"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/AICCSA.2008.4493575"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/359024.359029"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.01.004"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/571825.571833"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703433912"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0095-3"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.04.003"},{"key":"e_1_2_1_33_1","volume-title":"IFIP Congress. 155--160","author":"Lann G\u00e9rard Le","year":"1977","unstructured":"G\u00e9rard Le Lann . 1977 . Distributed systems - Towards a formal approach . In IFIP Congress. 155--160 . G\u00e9rard Le Lann. 1977. Distributed systems - Towards a formal approach. In IFIP Congress. 155--160."},{"key":"e_1_2_1_34_1","unstructured":"Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann. Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935772"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2002.1003864"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.08.020"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/69622.357194"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215032"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/645946.675009"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.481599"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3039870","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3039870","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:31Z","timestamp":1750217791000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3039870"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,6]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7,31]]}},"alternative-id":["10.1145\/3039870"],"URL":"https:\/\/doi.org\/10.1145\/3039870","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,6]]},"assertion":[{"value":"2016-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}