{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T20:54:53Z","timestamp":1762808093883,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2011,7,1]],"date-time":"2011-07-01T00:00:00Z","timestamp":1309478400000},"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":[[2011,7]]},"abstract":"<jats:p>\n            We present a trade-off between the expected time for two identical agents to rendezvous on a synchronous, anonymous, oriented ring and the memory requirements of the agents. In particular, we show there exists a 2\n            <jats:italic>t<\/jats:italic>\n            state agent which can achieve rendezvous on an\n            <jats:italic>n<\/jats:italic>\n            -node ring in expected time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            \/2\n            <jats:sup>\n              <jats:italic>t<\/jats:italic>\n            <\/jats:sup>\n            + 2\n            <jats:sup>\n              <jats:italic>t<\/jats:italic>\n            <\/jats:sup>\n            ) and that any\n            <jats:italic>t<\/jats:italic>\n            \/2 state agent requires expected time \u03a9(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            \/2\n            <jats:sup>\n              <jats:italic>t<\/jats:italic>\n            <\/jats:sup>\n            ). As a corollary we observe that \u0398(log log\n            <jats:italic>n<\/jats:italic>\n            ) bits of memory are necessary and sufficient to achieve rendezvous in linear time.\n          <\/jats:p>","DOI":"10.1145\/1978782.1978789","type":"journal-article","created":{"date-parts":[[2011,7,21]],"date-time":"2011-07-21T13:27:09Z","timestamp":1311254829000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Randomized rendezvous with limited memory"],"prefix":"10.1145","volume":"7","author":[{"given":"Evangelos","family":"Kranakis","sequence":"first","affiliation":[{"name":"Carleton University, Ottawa, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Krizanc","sequence":"additional","affiliation":[{"name":"Wesleyan University, Middletown, CT"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[{"name":"Carleton University, Ottawa, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,7,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012993249195"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1239\/jap\/1032374243"},{"key":"e_1_2_1_3_1","unstructured":"Alpern S. and Gal S. 2003. The Theory of Search Games and Rendezvous. Kluwer Academic Publishers Norwell MA.  Alpern S. and Gal S. 2003. The Theory of Search Games and Rendezvous. Kluwer Academic Publishers Norwell MA."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0406029"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92221-6_29"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Dessmark A. Fraigniaud P. and \n      Pelc A\n  . \n  2003\n  . Deterministic rendezvous in graphs. In Proceedings of the 11th European Symposium on Algorithms (ESA'03). G. D. Battista and U. Zwick Eds. Lecture Notes in Computer Science vol. \n  2832 Springer 184--195.  Dessmark A. Fraigniaud P. and Pelc A. 2003. Deterministic rendezvous in graphs. In Proceedings of the 11th European Symposium on Algorithms (ESA'03). G. D. Battista and U. Zwick Eds. Lecture Notes in Computer Science vol. 2832 Springer 184--195.","DOI":"10.1007\/978-3-540-39658-1_19"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Dobrev S. Flocchini P. Prencipe G. and \n      Santoro N\n  . \n  2004\n  . Multiple agents rendezvous in a ring in spite of a black hole. In Proceedings of the 8th International Conference on Principles of Distributed Systems (OPODIS'04). T. Higashino Ed. Lecture Notes in Computer Science vol. \n  3144 Springer 34--46.  Dobrev S. Flocchini P. Prencipe G. and Santoro N. 2004. Multiple agents rendezvous in a ring in spite of a black hole. In Proceedings of the 8th International Conference on Principles of Distributed Systems (OPODIS'04). T. Higashino Ed. Lecture Notes in Computer Science vol. 3144 Springer 34--46.","DOI":"10.1007\/978-3-540-27860-3_6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Flocchini P. Kranakis E. Krizanc D. Luccio F. Santoro N. and \n      Sawchuk C\n  . \n  2004\n  a. Mobile agent rendezvous when tokens fail. In Proceedings of the 11th Colloquium on Structural Information and Communication Complexity (SIROCCO'04). R. Kr\u00e1lovi\u010d and O. S\u00fdkora Eds. Lecture Notes in Computer Science vol. \n  3104 Springer 161--172.  Flocchini P. Kranakis E. Krizanc D. Luccio F. Santoro N. and Sawchuk C. 2004a. Mobile agent rendezvous when tokens fail. In Proceedings of the 11th Colloquium on Structural Information and Communication Complexity (SIROCCO'04). R. Kr\u00e1lovi\u010d and O. S\u00fdkora Eds. Lecture Notes in Computer Science vol. 3104 Springer 161--172.","DOI":"10.1007\/978-3-540-27796-5_15"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Flocchini P. Kranakis E. Krizanc D. Santoro N. and \n      Sawchuk C\n  . \n  2004\n  b. Multiple mobile agent rendezvous in the ring. In Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN'04). M. Farach-Colton Ed. Lecture Notes in Computer Science vol. \n  2976 Springer 599--608.  Flocchini P. Kranakis E. Krizanc D. Santoro N. and Sawchuk C. 2004b. Multiple mobile agent rendezvous in the ring. In Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN'04). M. Farach-Colton Ed. Lecture Notes in Computer Science vol. 2976 Springer 599--608.","DOI":"10.1007\/978-3-540-24698-5_62"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/11611257_26"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11780823_5"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30551-4_56"},{"key":"e_1_2_1_13_1","unstructured":"Kranakis E.\n     and \n      Krizanc D\n  . \n  2007\n  . An algorithmic theory of mobile agents. In Proceedings of the 2nd Symposium on Trustworthy Global Computing. R. Bruni and U. Montanari Eds. Lecture Notes in Computer Science vol. \n  4661 Springer 89--97.   Kranakis E. and Krizanc D. 2007. An algorithmic theory of mobile agents. In Proceedings of the 2nd Symposium on Trustworthy Global Computing. R. Bruni and U. Montanari Eds. Lecture Notes in Computer Science vol. 4661 Springer 89--97."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11682462_60"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Kranakis E. Krizanc D. and \n      Morin P\n  . \n  2008\n  . Randomized rendezvous with limited memory. In Proceedings of the 8th Latin American Theoretical Informatics Symposium (LATIN'08). E. S. Laber C. Bornstein L. T. Nogueira and L. Faria Eds. Lecture Notes in Computer Science vol. \n  4957 Springer 605--616.   Kranakis E. Krizanc D. and Morin P. 2008. Randomized rendezvous with limited memory. In Proceedings of the 8th Latin American Theoretical Informatics Symposium (LATIN'08). E. S. Laber C. Bornstein L. T. Nogueira and L. Faria Eds. Lecture Notes in Computer Science vol. 4957 Springer 605--616.","DOI":"10.1007\/978-3-540-78773-0_52"},{"volume-title":"Proceedings of the International Conference on Distributed Computing Systems (ICDCS'03)","author":"Kranakis E.","key":"e_1_2_1_16_1","unstructured":"Kranakis , E. , Krizanc , D. , Santoro , N. , and Sawchuk , C . 2003. Mobile agent rendezvous search problem in the ring . In Proceedings of the International Conference on Distributed Computing Systems (ICDCS'03) . IEEE Computer Society, 592--599. Kranakis, E., Krizanc, D., Santoro, N., and Sawchuk, C. 2003. Mobile agent rendezvous search problem in the ring. In Proceedings of the International Conference on Distributed Computing Systems (ICDCS'03). IEEE Computer Society, 592--599."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11549345_24"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.12.016"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Mitzenmacher M. and Upfal E. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press New York.   Mitzenmacher M. and Upfal E. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press New York.","DOI":"10.1017\/CBO9780511813603"},{"volume-title":"Probability Models for Computer Science","author":"Ross S. M.","key":"e_1_2_1_20_1","unstructured":"Ross , S. M. 2002. Probability Models for Computer Science . Harcourt Academic Press , Berkeley, CA . Ross, S. M. 2002. Probability Models for Computer Science. Harcourt Academic Press, Berkeley, CA."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011219024159"},{"volume-title":"Design and Analysis of Distributed Algorithms","author":"Santoro N.","key":"e_1_2_1_22_1","unstructured":"Santoro , N. 2006. Design and Analysis of Distributed Algorithms . Wiley , Hoboken, NJ . Santoro, N. 2006. Design and Analysis of Distributed Algorithms. Wiley, Hoboken, NJ."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979628292X"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Yu X.\n     and \n      Yung M\n  . \n  1996\n  . Agent rendezvous: A dynamic symmetry-breaking problem. In Proceedings of the 23rd International Colloquium on Automata Languages and Programming (ICALP'96). F. M. auf der Heide and B. Monien Eds. Lecture Notes in Computer Science vol. \n  1099 Springer 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). F. M. auf der Heide and B. Monien Eds. Lecture Notes in Computer Science vol. 1099 Springer 610--621.","DOI":"10.1007\/3-540-61440-0_163"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1978782.1978789","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1978782.1978789","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:37Z","timestamp":1750244377000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1978782.1978789"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["10.1145\/1978782.1978789"],"URL":"https:\/\/doi.org\/10.1145\/1978782.1978789","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2011,7]]},"assertion":[{"value":"2008-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-07-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}