License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2018.25
URN: urn:nbn:de:0030-drops-100855
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10085/
Go to the corresponding LIPIcs Volume Portal

Czyzowicz, Jurek ; Killick, Ryan ; Kranakis, Evangelos

Linear Rendezvous with Asymmetric Clocks

pdf-format:
LIPIcs-OPODIS-2018-25.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{czyzowicz_et_al:LIPIcs:2018:10085,
  author =	{Jurek Czyzowicz and Ryan Killick and Evangelos Kranakis},
  title =	{{Linear Rendezvous with Asymmetric Clocks}},
  booktitle =	{22nd International Conference on Principles of Distributed  Systems (OPODIS 2018)},
  pages =	{25:1--25:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{125},
  editor =	{Jiannong Cao and Faith Ellen and Luis Rodrigues and Bernardo Ferreira},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10085},
  URN =		{urn:nbn:de:0030-drops-100855},
  doi =		{10.4230/LIPIcs.OPODIS.2018.25},
  annote =	{Keywords: anonymous, asymmetric clock, infinite line, rendezvous, mobile robot, speed, competitive ratio}
}

Keywords: anonymous, asymmetric clock, infinite line, rendezvous, mobile robot, speed, competitive ratio
Collection: 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)
Issue Date: 2018
Date of publication: 15.01.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI