An Asynchronous Maximum Independent Set Algorithm by Myopic Luminous Robots on Grids
| Autor: | Sayaka Kamei, Sebastien Tixeuil |
|---|---|
| Přispěvatelé: | Graduate School of Advanced Science and Engineering [Higashi-Hiroshima], Hiroshima University, Networks and Performance Analysis (NPA), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Laboratory of Information, Network and Communication Sciences (LINCS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU), ANR-19-CE25-0005,SAPPORO,Sûreté et preuve de protocoles adaptatifs pour robots oublieux(2019), ANR-16-CE25-0009,ESTATE,Auto-stabilisation et amélioration de la sûreté dans les environnements distribués évoluant dans le temps(2016) |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Computer Science::Robotics General Computer Science Computer Science - Distributed Parallel and Cluster Computing [INFO.INFO-RB]Computer Science [cs]/Robotics [cs.RO] Distributed Parallel and Cluster Computing (cs.DC) [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] |
| Zdroj: | The Computer Journal The Computer Journal, 2022, ⟨10.1093/comjnl/bxac158⟩ |
| ISSN: | 0010-4620 1460-2067 |
| DOI: | 10.1093/comjnl/bxac158⟩ |
| Popis: | We consider the problem of constructing a maximum independent set with mobile myopic luminous robots on a grid network whose size is finite but unknown to the robots. In this setting, the robots enter the grid network one by one from a corner of the grid, and they eventually have to be disseminated on the grid nodes so that the occupied positions form a maximum independent set of the network. We assume that robots are asynchronous, anonymous, silent and they execute the same distributed algorithm. In this paper, we propose two algorithms: The first one assumes that the number of light colors of each robot is three and the visible range is two, but uses the additional assumption that a local edge-labeling exists for each node. To remove this assumption, the second one assumes that the number of light colors of each robot is seven, and that the visible range is three. In both algorithms, the number of movements is $O(n(L+l))$ steps, where $n$ is the number of nodes and $L$ and $l$ are the grid dimensions. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|