Document Open Access Logo

Linear Rendezvous with Asymmetric Clocks

Authors Jurek Czyzowicz, Ryan Killick, Evangelos Kranakis

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2018.25.pdf
  • Filesize: 479 kB
  • 16 pages

Document Identifiers

Author Details

Jurek Czyzowicz
  • Département d'informatique, Université du Québec en Outaouais, Gatineau, Canada
Ryan Killick
  • School of Computer Science, Carleton University, Ottawa, Canada
Evangelos Kranakis
  • School of Computer Science, Carleton University, Ottawa, Canada

Funding

  • Czyzowicz, Jurek: Research supported in part by NSERC Discovery grant
  • Killick, Ryan: Research supported by the Ontario Graduate Scholarship. Eligible for best student paper award.
  • Kranakis, Evangelos: Research supported in part by NSERC Discovery grant

Cite As Get BibTex

Jurek Czyzowicz, Ryan Killick, and Evangelos Kranakis. Linear Rendezvous with Asymmetric Clocks. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.OPODIS.2018.25

Abstract

Two anonymous robots placed at different positions on an infinite line need to rendezvous. Each robot possesses a clock which it uses to time its movement. However, the robot's individual parameters in the form of their walking speed and time unit may or may not be the same for both robots. We study the feasibility of rendezvous in different scenarios, in which some subsets of these parameters are not the same. As the robots are anonymous, they execute the same algorithm and when both parameters are identical the rendezvous is infeasible. We propose a universal algorithm, such that the robots are assured of meeting in finite time, in any case when at least one of the parameters is not equal for both robots.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Distributed algorithms
Keywords
  • anonymous
  • asymmetric clock
  • infinite line
  • rendezvous
  • mobile robot
  • speed
  • competitive ratio

Metrics

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

References

  1. S. Alpern and S. Gal. The theory of search games and rendezvous, volume 55. Kluwer Academic Publishers, 2002. Google Scholar
  2. R. Baeza Yates, J. Culberson, and G. Rawlins. Searching in the plane. Information and Computation, 106(2):234-252, 1993. Google Scholar
  3. R. Baeza-Yates and R. Schott. Parallel searching in the plane. Computational Geometry, 5(3):143-154, 1995. Google Scholar
  4. L. Barrière, P. Flocchini, P. Fraigniaud, and N. Santoro. Rendezvous and Election of Mobile Agents: Impact of Sense of Direction. Theory Comput. Syst., 40(2):143-162, 2007. Google Scholar
  5. A. Beck. On the linear search problem. Israel Journal of Mathematics, 2(4):221-228, 1964. Google Scholar
  6. A. Beck and D. Newman. Yet more on the linear search problem. Israel Journal of Mathematics, 8(4):419-429, 1970. Google Scholar
  7. R. Bellman. An optimal search. SIAM Review, 5(3):274-274, 1963. Google Scholar
  8. S. Bouchard, Y. Dieudonné, A. Pelc, and F. Petit. On deterministic rendezvous at a node of agents with arbitrary velocities. Inf. Process. Lett., 133:39-43, 2018. Google Scholar
  9. Q. Bramas and S. Tixeuil. Wait-Free Gathering Without Chirality. In Structural Information and Communication Complexity - 22nd International Colloquium, SIROCCO 2015, Montserrat, Spain, July 14-16, 2015, Post-Proceedings, pages 313-327, 2015. Google Scholar
  10. M. Chrobak, L. Gasieniec, Gorry T., and R. Martin. Group Search on the Line. In Proceedings of SOFSEM 2015, LNCS 8939, pages 164-176. Springer, 2015. Google Scholar
  11. R. Cohen and D. Peleg. Convergence of autonomous mobile robots with inaccurate sensors and movements. In Annual Symposium on Theoretical Aspects of Computer Science, pages 549-560. Springer, 2006. Google Scholar
  12. A. Collins, J. Czyzowicz, L. Gasieniec, and A. Labourel. Tell me where I am so I can meet you sooner. In International Colloquium on Automata, Languages, and Programming, pages 502-514. Springer, 2010. Google Scholar
  13. R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth. On the Lambert W function. Advances in Computational Mathematics, 5(1):329-359, December 1996. Google Scholar
  14. J. Czyzowicz, E. Kranakis, D. Krizanc, L. Narayanan, and J. Opatrny. Search on a Line with Faulty Robots. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC, pages 405-414, 2016. Google Scholar
  15. J. Czyzowicz, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny, and S. Shende. Linear search with terrain-dependent speeds. In International Conference on Algorithms and Complexity, pages 430-441. Springer, 2017. Google Scholar
  16. G. De Marco, L. Gargano, E. Kranakis, D Krizanc, A. Pelc, and U. Vaccaro. Asynchronous deterministic rendezvous in graphs. Theoretical Computer Science, 355(3):315-326, 2006. Google Scholar
  17. E. D. Demaine, S. P. Fekete, and S. Gal. Online searching with turn cost. Theoretical Computer Science, 361(2):342-355, 2006. Google Scholar
  18. A. Dessmark, P. Fraigniaud, D. R. Kowalski, and A. Pelc. Deterministic Rendezvous in Graphs. Algorithmica, 46(1):69-96, 2006. Google Scholar
  19. Y. Dieudonné, A. Pelc, and V. Villain. How to Meet Asynchronously at Polynomial Cost. SIAM J. Comput., 44(3):844-867, 2015. Google Scholar
  20. O. Feinerman, A. Korman, S. Kutten, and Y. Rodeh. Fast rendezvous on a cycle by agents with different speeds. Theoretical Computer Science, 688:77-85, 2017. Google Scholar
  21. A. Hoorfar and M. Hassani. Inequalities on the Lambert W function and hyperpower function. JIPAM. Journal of Inequalities in Pure &Applied Mathematics [electronic only], 9, January 2008. Google Scholar
  22. T. Izumi, S. Souissi, Y. Katayama, N. Inuzuka, X. Défago, K. Wada, and M. Yamashita. The Gathering Problem for Two Oblivious Robots with Unreliable Compasses. SIAM J. Comput., 41(1):26-46, 2012. Google Scholar
  23. M.-Y. Kao, J. H. Reif, and S. R. Tate. Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. Information and Computation, 131(1):63-79, 1996. Google Scholar
  24. E. Kranakis, N. Santoro, C. Sawchuk, and D. Krizanc. Mobile agent rendezvous in a ring. In Distributed Computing Systems, 2003. Proceedings. 23rd International Conference on, pages 592-599. IEEE, 2003. Google Scholar
  25. A. Pelc. Deterministic rendezvous in networks: A comprehensive survey. Networks, 59(3):331-347, 2012. Google Scholar
  26. G. Stachowiak. Asynchronous Deterministic Rendezvous on the Line. In SOFSEM 2009: Theory and Practice of Computer Science, pages 497-508. Springer, 2009. Google Scholar
  27. X. Yu and M. Yung. Agent rendezvous: A dynamic symmetry-breaking problem. In International Colloquium on Automata, Languages, and Programming, pages 610-621. Springer, 1996. Google Scholar
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