{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,5]],"date-time":"2023-01-05T10:51:22Z","timestamp":1672915882163},"reference-count":8,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2008,12]]},"abstract":"<jats:p> This paper focuses on the self-stabilizing leader election algorithm of Xu and Srimani [10] that finds a leader in a tree graph. The worst case execution time for this algorithm is O(N<jats:sup>4<\/jats:sup>), where N is the number of nodes in the tree. We show that the average execution time for this algorithm, assuming two different scenarios, is much lower than O(N<jats:sup>4<\/jats:sup>). In the first scenario, the algorithm assumes an equiprobable daemon and it only privileges a single node at a time. The average execution time for this case is O(N<jats:sup>2<\/jats:sup>). For the second case, the algorithm can privilege multiple nodes at a time. We eliminate the daemon from this algorithm by making random choices to avoid interference between neighboring nodes. The execution time for this case is O(N). We also show that for specific tree graphs, these results reduce even more. <\/jats:p>","DOI":"10.1142\/s0129054108006340","type":"journal-article","created":{"date-parts":[[2009,1,5]],"date-time":"2009-01-05T04:36:29Z","timestamp":1231130189000},"page":"1387-1402","source":"Crossref","is-referenced-by-count":3,"title":["ANALYSIS OF THE AVERAGE EXECUTION TIME FOR A SELF-STABILIZING LEADER ELECTION ALGORITHM"],"prefix":"10.1142","volume":"19","author":[{"given":"JOS\u00c9 ALBERTO","family":"FERN\u00c1NDEZ-ZEPEDA","sequence":"first","affiliation":[{"name":"Department of Computer Science, CICESE, Km. 107 Carretera Tijuana-Ensenada, Ensenada, B. C. 22860, Mexico"}]},{"given":"JUAN PAULO","family":"ALVARADO-MAGA\u00d1A","sequence":"additional","affiliation":[{"name":"Department of Computer Science, CICESE, Km. 107 Carretera Tijuana-Ensenada, Ensenada, B. C. 22860, Mexico"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.0059"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/6156.001.0001"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1109\/71.588622"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1145\/361179.361202"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00121-4"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1145\/169683.174161"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1145\/151254.151256"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054106003851"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054108006340","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:32:49Z","timestamp":1565123569000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054108006340"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,12]]},"references-count":8,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,12]]}},"alternative-id":["10.1142\/S0129054108006340"],"URL":"https:\/\/doi.org\/10.1142\/s0129054108006340","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,12]]}}}