{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:27Z","timestamp":1781077707256,"version":"3.54.1"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,3,4]],"date-time":"2015-03-04T00:00:00Z","timestamp":1425427200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,2]]},"DOI":"10.1007\/s00453-015-9982-0","type":"journal-article","created":{"date-parts":[[2015,3,3]],"date-time":"2015-03-03T16:11:38Z","timestamp":1425399098000},"page":"908-946","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":30,"title":["Anonymous Meeting in Networks"],"prefix":"10.1007","volume":"74","author":[{"given":"Yoann","family":"Dieudonn\u00e9","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,3,4]]},"reference":[{"issue":"1","key":"9982_CR1","doi-asserted-by":"crossref","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":"3","key":"9982_CR2","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1137\/S0363012993249195","volume":"33","author":"S Alpern","year":"1995","unstructured":"Alpern, S.: The rendezvous search problem. SIAM J. Control Optim. 33(3), 673\u2013683 (1995)","journal-title":"SIAM J. Control Optim."},{"key":"9982_CR3","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1002\/nav.10011","volume":"49","author":"S Alpern","year":"2002","unstructured":"Alpern, S.: Rendezvous search on labelled networks. Naval Res. Logist. 49, 256\u2013274 (2002)","journal-title":"Naval Res. Logist."},{"key":"9982_CR4","volume-title":"Theory of Search Games and Rendezvous","author":"S Alpern","year":"2003","unstructured":"Alpern, S., Gal, S.: Theory of Search Games and Rendezvous. Kluwer Academic, Dordrecht (2003)"},{"issue":"4","key":"9982_CR5","doi-asserted-by":"crossref","first-page":"839","DOI":"10.2307\/3214827","volume":"28","author":"E Anderson","year":"1990","unstructured":"Anderson, E., Weber, R.: The rendezvous problem on discrete locations. J. Appl. Probab. 28(4), 839\u2013851 (1990)","journal-title":"J. Appl. Probab."},{"key":"9982_CR6","doi-asserted-by":"crossref","unstructured":"Anderson, E., Fekete, S.: Asymmetric rendezvous on the plane. In: Proceedings of 14th Annual Symposium on Computational Geometry, June 7\u201310, Minneapolis, Minnesota, USA, pp. 365\u2013373 (1998)","DOI":"10.1145\/276884.276925"},{"issue":"1","key":"9982_CR7","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1287\/opre.49.1.107.11191","volume":"49","author":"E Anderson","year":"2001","unstructured":"Anderson, E., Fekete, S.: Two dimensional rendezvous search. Oper. Res. 49(1), 107\u2013118 (2001)","journal-title":"Oper. Res."},{"key":"9982_CR8","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processors (extended abstract). In: Proceedings of 12th Annual ACM Symposium on Theory of Computing, April 28\u201330, Los Angeles, California, USA, pp. 82\u201393 (1980)","DOI":"10.1145\/800141.804655"},{"issue":"2","key":"9982_CR9","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1016\/0196-6774(91)90002-G","volume":"12","author":"H Attiya","year":"1991","unstructured":"Attiya, H., Snir, M.: Better computing on the anonymous ring. J. Algorithms 12(2), 204\u2013238 (1991)","journal-title":"J. Algorithms"},{"key":"9982_CR10","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 24th International Symposium on Distributed Computing, DISC 2010, Cambridge, MA, USA, September 13\u201315, pp. 297\u2013311 (2010)","DOI":"10.1007\/978-3-642-15763-9_28"},{"issue":"8","key":"9982_CR11","doi-asserted-by":"crossref","first-page":"722","DOI":"10.1002\/nav.1044","volume":"48","author":"V Baston","year":"2001","unstructured":"Baston, V., Gal, S.: Rendezvous search when marks are left at the starting points. Naval Res. Logist. 48(8), 722\u2013731 (2001)","journal-title":"Naval Res. Logist."},{"key":"9982_CR12","doi-asserted-by":"crossref","unstructured":"Boldi, P., Vigna, S.: Computing anonymously with arbitrary knowledge. In: Proceedings of the Eighteenth Annual ACM Symposium on Principles of Distributed Computing, PODC, \u201999Atlanta, Georgia, USA, May 3\u20136, pp. 181\u2013188 (1999)","DOI":"10.1145\/301308.301355"},{"key":"9982_CR13","doi-asserted-by":"crossref","unstructured":"Chalopin, J., Das, S., Kosowski, A.: Constructing a map of an anonymous graph: applications of universal sequences. In: Proceedings 14th International Conference on Principles of Distributed Systems, OPODIS 2010, Tozeur, Tunisia, December 14\u201317, pp. 119\u2013134 (2010)","DOI":"10.1007\/978-3-642-17653-1_10"},{"issue":"4","key":"9982_CR14","doi-asserted-by":"crossref","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":"6","key":"9982_CR15","doi-asserted-by":"crossref","first-page":"1516","DOI":"10.1137\/S0097539704446475","volume":"34","author":"R Cohen","year":"2005","unstructured":"Cohen, R., Peleg, D.: Convergence properties of the gravitational algorithm in asynchronous robot systems. SIAM J. Comput. 34(6), 1516\u20131528 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9982_CR16","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1137\/060665257","volume":"38","author":"R Cohen","year":"2008","unstructured":"Cohen, R., Peleg, D.: Convergence of autonomous mobile robots with inaccurate sensors and movements. SIAM J. Comput. 38(1), 276\u2013302 (2008)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9982_CR17","doi-asserted-by":"crossref","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":"9982_CR18","doi-asserted-by":"crossref","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"},{"issue":"4","key":"9982_CR19","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/s00446-014-0212-9","volume":"27","author":"G D\u2019Angelo","year":"2014","unstructured":"D\u2019Angelo, G., Di Stefano, G., Navarra, A.: Gathering on rings under the look\u2013compute\u2013move model. Distrib. Comput. 27(4), 255\u2013285 (2014)","journal-title":"Distrib. Comput."},{"issue":"3","key":"9982_CR20","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.tcs.2005.12.016","volume":"355","author":"G Marco De","year":"2006","unstructured":"De Marco, G., 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."},{"issue":"1","key":"9982_CR21","doi-asserted-by":"crossref","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"},{"key":"9982_CR22","doi-asserted-by":"crossref","unstructured":"Dieudonn\u00e9, Y., Pelc, A.: Deterministic network exploration by anonymous silent agents with local traffic reports. In: Proceedings of 39th International Colloquium Automata, Languages, and Programming, Part II, ICALP 2012, Warwick, UK, July 9\u201313, pp. 500\u2013512 (2012)","DOI":"10.1007\/978-3-642-31585-5_45"},{"issue":"1","key":"9982_CR23","doi-asserted-by":"crossref","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"},{"key":"9982_CR24","doi-asserted-by":"crossref","unstructured":"Dieudonn\u00e9, Y., Pelc, A., Villain, V.: How to meet asynchronously at polynomial cost. In: ACM Symposium on Principles of Distributed Computing, PODC 2013, Montreal, QC, Canada, July 22\u201324, pp. 92\u201399 (2013)","DOI":"10.1145\/2484239.2484245"},{"issue":"14\u201315","key":"9982_CR25","doi-asserted-by":"crossref","first-page":"1583","DOI":"10.1016\/j.tcs.2010.01.007","volume":"411","author":"P Flocchini","year":"2010","unstructured":"Flocchini, P., Ilcinkas, D., Pelc, A., Santoro, N.: Remembering without memory: tree exploration by asynchronous oblivious robots. Theor. Comput. Sci. 411(14\u201315), 1583\u20131598 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20133","key":"9982_CR26","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/j.tcs.2005.01.001","volume":"337","author":"P Flocchini","year":"2005","unstructured":"Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous robots with limited visibility. Theor. Comput. Sci. 337(1\u20133), 147\u2013168 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9982_CR27","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1002\/net.20127","volume":"48","author":"P Fraigniaud","year":"2006","unstructured":"Fraigniaud, P., Gasieniec, L., Kowalski, D.R., Pelc, A.: Collective tree exploration. Networks 48(3), 166\u2013177 (2006)","journal-title":"Networks"},{"key":"9982_CR28","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Pelc, A.: Deterministic rendezvous in trees with little memory. In: Proceedings of 22nd International Symposium on Distributed Computing, DISC 2008, Arcachon, France, September 22\u201324, pp. 242\u2013256 (2008)","DOI":"10.1007\/978-3-540-87779-0_17"},{"issue":"2","key":"9982_CR29","doi-asserted-by":"crossref","first-page":"17","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 (2013)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"9982_CR30","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1145\/7531.7919","volume":"34","author":"GN Frederickson","year":"1987","unstructured":"Frederickson, G.N., Lynch, N.A.: Electing a leader in a synchronous ring. J. ACM 34(1), 98\u2013115 (1987)","journal-title":"J. ACM"},{"issue":"2","key":"9982_CR31","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/s00446-011-0131-y","volume":"24","author":"EG Fusco","year":"2011","unstructured":"Fusco, E.G., Pelc, A.: How much memory is needed for leader election. Distrib. Comput. 24(2), 65\u201378 (2011)","journal-title":"Distrib. Comput."},{"issue":"6","key":"9982_CR32","doi-asserted-by":"crossref","first-page":"974","DOI":"10.1287\/opre.47.6.974","volume":"47","author":"S Gal","year":"1999","unstructured":"Gal, S.: Rendezvous search on the line. Oper. Res. 47(6), 974\u2013976 (1999)","journal-title":"Oper. Res."},{"key":"9982_CR33","doi-asserted-by":"crossref","unstructured":"Guilbault, S., Pelc, A.: Asynchronous rendezvous of anonymous agents in arbitrary graphs. In: Proceedings of 15th International Conference on Principles of Distributed Systems, OPODIS 2011, Toulouse, France, December 13\u201316, pp. 421\u2013434 (2011)","DOI":"10.1007\/978-3-642-25873-2_29"},{"key":"9982_CR34","doi-asserted-by":"crossref","unstructured":"Haddar, M.A., Kacem, A.H., M\u00e9tivier, Y., Mosbah, M., Jmaiel, M.: Electing a leader in the local computation model using mobile agents. In: Proceedings of 6th ACS\/IEEE International Conference on Computer Systems and Applications, AICCSA 2008, Doha, Qatar, March 31\u2013April 4, pp. 473\u2013480 (2008)","DOI":"10.1109\/AICCSA.2008.4493575"},{"issue":"11","key":"9982_CR35","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1145\/359024.359029","volume":"23","author":"DS Hirschberg","year":"1980","unstructured":"Hirschberg, D.S., Sinclair, J.B.: Decentralized extrema-finding in circular configurations of processors. Commun. ACM 23(11), 627\u2013628 (1980)","journal-title":"Commun. ACM"},{"key":"9982_CR36","doi-asserted-by":"crossref","unstructured":"Israeli, A., Jalfon, M.: Token management schemes and random walks yield self-stabilizing mutual exclusion. In: Proceedings 9th Annual ACM Symposium on Principles of Distributed Computing, Quebec City, Quebec, Canada, August 22\u201324, pp. 119\u2013131 (1990)","DOI":"10.1145\/93385.93409"},{"issue":"34\u201336","key":"9982_CR37","doi-asserted-by":"crossref","first-page":"3235","DOI":"10.1016\/j.tcs.2010.05.020","volume":"411","author":"R Klasing","year":"2010","unstructured":"Klasing, R., Kosowski, A., Navarra, A.: Taking advantage of symmetries: gathering of many asynchronous oblivious robots on a ring. Theor. Comput. Sci. 411(34\u201336), 3235\u20133246 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9982_CR38","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.tcs.2007.09.032","volume":"390","author":"R Klasing","year":"2008","unstructured":"Klasing, R., Markou, E., Pelc, A.: Gathering asynchronous oblivious mobile robots in a ring. Theor. Comput. Sci. 390(1), 27\u201339 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"9982_CR39","doi-asserted-by":"crossref","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."},{"issue":"3","key":"9982_CR40","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1145\/1978782.1978789","volume":"7","author":"E Kranakis","year":"2011","unstructured":"Kranakis, E., Krizanc, D., Morin, P.: Randomized rendezvous with limited memory. ACM Trans. Algorithms 7(3), 34 (2011)","journal-title":"ACM Trans. Algorithms"},{"key":"9982_CR41","doi-asserted-by":"crossref","unstructured":"Kranakis, E., Santoro, N., Sawchuk, C., Krizanc, D.: Mobile agent rendezvous in a ring. In: Proceedings of 23rd International Conference on Distributed Computing Systems (ICDCS 2003), May 19\u201322, Providence, RI, USA, pp. 592\u2013599 (2003)","DOI":"10.1109\/ICDCS.2003.1203510"},{"key":"9982_CR42","unstructured":"Le Lann, G.: Distributed systems-towards a formal approach. In: Proceedings of IFIP Congress 77, Toronto, Canada, August 8\u201312, North-Holland, pp. 155\u2013160 (1977)"},{"issue":"5","key":"9982_CR43","doi-asserted-by":"crossref","first-page":"1650","DOI":"10.1137\/S036301299427816X","volume":"34","author":"WS Lim","year":"1996","unstructured":"Lim, W.S., Alpern, S.: Minimax rendezvous on the line. SIAM J. Control Optim. 34(5), 1650\u20131665 (1996)","journal-title":"SIAM J. Control Optim."},{"key":"9982_CR44","volume-title":"Distributed Algorithms","author":"NA Lynch","year":"1996","unstructured":"Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann, Burlington (1996)"},{"issue":"3","key":"9982_CR45","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1002\/net.21453","volume":"59","author":"A Pelc","year":"2012","unstructured":"Pelc, A.: Deterministic rendezvous in networks: a comprehensive survey. Networks 59(3), 331\u2013347 (2012)","journal-title":"Networks"},{"issue":"4","key":"9982_CR46","doi-asserted-by":"crossref","first-page":"758","DOI":"10.1145\/69622.357194","volume":"4","author":"GL Peterson","year":"1982","unstructured":"Peterson, G.L.: An O(n log n) unidirectional algorithm for the circular extrema problem. ACM Trans. Program. Lang. Syst. 4(4), 758\u2013762 (1982)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"9982_CR47","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM (2008). doi: 10.1145\/1391289.1391291","DOI":"10.1145\/1391289.1391291"},{"issue":"3","key":"9982_CR48","doi-asserted-by":"crossref","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"},{"key":"9982_CR49","doi-asserted-by":"crossref","unstructured":"Yamashita, M., Kameda, T.: Electing a leader when processor identity numbers are not distinct (extended abstract). In: Proceedings of 3rd International Workshop on Distributed Algorithms, Nice, France, September 26\u201328, pp. 303\u2013314 (1989)","DOI":"10.1007\/3-540-51687-5_52"},{"issue":"1","key":"9982_CR50","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1109\/71.481599","volume":"7","author":"M Yamashita","year":"1996","unstructured":"Yamashita, M., Kameda, T.: Computing on anonymous networks: Part I. Characterizing the solvable cases. IEEE Trans. Parallel Distrib. Syst. 7(1), 69\u201389 (1996)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"9982_CR51","doi-asserted-by":"crossref","unstructured":"Yu, X., Yung, M.: Agent rendezvous: a dynamic symmetry-breaking problem. In: Proceedings of 23rd International Colloquium on Automata, Languages, and Programming, ICALP 1996, Paderborn, Germany, July 8\u201312, pp. 610\u2013621 (1996)","DOI":"10.1007\/3-540-61440-0_163"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9982-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-9982-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9982-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T23:47:23Z","timestamp":1559087243000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-9982-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,4]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2]]}},"alternative-id":["9982"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-9982-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,4]]}}}