2026-07-22T08:36:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22548 2025-10-02T11:05:52Z ddc:004 open_access

Crash-Tolerant Perpetual Exploration with Myopic Luminous Robots on Rings Ooshita, Fukuhito Kitamura, Naoki Eguchi, Ryota Inoue, Michiko Kakugawa, Hirotsugu Kamei, Sayaka Shibata, Masahiro Sudo, Yuichi mobile robots crash faults LCM model exploration We investigate crash-tolerant perpetual exploration algorithms by myopic luminous robots on ring networks. Myopic robots mean that they can observe nodes only within a certain fixed distance ϕ, and luminous robots mean that they have light devices that can emit a color from a set of colors. The goal of perpetual exploration is to ensure that robots, starting from specific initial positions and colors, move in such a way that every node is visited by at least one robot infinitely often. As a main contribution, we clarify the tight necessary and sufficient number of robots to realize perpetual exploration when at most f robots crash. In the fully synchronous model, we prove that f+2 robots are necessary and sufficient for any ϕ ≥ 1. In the semi-synchronous and asynchronous models, we prove that 3f+3 (resp., 2f+2) robots are necessary and sufficient if ϕ = 1 (resp., ϕ ≥ 2). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fukuhito Ooshita and Naoki Kitamura and Ryota Eguchi and Michiko Inoue and Hirotsugu Kakugawa and Sayaka Kamei and Masahiro Shibata and Yuichi Sudo 2025 Is Part Of LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2024.12 urn:nbn:de:0030-drops-225486 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.12 eng https://creativecommons.org/licenses/by/4.0/legalcode