Live Exploration of Dynamic Rings

Abstract

Almost all the vast literature on graph explorationassumes that the graph is static: its topology does not changeduring the exploration, except for occasional faults. To date, very little is known on exploration of dynamic graphs, wherethe topology is continously changing. The few studies havebeen limited to the centralized (or post-mortem) case, assumingcomplete a priori knowledge of the changes and the times of theiroccurrence, and have only considered fully synchronous systems. In this paper, we start the study of the decentralized (or live) exploration of dynamic graphs, i.e. when the agents operate inthe graph unaware of the location and timing of the changes. Weconsider dynamic rings under the standard 1-interval-connectedrestriction, and investigate the feasibility of their exploration, inboth the fully synchronous and semi-synchronous cases. Whenexploration is possible we examine at what cost, focusing on theminimum number of agents capable of exploring the ring. Weestablish several results highlighting the impact that anonymityand structural knowledge have on the feasibility and complexityof the problem.