Document Open Access Logo

Fast Deterministic Rendezvous in Labeled Lines

Authors Avery Miller , Andrzej Pelc

PDF
Thumbnail PDF

File

LIPIcs.DISC.2023.29.pdf
  • Filesize: 0.86 MB
  • 22 pages

Document Identifiers

Author Details

Avery Miller
  • University of Manitoba, Winnipeg, Canada
Andrzej Pelc
  • Université du Québec en Outaouais, Canada

Funding

  • Miller, Avery: Supported by NSERC Discovery Grant 2017-05936.
  • Pelc, Andrzej: Partially supported by NSERC Discovery Grant 2018-03899 and by the Research Chair in Distributed Computing at the Université du Québec en Outaouais.

Cite As Get BibTex

Avery Miller and Andrzej Pelc. Fast Deterministic Rendezvous in Labeled Lines. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 29:1-29:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.DISC.2023.29

Abstract

Two mobile agents, starting from different nodes of a network modeled as a graph, and woken up at possibly different times, have to meet at the same node. This problem is known as rendezvous. Agents move in synchronous rounds. In each round, an agent can either stay idle or move to an adjacent node. We consider deterministic rendezvous in the infinite line, i.e., the infinite graph with all nodes of degree 2. Each node has a distinct label which is a positive integer. An agent currently located at a node can see its label and both ports 0 and 1 at the node. The time of rendezvous is the number of rounds until meeting, counted from the starting round of the earlier agent.
We consider three scenarios. In the first scenario, each agent knows its position in the line, i.e., each of them knows its initial distance from the smallest-labeled node, on which side of this node it is located, and the direction towards it. For this scenario, we design a rendezvous algorithm working in time O(D), where D is the initial distance between the agents. This complexity is clearly optimal. In the second scenario, each agent knows a priori only the label of its starting node and the initial distance D between them. In this scenario, we design a rendezvous algorithm working in time O(Dlog^*𝓁), where 𝓁 is the larger label of the starting nodes. We also prove a matching lower bound Ω(Dlog^*𝓁). Finally, in the most general scenario, where each agent knows a priori only the label of its starting node, we design a rendezvous algorithm working in time O(D²(log^*𝓁)³), which is thus at most cubic in the lower bound. All our results remain valid (with small changes) for arbitrary finite lines and for cycles. Our algorithms are drastically better than approaches that use graph exploration, which have running times that depend on the size or diameter of the graph.
Our main methodological tool, and the main novelty of the paper, is a two way reduction: from fast colouring of the infinite labeled line using a constant number of colours in the LOCAL model to fast rendezvous in this line, and vice-versa. In one direction we use fast node colouring to quickly break symmetry between the identical agents. In the other direction, a lower bound on colouring time implies a lower bound on the time of breaking symmetry between the agents, and hence a lower bound on their meeting time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • rendezvous
  • deterministic algorithm
  • mobile agent
  • labeled line
  • graph colouring

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Steve Alpern. The rendezvous search problem. SIAM Journal on Control and Optimization, 33(3):673-683, 1995. URL: https://doi.org/10.1137/S0363012993249195.
  2. Steve Alpern. Rendezvous search on labeled networks. Naval Research Logistics (NRL), 49(3):256-274, 2002. URL: https://doi.org/10.1002/nav.10011.
  3. Steve Alpern and Shmuel Gal. The theory of search games and rendezvous, volume 55 of International series in operations research and management science. Kluwer, 2003. Google Scholar
  4. E. J. Anderson and R. R. Weber. The rendezvous problem on discrete locations. Journal of Applied Probability, 27(4):839-851, 1990. URL: http://www.jstor.org/stable/3214827.
  5. Edward J. Anderson and Sándor P. Fekete. Asymmetric rendezvous on the plane. In Ravi Janardan, editor, Proceedings of the Fourteenth Annual Symposium on Computational Geometry, Minneapolis, Minnesota, USA, June 7-10, 1998, pages 365-373. ACM, 1998. URL: https://doi.org/10.1145/276884.276925.
  6. Edward J. Anderson and Sándor P. Fekete. Two dimensional rendezvous search. Oper. Res., 49(1):107-118, 2001. URL: https://doi.org/10.1287/opre.49.1.107.11191.
  7. Vic Baston and Shmuel Gal. Rendezvous on the line when the players' initial distance is given by an unknown probability distribution. SIAM Journal on Control and Optimization, 36(6):1880-1889, 1998. URL: https://doi.org/10.1137/S0363012996314130.
  8. Vic Baston and Shmuel Gal. Rendezvous search when marks are left at the starting points. Naval Research Logistics, 48(8):722-731, December 2001. URL: https://doi.org/10.1002/nav.1044.
  9. Subhash Bhagat and Andrzej Pelc. Deterministic rendezvous in infinite trees. CoRR, abs/2203.05160, 2022. URL: https://doi.org/10.48550/arXiv.2203.05160.
  10. Subhash Bhagat and Andrzej Pelc. How to meet at a node of any connected graph. In Christian Scheideler, editor, 36th International Symposium on Distributed Computing, DISC 2022, October 25-27, 2022, Augusta, Georgia, USA, volume 246 of LIPIcs, pages 11:1-11:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.DISC.2022.11.
  11. Sébastien Bouchard, Yoann Dieudonné, Andrzej Pelc, and Franck Petit. Almost universal anonymous rendezvous in the plane. In Christian Scheideler and Michael Spear, editors, SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, July 15-17, 2020, pages 117-127. ACM, 2020. URL: https://doi.org/10.1145/3350755.3400283.
  12. Richard Cole and Uzi Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control., 70(1):32-53, 1986. URL: https://doi.org/10.1016/S0019-9958(86)80023-7.
  13. Andrew Collins, Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski, and Russell A. Martin. Synchronous rendezvous for location-aware agents. In David Peleg, editor, Distributed Computing - 25th International Symposium, DISC 2011, Rome, Italy, September 20-22, 2011. Proceedings, volume 6950 of Lecture Notes in Computer Science, pages 447-459. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-24100-0_42.
  14. Jurek Czyzowicz, Leszek Gasieniec, Ryan Killick, and Evangelos Kranakis. Symmetry breaking in the plane: Rendezvous by robots with unknown attributes. In Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 4-13. ACM, 2019. URL: https://doi.org/10.1145/3293611.3331608.
  15. Jurek Czyzowicz, Adrian Kosowski, and Andrzej Pelc. How to meet when you forget: log-space rendezvous in arbitrary graphs. Distributed Comput., 25(2):165-178, 2012. URL: https://doi.org/10.1007/s00446-011-0141-9.
  16. Anders Dessmark, Pierre Fraigniaud, Dariusz R. Kowalski, and Andrzej Pelc. Deterministic rendezvous in graphs. Algorithmica, 46(1):69-96, 2006. URL: https://doi.org/10.1007/s00453-006-0074-2.
  17. Yoann Dieudonné and Andrzej Pelc. Anonymous meeting in networks. Algorithmica, 74(2):908-946, 2016. URL: https://doi.org/10.1007/s00453-015-9982-0.
  18. Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer. Gathering of asynchronous robots with limited visibility. Theor. Comput. Sci., 337(1-3):147-168, 2005. URL: https://doi.org/10.1016/j.tcs.2005.01.001.
  19. Pierre Fraigniaud and Andrzej Pelc. Delays induce an exponential memory gap for rendezvous in trees. ACM Trans. Algorithms, 9(2):17:1-17:24, 2013. URL: https://doi.org/10.1145/2438645.2438649.
  20. Dariusz R. Kowalski and Adam Malinowski. How to meet in anonymous network. Theor. Comput. Sci., 399(1-2):141-156, 2008. URL: https://doi.org/10.1016/j.tcs.2008.02.010.
  21. Evangelos Kranakis, Danny Krizanc, and Pat Morin. Randomized rendezvous with limited memory. ACM Trans. Algorithms, 7(3):34:1-34:12, 2011. URL: https://doi.org/10.1145/1978782.1978789.
  22. Evangelos Kranakis, Nicola Santoro, Cindy Sawchuk, and Danny Krizanc. Mobile agent rendezvous in a ring. In 23rd International Conference on Distributed Computing Systems (ICDCS 2003), 19-22 May 2003, Providence, RI, USA, pages 592-599. IEEE Computer Society, 2003. URL: https://doi.org/10.1109/ICDCS.2003.1203510.
  23. Juhana Laurinharju and Jukka Suomela. Linial’s lower bound made easy. CoRR, abs/1402.2552, 2014. URL: http://arxiv.org/abs/1402.2552, URL: https://arxiv.org/abs/1402.2552.
  24. Wei Shi Lim and Steve Alpern. Minimax rendezvous on the line. SIAM Journal on Control and Optimization, 34(5):1650-1665, 1996. URL: https://doi.org/10.1137/S036301299427816X.
  25. Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. URL: https://doi.org/10.1137/0221015.
  26. Avery Miller and Andrzej Pelc. Tradeoffs between cost and information for rendezvous and treasure hunt. J. Parallel Distributed Comput., 83:159-167, 2015. URL: https://doi.org/10.1016/j.jpdc.2015.06.004.
  27. Andrzej Pelc. Deterministic rendezvous in networks: A comprehensive survey. Networks, 59(3):331-347, 2012. URL: https://doi.org/10.1002/net.21453.
  28. Andrzej Pelc. Deterministic rendezvous algorithms. In Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro, editors, Distributed Computing by Mobile Entities, Current Research in Moving and Computing, volume 11340 of Lecture Notes in Computer Science, pages 423-454. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-11072-7_17.
  29. David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, 2000. URL: https://doi.org/10.1137/1.9780898719772.
  30. Amnon Ta-Shma and Uri Zwick. Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences. ACM Trans. Algorithms, 10(3):12:1-12:15, 2014. URL: https://doi.org/10.1145/2601068.
  31. L. C. Thomas. Finding your kids when they are lost. Journal of the Operational Research Society, 43(6):637-639, 1992. URL: https://doi.org/10.1057/jors.1992.89.
  32. Roger Wattenhofer. Principles of distributed computing, 2023. Accessed on 2023-04-16. URL: https://disco.ethz.ch/courses/fs23/podc/.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact