Self-stabilizing robots in highly dynamic environments

作     者：Bournat, Marjorie Datta, Ajoy K. Dubois, Swan 

作者机构：Sorbonne Univ CNRS INRIA LIP6 UMR 7606 4 Pl Jussieu F-75252 Paris 05 France Univ Nevada Las Vegas NV 89154 USA 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2019年第772卷

页      面：88-110页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：ANR project ESTATE [ANR-16-CE25-0009-03] French state funds by the ANR (Agence Nationale de la Recherche) 

主　　题：Highly dynamic graphs Evolving graphs Perpetual exploration Fully synchronous robots Self-stabilizing algorithm 

摘      要：This paper deals with the classical problem of exploring a ring by a cohort of synchronous robots. We focus on the perpetual version of this problem in which it is required that each node of the ring is visited by a robot infinitely often. The challenge in this paper is twofold. First, we assume that the robots evolve in a highly dynamic ring, i.e., edges may appear and disappear unpredictably without any recurrence, periodicity, or stability assumption. The only assumption we made (known as the temporal connectivity assumption) is that each node is infinitely often reachable from any other node. Second, we aim at providing a self-stabilizing algorithm to the robots, i.e., the algorithm must guarantee an eventual correct behavior regardless of the initial state and positions of the robots. In this harsh environment, our contribution is to fully characterize, for each size of the ring, the necessary and sufficient number of robots to solve deterministically the problem. (C) 2018 Elsevier B.V. All rights reserved.