{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:17:25Z","timestamp":1759637845641,"version":"3.41.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2018,1,8]],"date-time":"2018-01-08T00:00:00Z","timestamp":1515369600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005739","name":"Universidad Nacional Aut\u00f3noma de M\u00e9xico","doi-asserted-by":"publisher","award":["PAPIIT IA102417"],"award-info":[{"award-number":["PAPIIT IA102417"]}],"id":[{"id":"10.13039\/501100005739","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005739","name":"Universidad Nacional Aut\u00f3noma de M\u00e9xico","doi-asserted-by":"publisher","award":["PAPIIT IN109917"],"award-info":[{"award-number":["PAPIIT IN109917"]}],"id":[{"id":"10.13039\/501100005739","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Cyber-Physical Systems (CPS)","award":["CPSLab project H2020-ICT-644400"],"award-info":[{"award-number":["CPSLab project H2020-ICT-644400"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Braz Comput Soc"],"published-print":{"date-parts":[[2018,12]]},"DOI":"10.1186\/s13173-017-0065-8","type":"journal-article","created":{"date-parts":[[2018,1,8]],"date-time":"2018-01-08T12:06:55Z","timestamp":1515413215000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Convergence and covering on graphs for wait-free robots"],"prefix":"10.1186","volume":"24","author":[{"given":"Armando","family":"Casta\u00f1eda","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergio","family":"Rajsbaum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthieu","family":"Roy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,1,8]]},"reference":[{"issue":"1","key":"65_CR1","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1137\/050645221","volume":"36","author":"N Agmon","year":"2006","unstructured":"Agmon N, Peleg D (2006) Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM J Comput 36(1):56\u201382.","journal-title":"SIAM J Comput"},{"key":"65_CR2","doi-asserted-by":"crossref","unstructured":"Alc\u00e1ntara M, Casta\u00f1eda A, Pe\u00f1aloza DF, Rajsbaum S (2017) Fault-tolerant robot gathering problems on graphs with arbitrary appearing times In: 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS), 493\u2013502.. IEEE.","DOI":"10.1109\/IPDPS.2017.70"},{"issue":"1","key":"65_CR3","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1145\/200836.200869","volume":"42","author":"H Attiya","year":"1995","unstructured":"Attiya H, Bar-Noy A, Dolev D (1995) Sharing memory robustly in message-passing systems. J ACM 42(1):124\u2013142.","journal-title":"J ACM"},{"issue":"3","key":"65_CR4","doi-asserted-by":"crossref","first-page":"524","DOI":"10.1145\/79147.79158","volume":"37","author":"H Attiya","year":"1990","unstructured":"Attiya H, Bar-Noy A, Dolev D, Peleg D, Reischuk R (1990) Renaming in an asynchronous environment. J ACM 37(3):524\u2013548.","journal-title":"J ACM"},{"key":"65_CR5","doi-asserted-by":"crossref","unstructured":"Attiya H, Welch J (2004) Distributed computing: fundamentals, simulations, and advanced topics. Wiley.","DOI":"10.1002\/0471478210"},{"issue":"3","key":"65_CR6","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/s10472-013-9357-7","volume":"67","author":"S Bhattacharya","year":"2013","unstructured":"Bhattacharya S, Lipsky D, Ghrist R, Kumar V (2013) Invariants for homology classes with application to optimal search and planning problem in robotics. Ann Math Artif Intell 67(3):251\u2013281.","journal-title":"Ann Math Artif Intell"},{"issue":"3","key":"65_CR7","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1016\/0196-6774(90)90020-F","volume":"11","author":"O Biran","year":"1990","unstructured":"Biran O, Moran S, Zaks S (1990) A combinatorial characterization of the distributed 1-solvable tasks. J Algoritm 11(3):420\u2013440.","journal-title":"J Algoritm"},{"issue":"3","key":"65_CR8","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/PL00008933","volume":"14","author":"E Borowsky","year":"2001","unstructured":"Borowsky E, Gafni E, Lynch N, Rajsbaum S (2001) The BG distributed simulation algorithm. Distrib Comput 14(3):127\u2013146.","journal-title":"Distrib Comput"},{"key":"65_CR9","doi-asserted-by":"crossref","unstructured":"Borowsky E, Gafni E (1993) Generalized FLP impossibility result for t-resilient asynchronous computations In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, 91\u2013100.","DOI":"10.1145\/167088.167119"},{"key":"65_CR10","doi-asserted-by":"crossref","unstructured":"Bouzid Z, Das S, Tixeuil S (2013) Gathering of mobile robots tolerating multiple crash faults In: Proceedings of the 2013 IEEE 33rd International Conference on Distributed Computing Systems, ICDCS \u201913. IEEE Computer Society, Washington, 337\u2013346.","DOI":"10.1109\/ICDCS.2013.27"},{"issue":"1","key":"65_CR11","doi-asserted-by":"crossref","first-page":"3:1","DOI":"10.1145\/2108242.2108245","volume":"59","author":"A Casta\u00f1eda","year":"2012","unstructured":"Casta\u00f1eda A, Rajsbaum S (2012) New combinatorial topology bounds for renaming: the upper bound. J ACM 59(1):3:1\u20133:49.","journal-title":"J ACM"},{"issue":"3","key":"65_CR12","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/j.cosrev.2011.04.001","volume":"5","author":"A Casta\u00f1eda","year":"2011","unstructured":"Casta\u00f1eda A, Rajsbaum S, Raynal M (2011) The renaming problem in shared memory systems: an introduction. Comput Sci Rev 5(3):229\u2013251.","journal-title":"Comput Sci Rev"},{"issue":"2","key":"65_CR13","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1137\/130936828","volume":"45","author":"A Casta\u00f1eda","year":"2016","unstructured":"Casta\u00f1eda A, Imbs D, Rajsbaum S, Raynal M (2016) Generalized symmetry breaking tasks and nondeterminism in concurrent objects. SIAM J Comput 45(2):379\u2013414.","journal-title":"SIAM J Comput"},{"issue":"1","key":"65_CR14","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1006\/inco.1993.1043","volume":"105","author":"S Chaudhuri","year":"1993","unstructured":"Chaudhuri S (1993) More choices allow more faults: set consensus problems in totally asynchronous systems. Inf Comput 105(1):132\u2013158.","journal-title":"Inf Comput"},{"issue":"P1","key":"65_CR15","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/j.tcs.2015.09.018","volume":"609","author":"S Das","year":"2016","unstructured":"Das S, Flocchini P, Prencipe G, Santoro N, Yamashita M (2016) Autonomous mobile robots with lights. Theor Comput Sci 609(P1):171\u2013184.","journal-title":"Theor Comput Sci"},{"issue":"3","key":"65_CR16","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1145\/5925.5931","volume":"33","author":"D Dolev","year":"1986","unstructured":"Dolev D, Lynch NA, Pinter SS, Stark EW, Weihl WE (1986) Reaching approximate agreement in the presence of faults. J ACM 33(3):499\u2013516.","journal-title":"J ACM"},{"issue":"2","key":"65_CR17","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1145\/3149.214121","volume":"32","author":"MJ Fischer","year":"1985","unstructured":"Fischer MJ, Lynch NA, Paterson M (1985) Impossibility of distributed consensus with one faulty process. J ACM 32(2):374\u2013382.","journal-title":"J ACM"},{"key":"65_CR18","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1007\/978-3-642-16023-3_30","volume-title":"Proceedings of the 12th International Conference on Stabilization, Safety, and Security of Distributed Systems, SSS\u201910","author":"E Gafni","year":"2010","unstructured":"Gafni E, Rajsbaum S (2010) Recursion in distributed computing In: Proceedings of the 12th International Conference on Stabilization, Safety, and Security of Distributed Systems, SSS\u201910, 362\u2013376.. Springer-Verlag, Heidelberg."},{"key":"65_CR19","first-page":"329","volume-title":"Proceedings of the 20th International Conference on Distributed Computing, DISC\u201906","author":"E Gafni","year":"2006","unstructured":"Gafni E, Rajsbaum S, Herlihy M (2006) Subconsensus tasks: renaming is weaker than set agreement In: Proceedings of the 20th International Conference on Distributed Computing, DISC\u201906, 329\u2013338.. Springer-Verlag, Heidelberg."},{"issue":"1","key":"65_CR20","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1145\/114005.102808","volume":"13","author":"M Herlihy","year":"1991","unstructured":"Herlihy M (1991) Wait-free synchronization. ACM Trans Program Lang Syst 13(1):124\u2013149.","journal-title":"ACM Trans Program Lang Syst"},{"key":"65_CR21","volume-title":"Distributed computing through combinatorial topology, 1st edition","author":"M Herlihy","year":"2013","unstructured":"Herlihy M, Kozlov D, Rajsbaum S (2013) Distributed computing through combinatorial topology, 1st edition. Morgan Kaufmann Publishers Inc., San Francisco."},{"key":"65_CR22","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1145\/258533.258652","volume-title":"Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, STOC \u201997","author":"M Herlihy","year":"1997","unstructured":"Herlihy M, Rajsbaum S (1997) The decidability of distributed decision tasks (extended abstract) In: Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, STOC \u201997, 589\u2013598.. ACM, New York."},{"issue":"1","key":"65_CR23","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0304-3975(01)00396-6","volume":"291","author":"M Herlihy","year":"2003","unstructured":"Herlihy M, Rajsbaum S (2003) A classification of wait-free loop agreement tasks. Theor Comput Sci 291(1):55\u201377.","journal-title":"Theor Comput Sci"},{"key":"65_CR24","first-page":"214","volume-title":"Proceedings, chapter Computing in the Presence of Concurrent Solo Executions","author":"M Herlihy","year":"2014","unstructured":"Herlihy M, Rajsbaum S, Raynal M, Stainer J (2014) LATIN 2014: Theoretical Informatics: 11th Latin American Symposium, Montevideo, Uruguay, March 31\u2013April 4, 2014 In: Proceedings, chapter Computing in the Presence of Concurrent Solo Executions, 214\u2013225.. Springer Berlin Heidelberg, Heidelberg."},{"issue":"6","key":"65_CR25","doi-asserted-by":"crossref","first-page":"858","DOI":"10.1145\/331524.331529","volume":"46","author":"M Herlihy","year":"1999","unstructured":"Herlihy M, Shavit N (1999) The topological structure of asynchronous computability. J ACM 46(6):858\u2013923.","journal-title":"J ACM"},{"issue":"2","key":"65_CR26","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1137\/S0097539701397412","volume":"36","author":"G Hoest","year":"2006","unstructured":"Hoest G, Shavit N (2006) Toward a topological characterization of asynchronous complexity. SIAM J Comput 36(2):457\u2013497.","journal-title":"SIAM J Comput"},{"issue":"21-23","key":"65_CR27","doi-asserted-by":"crossref","first-page":"2162","DOI":"10.1016\/j.tcs.2009.01.033","volume":"410","author":"X Liu","year":"2009","unstructured":"Liu X, Xu Z, Pan J (2009) Classifying rendezvous tasks of arbitrary dimension. Theor Comput Sci 410(21-23):2162\u20132173.","journal-title":"Theor Comput Sci"},{"issue":"6","key":"65_CR28","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/s00446-014-0240-5","volume":"28","author":"H Mendes","year":"2015","unstructured":"Mendes H, Herlihy M, Vaidya N, Garg VK (2015) Multidimensional agreement in byzantine systems. Distrib Comput 28(6):423\u2013441.","journal-title":"Distrib Comput"},{"key":"65_CR29","volume-title":"Retrieving topological information for mobile robots provided with grid maps, Number 358 in Communications in Computer and Information Science","author":"D Portugal","year":"2013","unstructured":"Portugal D, Rocha RP (2013) Retrieving topological information for mobile robots provided with grid maps, Number 358 in Communications in Computer and Information Science. Springer Berlin Heidelberg, Heidelberg."},{"key":"65_CR30","doi-asserted-by":"crossref","unstructured":"Saraph V, Herlihy MThe relative power of composite loop agreement tasks In: Proceedings of the International Conference on Principles of Distributed systems (OPODIS), LIPIcs: Leibniz Int. Proc. Informatics, Germany, 2015. Dagstuhl.","DOI":"10.1016\/B978-0-12-404578-1.00015-2"}],"container-title":["Journal of the Brazilian Computer Society"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s13173-017-0065-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13173-017-0065-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13173-017-0065-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,29]],"date-time":"2025-06-29T13:42:53Z","timestamp":1751204573000},"score":1,"resource":{"primary":{"URL":"https:\/\/journal-bcs.springeropen.com\/articles\/10.1186\/s13173-017-0065-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,8]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["65"],"URL":"https:\/\/doi.org\/10.1186\/s13173-017-0065-8","relation":{},"ISSN":["0104-6500","1678-4804"],"issn-type":[{"type":"print","value":"0104-6500"},{"type":"electronic","value":"1678-4804"}],"subject":[],"published":{"date-parts":[[2018,1,8]]},"article-number":"1"}}