{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T19:01:03Z","timestamp":1774292463101,"version":"3.50.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,1,21]],"date-time":"2022-01-21T00:00:00Z","timestamp":1642723200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,21]],"date-time":"2022-01-21T00:00:00Z","timestamp":1642723200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"agence nationale de la recherche","award":["Project ESTATE, ANR-16-CE25-0009-03"],"award-info":[{"award-number":["Project ESTATE, ANR-16-CE25-0009-03"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2022,6]]},"DOI":"10.1007\/s00446-022-00419-9","type":"journal-article","created":{"date-parts":[[2022,1,21]],"date-time":"2022-01-21T09:04:06Z","timestamp":1642755846000},"page":"235-263","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Byzantine gathering in polynomial time"],"prefix":"10.1007","volume":"35","author":[{"given":"S\u00e9bastien","family":"Bouchard","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9593-7802","authenticated-orcid":false,"given":"Yoann","family":"Dieudonn\u00e9","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anissa","family":"Lamani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,1,21]]},"reference":[{"key":"419_CR1","unstructured":"Abiteboul, S., Kaplan, H., Milo, T.: Compact labeling schemes for ancestor queries. In: Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7\u20139, 2001, Washington, DC, USA, pp. 547\u2013556 (2001)"},{"issue":"1","key":"419_CR2","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1137\/050645221","volume":"36","author":"N Agmon","year":"2006","unstructured":"Agmon, N., Peleg, D.: Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM J. Comput. 36(1), 56\u201382 (2006)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"419_CR3","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1287\/opre.50.5.772.363","volume":"50","author":"S Alpern","year":"2002","unstructured":"Alpern, S.: Rendezvous search: a personal perspective. Oper. Res. 50(5), 772\u2013795 (2002)","journal-title":"Oper. Res."},{"key":"419_CR4","volume-title":"The Theory of Search Games and Rendezvous. International Series in Operations Research and Management Science","author":"S Alpern","year":"2003","unstructured":"Alpern, S.: The Theory of Search Games and Rendezvous. International Series in Operations Research and Management Science. Kluwer, Amsterdam (2003)"},{"key":"419_CR5","doi-asserted-by":"crossref","unstructured":"Bampas, E., Czyzowicz, J., Gasieniec, L., Ilcinkas, D., Labourel, A.: Almost optimal asynchronous rendezvous in infinite multidimensional grids. In: Proceedings of Distributed Computing, 24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13\u201315, 2010, pp. 297\u2013311 (2010)","DOI":"10.1007\/978-3-642-15763-9_28"},{"issue":"2","key":"419_CR6","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1145\/152610.152612","volume":"25","author":"M Barborak","year":"1993","unstructured":"Barborak, M., Malek, M.: The consensus problem in fault-tolerant computing. ACM Comput. Surv. 25(2), 171\u2013220 (1993)","journal-title":"ACM Comput. Surv."},{"issue":"6","key":"419_CR7","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/s00446-016-0276-9","volume":"29","author":"S Bouchard","year":"2016","unstructured":"Bouchard, S., Dieudonn\u00e9, Y., Ducourthial, B.: Byzantine gathering in networks. Distrib. Comput. 29(6), 435\u2013457 (2016)","journal-title":"Distrib. Comput."},{"key":"419_CR8","unstructured":"Bouchard, S., Dieudonn\u00e9, Y., Lamani, A.: Byzantine gathering in polynomial time. In:\u00a0Chatzigiannakis, I.,\u00a0Kaklamanis, C.,\u00a0Marx, D.,\u00a0Sannella, D. (eds.) 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9\u201313, 2018, Prague, Czech Republic, LIPIcs, vol. 107, pp. 147:1\u2013147:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"issue":"4","key":"419_CR9","doi-asserted-by":"publisher","first-page":"829","DOI":"10.1137\/100796534","volume":"41","author":"M Cieliebak","year":"2012","unstructured":"Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Distributed computing by mobile robots: gathering. SIAM J. Comput. 41(4), 829\u2013879 (2012)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"419_CR10","doi-asserted-by":"publisher","first-page":"42:1","DOI":"10.1145\/1383369.1383373","volume":"4","author":"R Cohen","year":"2008","unstructured":"Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-guided graph exploration by a finite automaton. ACM Trans. Algorithms 4(4), 42:1-42:18 (2008)","journal-title":"ACM Trans. Algorithms"},{"key":"419_CR11","doi-asserted-by":"crossref","unstructured":"Collins, A., Czyzowicz, J., Gasieniec, L., Labourel, A.: Tell me where I am so I can meet you sooner. In: Proceedings of Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6\u201310, 2010, Part II, pp. 502\u2013514 (2010)","DOI":"10.1007\/978-3-642-14162-1_42"},{"key":"419_CR12","unstructured":"Czyzowicz, J., Georgiou, K., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., Shende, S.M.: Search on a line by byzantine robots. In: 27th International Symposium on Algorithms and Computation, ISAAC 2016, December 12\u201314, 2016, Sydney, Australia, pp. 27:1\u201327:12 (2016)"},{"issue":"2","key":"419_CR13","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s00446-011-0141-9","volume":"25","author":"J Czyzowicz","year":"2012","unstructured":"Czyzowicz, J., Kosowski, A., Pelc, A.: How to meet when you forget: log-space rendezvous in arbitrary graphs. Distrib. Comput. 25(2), 165\u2013178 (2012)","journal-title":"Distrib. Comput."},{"issue":"4","key":"419_CR14","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1145\/2344422.2344427","volume":"8","author":"J Czyzowicz","year":"2012","unstructured":"Czyzowicz, J., Pelc, A., Labourel, A.: How to meet asynchronously (almost) everywhere. ACM Trans. Algorithms 8(4), 37 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"419_CR15","doi-asserted-by":"crossref","unstructured":"Das, S., Dereniowski, D., Kosowski, A., Uznanski, P.: Rendezvous of distance-aware mobile agents in unknown graphs. In: Proceedings of Structural Information and Communication Complexity\u201421st International Colloquium, SIROCCO 2014, Takayama, Japan, July 23\u201325, 2014, pp. 295\u2013310 (2014)","DOI":"10.1007\/978-3-319-09620-9_23"},{"key":"419_CR16","doi-asserted-by":"crossref","unstructured":"D\u00e9fago, X., Gradinariu, M., Messika, S., Parv\u00e9dy, P.R.: Fault-tolerant and self-stabilizing mobile robots gathering. In: Proceedings of Distributed Computing, 20th International Symposium, DISC 2006, Stockholm, Sweden, September 18\u201320, 2006, pp. 46\u201360 (2006)","DOI":"10.1007\/11864219_4"},{"issue":"1","key":"419_CR17","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s00453-006-0074-2","volume":"46","author":"A Dessmark","year":"2006","unstructured":"Dessmark, A., Fraigniaud, P., Kowalski, D.R., Pelc, A.: Deterministic rendezvous in graphs. Algorithmica 46(1), 69\u201396 (2006)","journal-title":"Algorithmica"},{"issue":"1","key":"419_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2629656","volume":"11","author":"Y Dieudonn\u00e9","year":"2014","unstructured":"Dieudonn\u00e9, Y., Pelc, A., Peleg, D.: Gathering despite mischief. ACM Trans. Algorithms 11(1), 1 (2014)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"419_CR19","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1137\/130931990","volume":"44","author":"Y Dieudonn\u00e9","year":"2015","unstructured":"Dieudonn\u00e9, Y., Pelc, A., Villain, V.: How to meet asynchronously at polynomial cost. SIAM J. Comput. 44(3), 844\u2013867 (2015)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"419_CR20","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/s00446-008-0076-y","volume":"21","author":"P Fraigniaud","year":"2009","unstructured":"Fraigniaud, P., Gavoille, C., Ilcinkas, D., Pelc, A.: Distributed computing with advice: information sensitivity of graph coloring. Distrib. Comput. 21(6), 395\u2013403 (2009)","journal-title":"Distrib. Comput."},{"issue":"11","key":"419_CR21","doi-asserted-by":"publisher","first-page":"1276","DOI":"10.1016\/j.ic.2008.07.005","volume":"206","author":"P Fraigniaud","year":"2008","unstructured":"Fraigniaud, P., Ilcinkas, D., Pelc, A.: Tree exploration with advice. Inf. Comput. 206(11), 1276\u20131287 (2008)","journal-title":"Inf. Comput."},{"key":"419_CR22","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Pelc, A.: Deterministic rendezvous in trees with little memory. In: Proceedings of Distributed Computing, 22nd International Symposium, DISC 2008, Arcachon, France, September 22\u201324, 2008, pp. 242\u2013256 (2008)","DOI":"10.1007\/978-3-540-87779-0_17"},{"issue":"2","key":"419_CR23","doi-asserted-by":"publisher","first-page":"17:1","DOI":"10.1145\/2438645.2438649","volume":"9","author":"P Fraigniaud","year":"2013","unstructured":"Fraigniaud, P., Pelc, A.: Delays induce an exponential memory gap for rendezvous in trees. ACM Trans. Algorithms 9(2), 17:1-17:24 (2013)","journal-title":"ACM Trans. Algorithms"},{"key":"419_CR24","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.tcs.2012.07.004","volume":"509","author":"S Guilbault","year":"2013","unstructured":"Guilbault, S., Pelc, A.: Gathering asynchronous oblivious agents with local vision in regular bipartite graphs. Theor. Comput. Sci. 509, 86\u201396 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"419_CR25","doi-asserted-by":"crossref","unstructured":"Hirose, J., Nakamura, J., Ooshita, F., Inoue, M.: Gathering with a strong team in weakly byzantine environments. In: ICDCN\u201921: International Conference on Distributed Computing and Networking, Virtual Event, Nara, Japan, January 5\u20138, 2021. ACM, pp. 26\u201335 (2021)","DOI":"10.1145\/3427796.3427799"},{"issue":"1","key":"419_CR26","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1137\/100797916","volume":"41","author":"T Izumi","year":"2012","unstructured":"Izumi, T., Souissi, S., Katayama, Y., Inuzuka, N., D\u00e9fago, X., Wada, K., Yamashita, M.: The gathering problem for two oblivious robots with unreliable compasses. SIAM J. Comput. 41(1), 26\u201346 (2012)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"419_CR27","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1137\/S0097539703433912","volume":"34","author":"M Katz","year":"2004","unstructured":"Katz, M., Katz, N.A., Korman, A., Peleg, D.: Labeling schemes for flow and connectivity. SIAM J. Comput. 34(1), 23\u201340 (2004)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"419_CR28","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/j.tcs.2008.02.010","volume":"399","author":"DR Kowalski","year":"2008","unstructured":"Kowalski, D.R., Malinowski, A.: How to meet in anonymous network. Theor. Comput. Sci. 399(1\u20132), 141\u2013156 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"419_CR29","doi-asserted-by":"crossref","unstructured":"Kranakis, E., Krizanc, D., Markou, E., Pagourtzis, A., Ram\u00edrez, F.: Different speeds suffice for rendezvous of two agents on arbitrary graphs. In: Proceedings of SOFSEM 2017: Theory and Practice of Computer Science\u201443rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, January 16\u201320, 2017, pp. 79\u201390 (2017)","DOI":"10.1007\/978-3-319-51963-0_7"},{"key":"419_CR30","doi-asserted-by":"crossref","unstructured":"Kranakis, E., Krizanc, D., Rajsbaum, S.: Mobile agent rendezvous: A survey. In: Proceedings of Structural Information and Communication Complexity, 13th International Colloquium, SIROCCO 2006, Chester, UK, July 2-5, 2006, pp. 1\u20139 (2006)","DOI":"10.1007\/11780823_1"},{"key":"419_CR31","volume-title":"Distributed Algorithms","author":"NA Lynch","year":"1996","unstructured":"Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann, Burlington (1996)"},{"issue":"3","key":"419_CR32","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.tcs.2005.12.016","volume":"355","author":"GD Marco","year":"2006","unstructured":"Marco, G.D., Gargano, L., Kranakis, E., Krizanc, D., Pelc, A., Vaccaro, U.: Asynchronous deterministic rendezvous in graphs. Theor. Comput. Sci. 355(3), 315\u2013326 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"419_CR33","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/j.tcs.2015.09.025","volume":"608","author":"A Miller","year":"2015","unstructured":"Miller, A., Pelc, A.: Fast rendezvous with advice. Theor. Comput. Sci. 608, 190\u2013198 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"419_CR34","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s00446-015-0253-8","volume":"29","author":"A Miller","year":"2016","unstructured":"Miller, A., Pelc, A.: Time versus cost tradeoffs for deterministic rendezvous in networks. Distrib. Comput. 29(1), 51\u201364 (2016)","journal-title":"Distrib. Comput."},{"key":"419_CR35","doi-asserted-by":"crossref","unstructured":"Miller, A., Saha, U.: Fast byzantine gathering with visibility in graphs. In: Pinotti, C.M.,\u00a0Navarra, A.,\u00a0Bagchi, A. (eds.) Algorithms for Sensor Systems\u201416th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2020, Pisa, Italy, September 9-10, 2020, Revised Selected Papers, Lecture Notes in Computer Science, vol. 12503. Springer, pp. 140\u2013153 (2020)","DOI":"10.1007\/978-3-030-62401-9_10"},{"issue":"14","key":"419_CR36","doi-asserted-by":"publisher","first-page":"1307","DOI":"10.1016\/j.tcs.2008.08.020","volume":"410","author":"N Nisse","year":"2009","unstructured":"Nisse, N., Soguet, D.: Graph searching with advice. Theor. Comput. Sci. 410(14), 1307\u20131318 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"419_CR37","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1145\/322186.322188","volume":"27","author":"MC Pease","year":"1980","unstructured":"Pease, M.C., Shostak, R.E., Lamport, L.: Reaching agreement in the presence of faults. J. ACM 27(2), 228\u2013234 (1980)","journal-title":"J. ACM"},{"issue":"2","key":"419_CR38","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1002\/net.21810","volume":"72","author":"A Pelc","year":"2018","unstructured":"Pelc, A.: Deterministic gathering with crash faults. Networks 72(2), 182\u2013199 (2018)","journal-title":"Networks"},{"issue":"4","key":"419_CR39","doi-asserted-by":"publisher","first-page":"17:1","DOI":"10.1145\/1391289.1391291","volume":"55","author":"O Reingold","year":"2008","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4), 17:1-17:24 (2008)","journal-title":"J. ACM"},{"key":"419_CR40","volume-title":"The Strategy of Conflict","author":"T Schelling","year":"1960","unstructured":"Schelling, T.: The Strategy of Conflict. Oxford University Press, Oxford (1960)"},{"issue":"3","key":"419_CR41","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/2601068","volume":"10","author":"A Ta-Shma","year":"2014","unstructured":"Ta-Shma, A., Zwick, U.: Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences. ACM Trans. Algorithms 10(3), 12 (2014)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"419_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM 52(1), 1\u201324 (2005)","journal-title":"J. ACM"},{"issue":"3","key":"419_CR43","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1587\/transinf.2017FCP0008","volume":"101\u2013D","author":"M Tsuchida","year":"2018","unstructured":"Tsuchida, M., Ooshita, F., Inoue, M.: Byzantine-tolerant gathering of mobile agents in arbitrary networks with authenticated whiteboards. IEICE Trans. 101\u2013D(3), 602\u2013610 (2018)","journal-title":"IEICE Trans."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-022-00419-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-022-00419-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-022-00419-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,18]],"date-time":"2022-05-18T06:09:09Z","timestamp":1652854149000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-022-00419-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,21]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["419"],"URL":"https:\/\/doi.org\/10.1007\/s00446-022-00419-9","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,21]]},"assertion":[{"value":"25 March 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}