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.24
URN: urn:nbn:de:0030-drops-100843
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10084/
Go to the corresponding LIPIcs Volume Portal

Okumura, Takashi ; Wada, Koichi ; Défago, Xavier

Optimal Rendezvous L-Algorithms for Asynchronous Mobile Robots with External-Lights

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

Abstract

We study the Rendezvous problem for two autonomous mobile robots in asynchronous settings with persistent memory called light. It is well known that Rendezvous is impossible in a basic model when robots have no lights, even if the system is semi-synchronous. On the other hand, Rendezvous is possible if robots have lights of various types with a constant number of colors. If robots can observe not only their own lights but also other robots' lights, their lights are called full-light. If robots can only observe the state of other robots' lights, the lights are called external-light. This paper focuses on robots with external-lights in asynchronous settings and a particular class of algorithms called L-algorithms, where an L-algorithm computes a destination based only on the current colors of observable lights. When considering L-algorithms, Rendezvous can be solved by robots with full-lights and three colors in general asynchronous settings (called ASYNC) and the number of colors is optimal under these assumptions. In contrast, there exist no L-algorithms in ASYNC with external-lights regardless of the number of colors.
In this paper, extending the impossibility result, we show that there exist no L-algorithms in so-called LC-1-Bounded ASYNC with external-lights regardless of the number of colors, where LC-1-Bounded ASYNC is a proper subset of ASYNC and other robots can execute at most one Look operation between the Look operation of a robot and its subsequent Compute operation. We also show that LC-1-Bounded ASYNC is the minimal subclass in which no L-algorithms with external-lights exist. That is, Rendezvous can be solved by L-algorithms using external-lights with a finite number of colors in LC-0-Bounded ASYNC (equivalently LC-atomic ASYNC). Furthermore, we show that the algorithms are optimal in the number of colors they use.

BibTeX - Entry

@InProceedings{okumura_et_al:LIPIcs:2018:10084,
  author =	{Takashi Okumura and Koichi Wada and Xavier D{\'e}fago},
  title =	{{Optimal Rendezvous L-Algorithms for Asynchronous Mobile Robots with External-Lights}},
  booktitle =	{22nd International Conference on Principles of Distributed  Systems (OPODIS 2018)},
  pages =	{24:1--24: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/10084},
  URN =		{urn:nbn:de:0030-drops-100843},
  doi =		{10.4230/LIPIcs.OPODIS.2018.24},
  annote =	{Keywords: Autonomous mobile robots, Rendezvous, Lights, L-algorithms}
}

Keywords: Autonomous mobile robots, Rendezvous, Lights, L-algorithms
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