{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:23Z","timestamp":1781077703697,"version":"3.54.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,9,1]],"date-time":"2012-09-01T00:00:00Z","timestamp":1346457600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2012,9]]},"abstract":"<jats:p>\n            Two mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly infinite, unknown connected graph or in an unknown connected terrain in the plane. Agents are modeled as points, and the route of each of them only depends on its label and on the unknown environment. The actual walk of each agent also depends on an asynchronous adversary that may arbitrarily vary the speed of the agent, stop it, or even move it back and forth, as long as the walk of the agent is continuous, does not leave its route and covers all of it. Meeting in a graph means that both agents must be at the same time in some node or in some point inside an edge of the graph, while meeting in a terrain means that both agents must be at the same time in some point of the terrain. Does there exist a deterministic algorithm that allows any two agents to meet in any unknown environment in spite of this very powerful adversary? We give deterministic rendezvous algorithms for agents starting at arbitrary nodes of any anonymous connected graph (finite or infinite) and for agents starting at any interior points with rational coordinates in any closed region of the plane with path-connected interior. In the geometric scenario agents may have different compasses and different units of length. While our algorithms work in a very general setting -- agents can, indeed, meet almost everywhere -- we show that none of these few limitations imposed on the environment can be removed. On the other hand, our algorithm also guarantees the following\n            <jats:italic>approximate rendezvous<\/jats:italic>\n            for agents starting at\n            <jats:italic>arbitrary<\/jats:italic>\n            interior points of a terrain as previously stated agents will eventually get to within an arbitrarily small positive distance from each other.\n          <\/jats:p>","DOI":"10.1145\/2344422.2344427","type":"journal-article","created":{"date-parts":[[2012,10,2]],"date-time":"2012-10-02T13:50:00Z","timestamp":1349185800000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":68,"title":["How to meet asynchronously (almost) everywhere"],"prefix":"10.1145","volume":"8","author":[{"given":"Jurek","family":"Czyzowicz","sequence":"first","affiliation":[{"name":"Universit\u00e9 du Qu\u00e9bec en Outaouais"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[{"name":"Universit\u00e9 du Qu\u00e9bec en Outaouais"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arnaud","family":"Labourel","sequence":"additional","affiliation":[{"name":"Aix Marseille Universit\u00e9 &amp; Outaouais CNRS"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,10,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.34"},{"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","doi-asserted-by":"publisher","DOI":"10.1239\/jap\/1032374243"},{"key":"e_1_2_1_5_1","unstructured":"Alpern S. and Gal S. 2002. The Theory of Search Games and Rendezvous. Int. Series in Operations research and Management Science Series vol. 55. Kluwer Academic Publishers Boston Mass.  Alpern S. and Gal S. 2002. The Theory of Search Games and Rendezvous. Int. Series in Operations research and Management Science Series vol. 55. Kluwer Academic Publishers Boston Mass."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.2307\/3214827"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/276884.276925"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.49.1.107.11191"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 24th International Conference on Distributed Computing (DISC'10)","author":"Bampas E.","unstructured":"Bampas , E. , Czyzowicz , J. , Gasieniec , L. , Ilcinkas , D. , and Labourel , A . 2010. Almost optimal asynchronous rendezvous in infinite multidimensional grids . In Proceedings of the 24th International Conference on Distributed Computing (DISC'10) . Springer-Verlag, Berlin, Heidelberg, 297--311. Bampas, E., Czyzowicz, J., Gasieniec, L., Ilcinkas, D., and Labourel, A. 2010. Almost optimal asynchronous rendezvous in infinite multidimensional grids. In Proceedings of the 24th International Conference on Distributed Computing (DISC'10). Springer-Verlag, Berlin, Heidelberg, 297--311."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012996314130"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.1044"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 30th International Conference on Automata, Languages and Programming (ICALP'03)","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 Conference on Automata, Languages and Programming (ICALP'03) . Springer-Verlag, Berlin, Heidelberg, 1181--1196. Cieliebak, M., Flocchini, P., Prencipe, G., and Santoro, N. 2003. Solving the robots gathering problem. In Proceedings of the 30th International Conference on Automata, Languages and Programming (ICALP'03). Springer-Verlag, Berlin, Heidelberg, 1181--1196."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 37th International Colloquium Conference on Automata, Languages and Programming: Part II. (ICALP'10)","author":"Collins A.","unstructured":"Collins , A. , Czyzowicz , J. , Gasieniec , L. , and Labourel , A . 2010. Tell me where I am so I can meet you sooner: Asynchronous rendezvous with location information . In Proceedings of the 37th International Colloquium Conference on Automata, Languages and Programming: Part II. (ICALP'10) . Springer-Verlag, Berlin, Heidelberg, 502--514. Collins, A., Czyzowicz, J., Gasieniec, L., and Labourel, A. 2010. Tell me where I am so I can meet you sooner: Asynchronous rendezvous with location information. In Proceedings of the 37th International Colloquium Conference on Automata, Languages and Programming: Part II. (ICALP'10). Springer-Verlag, Berlin, Heidelberg, 502--514."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100266"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11549345_24"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-0074-2"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102783"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS'01)","author":"Flocchini P.","unstructured":"Flocchini , P. , Prencipe , G. , Santoro , N. , and Widmayer , P . 2001. Gathering of asynchronous oblivious robots with limited visibility . In Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS'01) . Springer-Verlag, London, UK, 247--258. Flocchini, P., Prencipe, G., Santoro, N., and Widmayer, P. 2001. Gathering of asynchronous oblivious robots with limited visibility. In Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS'01). Springer-Verlag, London, UK, 247--258."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.47.6.974"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/93385.93409"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.05.020"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.09.032"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.02.010"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the International Conference on Distributed Computing Systems, 592","author":"Kranakis E.","unstructured":"Kranakis , E. , Santoro , N. , Sawchuk , C. , and Krizanc , D . 2003. Mobile agent rendezvous in a ring . In Proceedings of the International Conference on Distributed Computing Systems, 592 . Kranakis, E., Santoro, N., Sawchuk, C., and Krizanc, D. 2003. Mobile agent rendezvous in a ring. In Proceedings of the International Conference on Distributed Computing Systems, 592."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S036301299427816X"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.04.023"},{"key":"e_1_2_1_27_1","volume-title":"The Strategy of Conflict","author":"Schelling T.","unstructured":"Schelling , T. 1960. The Strategy of Conflict . Oxford University Press , Oxford . Schelling, T. 1960. The Strategy of Conflict. Oxford University Press, Oxford."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-95891-8_45"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 18th annual ACM-SIAM symposium on Discrete algorithms (SODA'07)","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 annual ACM-SIAM symposium on Discrete algorithms (SODA'07) . Society for Industrial and Applied Mathematics, Philadelphia, PA, 599--608. Ta-Shma, A. and Zwick, U. 2007. Deterministic rendezvous, treasure hunts and strongly universal exploration sequences. In Proceedings of the 18th annual ACM-SIAM symposium on Discrete algorithms (SODA'07). Society for Industrial and Applied Mathematics, Philadelphia, PA, 599--608."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1992.89"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 23rd International Colloquium on Automata, Languages and Programming (ICALP'96)","author":"Yu X.","unstructured":"Yu , X. and Yung , M . 1996. Agent rendezvous: A dynamic symmetry-breaking problem . In Proceedings of the 23rd International Colloquium on Automata, Languages and Programming (ICALP'96) . Springer-Verlag, London, UK, 610--621. Yu, X. and Yung, M. 1996. Agent rendezvous: A dynamic symmetry-breaking problem. In Proceedings of the 23rd International Colloquium on Automata, Languages and Programming (ICALP'96). Springer-Verlag, London, UK, 610--621."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2344422.2344427","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2344422.2344427","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:07:39Z","timestamp":1750273659000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2344422.2344427"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,9]]}},"alternative-id":["10.1145\/2344422.2344427"],"URL":"https:\/\/doi.org\/10.1145\/2344422.2344427","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9]]},"assertion":[{"value":"2010-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-10-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}