{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T19:00:17Z","timestamp":1774292417918,"version":"3.50.1"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2013,3,1]],"date-time":"2013-03-01T00:00:00Z","timestamp":1362096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100012950","name":"INRIA","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100012950","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Research Chair in Distributed Computing of the Universit\u00e9 du Qu\u00e9bec en Outaouais"},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2013,3]]},"abstract":"<jats:p>The aim of rendezvous in a graph is meeting of two mobile agents at some node of an unknown anonymous connected graph. In this article, we focus on rendezvous in trees, and, analogously to the efforts that have been made for solving the exploration problem with compact automata, we study the size of memory of mobile agents that permits to solve the rendezvous problem deterministically. We assume that the agents are identical, and move in synchronous rounds.<\/jats:p>\n          <jats:p>\n            We first show that if the delay between the starting times of the agents is\n            <jats:italic>arbitrary<\/jats:italic>\n            , then the lower bound on memory required for rendezvous is\n            <jats:italic>\u03a9<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) bits, even for the line of length\n            <jats:italic>n<\/jats:italic>\n            . This lower bound meets a previously known upper bound of\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) bits for rendezvous in arbitrary graphs of size at most\n            <jats:italic>n<\/jats:italic>\n            . Our main result is a proof that the amount of memory needed for rendezvous\n            <jats:italic>with simultaneous start<\/jats:italic>\n            depends essentially on the number \u2113 of leaves of the tree, and is exponentially less impacted by the number\n            <jats:italic>n<\/jats:italic>\n            of nodes. Indeed, we present two identical agents with\n            <jats:italic>O<\/jats:italic>\n            (log \u2113 + log log\n            <jats:italic>n<\/jats:italic>\n            ) bits of memory that solve the rendezvous problem in all trees with at most\n            <jats:italic>n<\/jats:italic>\n            nodes and at most \u2113 leaves. Hence, for the class of trees with polylogarithmically many leaves, there is an exponential gap in minimum memory size needed for rendezvous between the scenario with arbitrary delay and the scenario with delay zero. Moreover, we show that our upper bound is optimal by proving that\n            <jats:italic>\u03a9<\/jats:italic>\n            (log \u2113 + log log\n            <jats:italic>n<\/jats:italic>\n            ) bits of memory are required for rendezvous, even in the class of trees with degrees bounded by 3.\n          <\/jats:p>","DOI":"10.1145\/2438645.2438649","type":"journal-article","created":{"date-parts":[[2013,3,19]],"date-time":"2013-03-19T13:34:23Z","timestamp":1363700063000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":38,"title":["Delays Induce an Exponential Memory Gap for Rendezvous in Trees"],"prefix":"10.1145","volume":"9","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[{"name":"CNRS and Universit\u00e9 Paris Diderot"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[{"name":"Universit\u00e9 du Qu\u00e9bec en Outaouais"}]}],"member":"320","published-online":{"date-parts":[[2013,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1239\/jap\/1032374243"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012993249195"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.10011"},{"key":"e_1_2_1_4_1","unstructured":"Alpern S. and Gal S. 2002. The theory of search games and rendezvous. In International Series in Operations Research and Management Science Kluwer Academic Publishers.  Alpern S. and Gal S. 2002. The theory of search games and rendezvous. In International Series in Operations Research and Management Science Kluwer Academic Publishers."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/276884.276925"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.49.1.107.11191"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.2307\/3214827"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13284-1_8"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012996314130"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.1044"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP\u201903)","author":"Cieliebak M.","unstructured":"Cieliebak , M. , Flocchini , P. , Prencipe , G. , and Santoro , N . 2003. Solving the robots gathering problem . In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP\u201903) . 1181--1196. Cieliebak, M., Flocchini, P., Prencipe, G., and Santoro, N. 2003. Solving the robots gathering problem. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP\u201903). 1181--1196."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209048"},{"key":"e_1_2_1_13_1","unstructured":"Cormen T. H. Leiserson C. E. and Rivest R. L. 1990. Introduction to Algorithms. McGraw-Hill.   Cormen T. H. Leiserson C. E. and Rivest R. L. 1990. Introduction to Algorithms . McGraw-Hill."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835801"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910)","author":"Czyzowicz J.","unstructured":"Czyzowicz , J. , Labourel , A. , and Pelc , A . 2010b. How to meet asynchronously (almost) everywhere . In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910) . 22--30. Czyzowicz, J., Labourel, A., and Pelc, A. 2010b. How to meet asynchronously (almost) everywhere. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910). 22--30."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312007"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.12.016"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118736.3118835"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.10.002"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00395-4"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201901)","author":"Flocchini P.","unstructured":"Flocchini , P. , Prencipe , G. , Santoro , N. , and Widmayer , P . 2010. Gathering of asynchronous oblivious robots with limited visibility . In Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201901) . Lecture Notes in Computer Science, Springer, 247--258. Flocchini, P., Prencipe, G., Santoro, N., and Widmayer, P. 2010. Gathering of asynchronous oblivious robots with limited visibility. In Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201901). Lecture Notes in Computer Science, Springer, 247--258."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/646254.684110"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/646516.696161"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24749-4_22"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_17"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810524"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.47.6.974"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907)","author":"Gasieniec L.","unstructured":"Gasieniec , L. , Pelc , A. , Radzik , T. , and Zhang , X . 2007. Tree exploration with logarithmic memory . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907) . 585--594. Gasieniec, L., Pelc, A., Radzik, T., and Zhang, X. 2007. Tree exploration with logarithmic memory. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907). 585--594."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/93385.93409"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 16th IEEE Conference on Computational Complexity. 21--26","author":"Kouck\u2018 Y, M","year":"2001","unstructured":"Kouck\u2018 Y, M . 2001 . Universal traversal sequences with backtracking . In Proceedings of the 16th IEEE Conference on Computational Complexity. 21--26 . Kouck\u2018Y, M. 2001. Universal traversal sequences with backtracking. In Proceedings of the 16th IEEE Conference on Computational Complexity. 21--26."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/11780823_5"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/1792918.1792970"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 23rd International Conference on Distributed Computing Systems (ICDCS\u201903)","author":"Kranakis E.","unstructured":"Kranakis , E. , Krizanc , D. , Santoro , N. and Sawchuk , C . 2003. Mobile agent rendezvous in a ring . In Proceedings of the 23rd International Conference on Distributed Computing Systems (ICDCS\u201903) . IEEE, 592--599. Kranakis, E., Krizanc, D., Santoro, N. and Sawchuk, C. 2003. Mobile agent rendezvous in a ring. In Proceedings of the 23rd International Conference on Distributed Computing Systems (ICDCS\u201903). IEEE, 592--599."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/235049.235058"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"key":"e_1_2_1_36_1","volume-title":"The Strategy of Conflict","author":"Schelling T.","unstructured":"Schelling , T. 1960. The Strategy of Conflict . Oxford University Press , Oxford, UK . Schelling, T. 1960. The Strategy of Conflict. Oxford University Press, Oxford, UK."},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907)","author":"Ta-Shma A.","unstructured":"Ta-Shma , A. and Zwick , U . 2007. Deterministic rendezvous, treasure hunts and strongly universal exploration sequences . In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907) . 599--608. Ta-Shma, A. and Zwick, U. 2007. Deterministic rendezvous, treasure hunts and strongly universal exploration sequences. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907). 599--608."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1992.89"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/646250.685518"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2438645.2438649","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2438645.2438649","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:35:29Z","timestamp":1750235729000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2438645.2438649"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["10.1145\/2438645.2438649"],"URL":"https:\/\/doi.org\/10.1145\/2438645.2438649","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3]]},"assertion":[{"value":"2011-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}