{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:45Z","timestamp":1740109305652,"version":"3.37.3"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,11,5]],"date-time":"2021-11-05T00:00:00Z","timestamp":1636070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,11,5]],"date-time":"2021-11-05T00:00:00Z","timestamp":1636070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-16-CE40-0023","ANR-16-CE25-0009"],"award-info":[{"award-number":["ANR-16-CE40-0023","ANR-16-CE25-0009"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,1]]},"DOI":"10.1007\/s00453-021-00878-9","type":"journal-article","created":{"date-parts":[[2021,11,5]],"date-time":"2021-11-05T06:03:01Z","timestamp":1636092181000},"page":"85-123","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Optimized Silent Self-Stabilizing Scheme for Tree-Based Constructions"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5405-9169","authenticated-orcid":false,"given":"St\u00e9phane","family":"Devismes","sequence":"first","affiliation":[]},{"given":"David","family":"Ilcinkas","sequence":"additional","affiliation":[]},{"given":"Colette","family":"Johnen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,5]]},"reference":[{"key":"878_CR1","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1016\/j.ic.2016.09.002","volume":"254","author":"K Altisen","year":"2017","unstructured":"Altisen, K., Cournier, A., Devismes, S., Durand, A., Petit, F.: Self-stabilizing leader election in polynomial steps. Inf. Comput. 254, 330\u2013366 (2017). https:\/\/doi.org\/10.1016\/j.ic.2016.09.002","journal-title":"Inf. Comput."},{"key":"878_CR2","doi-asserted-by":"publisher","unstructured":"Altisen, K., Devismes, S., Dubois, S., Petit, F.: Introduction to Distributed Self-stabilizing Algorithms. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers (2019). https:\/\/doi.org\/10.2200\/S00908ED1V01Y201903DCT015","DOI":"10.2200\/S00908ED1V01Y201903DCT015"},{"key":"878_CR3","doi-asserted-by":"crossref","unstructured":"Arora, A., Gouda, M., Herman, T.: Composite routing protocols. In: the 2nd IEEE Symposium on Parallel and Distributed Processing (SPDP\u201990), pp. 70\u201378 (1990)","DOI":"10.1109\/SPDP.1990.143510"},{"key":"878_CR4","doi-asserted-by":"crossref","unstructured":"Beauquier, J., Gradinariu, M., Johnen, C.: Cross-over composition\u2014enforcement of fairness under unfair adversary. In: 5th International Workshop on Self-Stabilizing Systems, (WSS 2001), Springer LNCS 2194, pp. 19\u201334 (2001)","DOI":"10.1007\/3-540-45438-1_2"},{"key":"878_CR5","doi-asserted-by":"crossref","unstructured":"Blin, L., Cournier, A., Villain, V.: An improved snap-stabilizing PIF algorithm. In: Huang, S., Herman, T. (eds.) Self-Stabilizing Systems, 6th International Symposium, SSS 2003. Lecture Notes in Computer Science, vol. 2704, pp. 199\u2013214. Springer, San Francisco, CA, USA (2003)","DOI":"10.1007\/3-540-45032-7_15"},{"key":"878_CR6","doi-asserted-by":"crossref","unstructured":"Blin, L., Fraigniaud, P., Patt-Shamir, B.: On proof-labeling schemes versus silent self-stabilizing algorithms. In: 16th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2014), Springer LNCS 8756, pp. 18\u201332 (2014)","DOI":"10.1007\/978-3-319-11764-5_2"},{"key":"878_CR7","doi-asserted-by":"crossref","unstructured":"Blin, L., Potop-Butucaru, M., Rovedakis, S., Tixeuil, S.: Loop-free super-stabilizing spanning tree construction. In: the 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS\u201910), Springer LNCS 6366, pp. 50\u201364 (2010)","DOI":"10.1007\/978-3-642-16023-3_7"},{"issue":"3","key":"878_CR8","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s004460100062","volume":"15","author":"P Boldi","year":"2002","unstructured":"Boldi, P., Vigna, S.: Universal dynamic synchronous self-stabilization. Distrib. Comput. 15(3), 137\u2013153 (2002)","journal-title":"Distrib. Comput."},{"key":"878_CR9","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.jpdc.2015.02.001","volume":"81\u201382","author":"F Carrier","year":"2015","unstructured":"Carrier, F., Datta, A.K., Devismes, S., Larmore, L.L., Rivierre, Y.: Self-stabilizing (f, g)-alliances with safe convergence. J. Parallel Distrib. Comput. 81\u201382, 11\u201323 (2015). https:\/\/doi.org\/10.1016\/j.jpdc.2015.02.001","journal-title":"J. Parallel Distrib. Comput."},{"issue":"4","key":"878_CR10","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1109\/TSE.1982.235573","volume":"8","author":"EJH Chang","year":"1982","unstructured":"Chang, E.J.H.: Echo algorithms: depth parallel operations on general graphs. IEEE Trans. Softw. Eng. 8(4), 391\u2013401 (1982)","journal-title":"IEEE Trans. Softw. Eng."},{"key":"878_CR11","doi-asserted-by":"publisher","unstructured":"Cobb, J.A., Huang, C.T.: Stabilization of maximal-metric routing without knowledge of network size. In: 2009 International Conference on Parallel and Distributed Computing, Applications and Technologies, pp. 306\u2013311 (2009). https:\/\/doi.org\/10.1109\/PDCAT.2009.75","DOI":"10.1109\/PDCAT.2009.75"},{"issue":"6","key":"878_CR12","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0020-0190(94)90103-1","volume":"49","author":"Z Collin","year":"1994","unstructured":"Collin, Z., Dolev, S.: Self-stabilizing depth-first search. Inf. Process. Lett. 49(6), 297\u2013301 (1994)","journal-title":"Inf. Process. Lett."},{"key":"878_CR13","doi-asserted-by":"crossref","unstructured":"Cournier, A.: A new polynomial silent stabilizing spanning-tree construction algorithm. In: International Colloquium on Structural Information and Communication Complexity, pp. 141\u2013153. Springer (2009)","DOI":"10.1007\/978-3-642-11476-2_12"},{"key":"878_CR14","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.tcs.2016.01.036","volume":"626","author":"A Cournier","year":"2016","unstructured":"Cournier, A., Datta, A.K., Devismes, S., Petit, F., Villain, V.: The expressive power of snap-stabilization. Theor. Comput. Sci. 626, 40\u201366 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2016.01.036","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"878_CR15","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1093\/comjnl\/bxh154","volume":"49","author":"A Cournier","year":"2006","unstructured":"Cournier, A., Devismes, S., Petit, F., Villain, V.: Snap-stabilizing depth-first search on arbitrary networks. Comput. J. 49(3), 268\u2013280 (2006)","journal-title":"Comput. J."},{"key":"878_CR16","doi-asserted-by":"crossref","unstructured":"Cournier, A., Devismes, S., Villain, V.: A snap-stabilizing dfs with a lower space requirement. In: Symposium on Self-Stabilizing Systems, pp. 33\u201347. Springer (2005)","DOI":"10.1007\/11577327_3"},{"issue":"1","key":"878_CR17","doi-asserted-by":"publisher","first-page":"6:1","DOI":"10.1145\/1462187.1462193","volume":"4","author":"A Cournier","year":"2009","unstructured":"Cournier, A., Devismes, S., Villain, V.: Light enabling snap-stabilization of fundamental protocols. TAAS 4(1), 6:1-6:27 (2009). https:\/\/doi.org\/10.1145\/1462187.1462193","journal-title":"TAAS"},{"issue":"1","key":"878_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1462187.1462193","volume":"4","author":"A Cournier","year":"2009","unstructured":"Cournier, A., Devismes, S., Villain, V.: Light enabling snap-stabilization of fundamental protocols. ACM Trans. Auton. Adapt. Syst. 4(1), 1\u201327 (2009)","journal-title":"ACM Trans. Auton. Adapt. Syst."},{"key":"878_CR19","doi-asserted-by":"crossref","unstructured":"Cournier, A., Rovedakis, S., Villain, V.: The first fully polynomial stabilizing algorithm for BFS tree construction. In: The 15th International Conference on Principles of Distributed Systems (OPODIS\u201911). Springer LNCS 7109, pp. 159\u2013174 (2011)","DOI":"10.1007\/978-3-642-25873-2_12"},{"key":"878_CR20","doi-asserted-by":"crossref","unstructured":"Cournier, A.: A lower bound for the $$Max + 1$$ algorithm. https:\/\/home.mis.u-picardie.fr\/~cournier\/MaxPlusUn.pdf (2009). Accessed 11 Feb 2009","DOI":"10.1109\/IPDPS.2009.5160997"},{"key":"878_CR21","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/j.tcs.2016.02.010","volume":"626","author":"AK Datta","year":"2016","unstructured":"Datta, A.K., Devismes, S., Heurtefeux, K., Larmore, L.L., Rivierre, Y.: Competitive self-stabilizing k-clustering. Theor. Comput. Sci. 626, 110\u2013133 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2016.02.010","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"878_CR22","first-page":"1","volume":"1","author":"AK Datta","year":"2001","unstructured":"Datta, A.K., Gurumurthy, S., Petit, F., Villain, V.: Self-stabilizing network orientation algorithms in arbitrary rooted networks. Stud. Inform. Univ. 1(1), 1\u201322 (2001)","journal-title":"Stud. Inform. Univ."},{"issue":"1","key":"878_CR23","doi-asserted-by":"publisher","first-page":"116","DOI":"10.15803\/ijnc.3.1_116","volume":"3","author":"AK Datta","year":"2013","unstructured":"Datta, A.K., Larmore, L.L., Devismes, S., Heurtefeux, K., Rivierre, Y.: Self-stabilizing small k-dominating sets. IJNC 3(1), 116\u2013136 (2013)","journal-title":"IJNC"},{"issue":"11","key":"878_CR24","first-page":"1532","volume":"71","author":"AK Datta","year":"2011","unstructured":"Datta, A.K., Larmore, L.L., Vemula, P.: An o(n)-time self-stabilizing leader election algorithm. IPDC 71(11), 1532\u20131544 (2011)","journal-title":"IPDC"},{"issue":"40","key":"878_CR25","doi-asserted-by":"publisher","first-page":"5541","DOI":"10.1016\/j.tcs.2010.05.001","volume":"412","author":"AK Datta","year":"2011","unstructured":"Datta, A.K., Larmore, L.L., Vemula, P.: Self-stabilizing leader election in optimal space under an arbitrary scheduler. Theor. Comput. Sci. 412(40), 5541\u20135561 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"878_CR26","doi-asserted-by":"publisher","unstructured":"Dela\u00ebt, S., Ducourthial, B., Tixeuil, S.: Self-stabilization with r-operators revisited. J. Aerosp. Comput. Inf. Commun. (JACIC) 3(10), 498\u2013514 (2006). https:\/\/doi.org\/10.2514\/1.19848","DOI":"10.2514\/1.19848"},{"key":"878_CR27","unstructured":"Devismes, S., Ilcinkas, D., Johnen, C.: Self-stabilizing disconnected components detection and rooted shortest-path tree maintenance in polynomial steps. In: P.\u00a0Fatourou, E.\u00a0Jim\u00e9nez, F.\u00a0Pedone (eds.) 20th International Conference on Principles of Distributed Systems, OPODIS 2016, December 13-16, 2016, Madrid, Spain, LIPIcs, vol.\u00a070, pp. 10:1\u201310:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016)"},{"key":"878_CR28","doi-asserted-by":"crossref","unstructured":"Devismes, S., Ilcinkas, D., Johnen, C.: Silent self-stabilizing scheme for spanning-tree-like constructions. In: R.C. Hansdah, D.\u00a0Krishnaswamy, N.\u00a0Vaidya (eds.) Proceedings of the 20th International Conference on Distributed Computing and Networking, ICDCN 2019, Bangalore, India, January 04-07, 2019, pp. 158\u2013167. ACM (2019)","DOI":"10.1145\/3288599.3288607"},{"key":"878_CR29","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.jpdc.2016.06.003","volume":"97","author":"S Devismes","year":"2016","unstructured":"Devismes, S., Johnen, C.: Silent self-stabilizing BFS tree algorithms revisited. J. Parallel Distrib. Comput. 97, 11\u201323 (2016). https:\/\/doi.org\/10.1016\/j.jpdc.2016.06.003","journal-title":"J. Parallel Distrib. Comput."},{"issue":"11","key":"878_CR30","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1145\/361179.361202","volume":"17","author":"EW Dijkstra","year":"1974","unstructured":"Dijkstra, E.W.: Self-stabilizing systems in spite of distributed control. Commun. ACM 17(11), 643\u2013644 (1974)","journal-title":"Commun. ACM"},{"key":"878_CR31","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/6156.001.0001","volume-title":"Self-stabilization","author":"S Dolev","year":"2000","unstructured":"Dolev, S.: Self-stabilization. MIT Press, Cambridge (2000)"},{"issue":"6","key":"878_CR32","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/s002360050180","volume":"36","author":"S Dolev","year":"1999","unstructured":"Dolev, S., Gouda, M.G., Schneider, M.: Memory requirements for silent stabilization. Acta Inf. 36(6), 447\u2013462 (1999)","journal-title":"Acta Inf."},{"issue":"3","key":"878_CR33","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/PL00008934","volume":"14","author":"B Ducourthial","year":"2001","unstructured":"Ducourthial, B., Tixeuil, S.: Self-stabilization with r-operators. Distrib. Comput. 14(3), 147\u2013162 (2001). https:\/\/doi.org\/10.1007\/PL00008934","journal-title":"Distrib. Comput."},{"key":"878_CR34","unstructured":"Glacet, C., Hanusse, N., Ilcinkas, D., Johnen, C.: Disconnected components detection and rooted shortest-path tree maintenance in networks. In: the 16th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS\u201914). Springer LNCS 8736, pp. 120\u2013134 (2014)"},{"key":"878_CR35","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2019.05.006","author":"C Glacet","year":"2019","unstructured":"Glacet, C., Hanusse, N., Ilcinkas, D., Johnen, C.: Disconnected components detection and rooted shortest-path tree maintenance in networks. J. Parallel Distrib. Comput (2019). https:\/\/doi.org\/10.1016\/j.jpdc.2019.05.006","journal-title":"J. Parallel Distrib. Comput"},{"key":"878_CR36","doi-asserted-by":"crossref","unstructured":"Godard, E.: Snap-stabilizing tasks in anonymous networks. In: Stabilization. Safety, and Security of Distributed Systems (SSS\u201916), Lecture Notes in Computer Science, pp. 170\u2013184. Springer, Cham (2016)","DOI":"10.1007\/978-3-319-49259-9_14"},{"issue":"9","key":"878_CR37","doi-asserted-by":"publisher","first-page":"911","DOI":"10.1109\/32.92911","volume":"17","author":"MG Gouda","year":"1991","unstructured":"Gouda, M.G., Herman, T.: Adaptive programming. IEEE Trans. Softw. Eng. 17(9), 911\u2013921 (1991)","journal-title":"IEEE Trans. Softw. Eng."},{"key":"878_CR38","unstructured":"G\u00e4rtner, F.C.: A survey of self-stabilizing spanning-tree construction algorithms. Tech. rep, Swiss Federal Institute of Technolog (EPFL) (2003)"},{"issue":"2","key":"878_CR39","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0020-0190(92)90264-V","volume":"41","author":"ST Huang","year":"1992","unstructured":"Huang, S.T., Chen, N.S.: A self-stabilizing algorithm for constructing breadth-first trees. Inf. Process. Lett. 41(2), 109\u2013117 (1992)","journal-title":"Inf. Process. Lett."},{"key":"878_CR40","unstructured":"Ilcinkas, D., Johnen, C., Laplace, R.: STlC meta-algorithm on JBotSim, SWHID: $$\\langle $$swh:1:rev:65238c18e332117de59682903f828be18ad6a91f;origin=https:\/\/gitlab.com\/re mikey\/jbotsim-stlc.git$$\\rangle $$. https:\/\/archive.softwareheritage.org\/SWHID"},{"issue":"1","key":"878_CR41","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/BF02278852","volume":"7","author":"S Katz","year":"1993","unstructured":"Katz, S., Perry, K.J.: Self-stabilizing extensions for message-passing systems. Distrib. Comput. 7(1), 17\u201326 (1993)","journal-title":"Distrib. Comput."},{"issue":"4","key":"878_CR42","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s00446-010-0095-3","volume":"22","author":"A Korman","year":"2010","unstructured":"Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. Distrib. Comput. 22(4), 215\u2013233 (2010). https:\/\/doi.org\/10.1007\/s00446-010-0095-3","journal-title":"Distrib. Comput."},{"key":"878_CR43","doi-asserted-by":"crossref","unstructured":"Kosowski, A., Kuszner, L.: A self-stabilizing algorithm for finding a spanning tree in a polynomial number of moves. In: 6th International Conference Parallel Processing and Applied Mathematics, (PPAM\u201905). Springer LNCS 3911, pp. 75\u201382 (2005)","DOI":"10.1007\/11752578_10"},{"key":"878_CR44","volume-title":"Communication Networks","author":"A Leon-Garcia","year":"2004","unstructured":"Leon-Garcia, A., Widjaja, I.: Communication Networks, 2nd edn. McGraw-Hill Inc, New York (2004)","edition":"2"},{"issue":"1","key":"878_CR45","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1109\/TIT.1983.1056620","volume":"29","author":"A Segall","year":"1983","unstructured":"Segall, A.: Distributed network protocols. IEEE Trans. Inf. Theory 29(1), 23\u201334 (1983)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"878_CR46","volume-title":"Distributed Systems and Computer Networks","author":"M Sloman","year":"1987","unstructured":"Sloman, M., Kramer, J.: Distributed Systems and Computer Networks. Prentice Hall, Hoboken (1987)"},{"key":"878_CR47","volume-title":"Introduction to Distributed Algorithms","author":"G Tel","year":"2001","unstructured":"Tel, G.: Introduction to Distributed Algorithms, 2nd edn. Cambridge University Press, Cambridge (2001)","edition":"2"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00878-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00878-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00878-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,11]],"date-time":"2024-09-11T14:57:01Z","timestamp":1726066621000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00878-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,5]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["878"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00878-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,11,5]]},"assertion":[{"value":"3 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}