2026-07-22T15:55:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10084 2024-03-06T10:45:35Z ddc:004 open_access

Optimal Rendezvous L-Algorithms for Asynchronous Mobile Robots with External-Lights Okumura, Takashi Wada, Koichi Défago, Xavier Autonomous mobile robots Rendezvous Lights L-algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Takashi Okumura and Koichi Wada and Xavier Défago 2019 Is Part Of LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2018.24 urn:nbn:de:0030-drops-100843 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.24 eng https://creativecommons.org/licenses/by/3.0/legalcode