Distributed exploration of dynamic rings
From MaRDI portal
Publication:2174251
DOI10.1007/S00446-018-0339-1zbMATH Open1433.68054arXiv1512.05306OpenAlexW2888048527WikidataQ129359859 ScholiaQ129359859MaRDI QIDQ2174251FDOQ2174251
Authors: Stefan Dobrev, P. Flocchini, N. Santoro, Giuseppe Antonio Di Luna 
Publication date: 21 April 2020
Published in: Distributed Computing (Search for Journal in Brave)
Abstract: In the graph exploration problem, a team of mobile computational entities, called agents, arbitrarily positioned at some nodes of a graph, must cooperate so that each node is eventually visited by at least one agent. In the literature, the main focus has been on graphs that are static; that is, the topology is either invariant in time or subject to localized changes. The few studies on exploration of dynamic graphs have been almost all limited to the centralized case (i.e., assuming complete a priori knowledge of the changes and the times of their occurrence). We investigate the decentralized exploration of dynamic graphs (i.e., when the agents are unaware of the location and timing of the changes) focusing, in this paper, on dynamic systems whose underlying graph is a ring. We first consider the fully-synchronous systems traditionally assumed in the literature; i.e., all agents are active at each time step. We then introduce the notion of semi-synchronous systems, where only a subset of agents might be active at each time step (the choice of the subset is made by an adversary); this model is common in the context of mobile agents in continuous spaces but has never been studied before for agents moving in graphs. Our main focus is on the impact that the level of synchrony as well as other factors such as anonymity, knowledge of the size of the ring, and chirality (i.e., common orientation) have on the solvability of the problem, focusing on the minimum number of agents necessary. We draw an extensive map of feasibility, and of complexity in terms of minimum number of agent movements. All our sufficiency proofs are constructive, and almost all our solution protocols are asymptotically optimal.
Full work available at URL: https://arxiv.org/abs/1512.05306
Recommendations
- Structural Information and Communication Complexity
- Optimal deterministic ring exploration with oblivious asynchronous robots
- Optimal probabilistic ring exploration by semi-synchronous oblivious robots
- Optimal probabilistic ring exploration by semi-synchronous oblivious robots
- scientific article; zbMATH DE number 4058846
- Partial Gathering of Mobile Agents in Dynamic Rings
- Gathering in dynamic rings
- Gathering in dynamic rings
- Almost uniform deployment of mobile agents in dynamic rings
- Compacting and grouping mobile agents on dynamic rings
Graph theory (including graph drawing) in computer science (68R10) Network design and communication in computer systems (68M10) Distributed systems (68M14)
Cites Work
- Exploring an unknown graph
- Dynamic graph models
- Graph exploration by a finite automaton
- How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
- Traveling salesman problems in temporal graphs
- Distributed computation in dynamic networks
- COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
- Map construction of unknown graphs by multiple agents
- Exploring Unknown Environments
- Exploring an unknown dangerous graph using tokens
- Searching for a black hole in arbitrary networks: optimal mobile agents protocols
- Efficient routing in carrier-based mobile networks
- Coordinated consensus in dynamic networks
- On the exploration of time-varying networks
- Parsimonious flooding in dynamic graphs
- Measuring Temporal Lags in Delay-Tolerant Networks
- Searching for black holes in subways
- Exploring Unknown Undirected Graphs
- Exploration of the \(T\)-interval-connected dynamic graphs: the case of the ring
- Exploration of constantly connected dynamic graphs based on cactuses
- Exploring an unknown dangerous graph with a constant number of tokens
- Election and rendezvous with incomparable labels
- Fast Byzantine agreement in dynamic networks
- Gathering in dynamic rings
- Shortest, fastest, and foremost broadcast in dynamic networks
- Distributed exploration of dynamic rings
- Deterministic Network Exploration by Anonymous Silent Agents with Local Traffic Reports
Cited In (21)
- A tight lower bound for semi-synchronous collaborative grid exploration
- Black hole search in dynamic cactus graph
- Cops \& robber on periodic temporal graphs: characterization and improved bounds
- Beyond rings: gathering in 1-interval connected graphs
- Exploring a Dynamic Ring Without Landmark
- Exploration of dynamic cactuses with sub-logarithmic overhead
- Live exploration with mobile robots in a dynamic ring (revisited)
- Distributed exploration of dynamic rings
- Exploration of dynamic tori by multiple agents
- Efficient live exploration of a dynamic ring with mobile robots
- Partial Gathering of Mobile Agents in Dynamic Rings
- Exploring a dynamic ring without landmark
- Exploration of dynamic networks: tight bounds on the number of agents
- Exploration of Time-Varying Connected Graphs with Silent Agents
- Non-strict Temporal Exploration
- Exploration of dynamic ring networks by a single agent with the H-hops and S-time steps view
- Gathering in dynamic rings
- Simple, strict, proper, happy: a study of reachability in temporal graphs
- Invited paper: Simple, strict, proper, happy: a study of reachability in temporal graphs
- Exploration of carrier-based time-varying networks: the power of waiting
- Temporal cliques admit sparse spanners
This page was built for publication: Distributed exploration of dynamic rings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2174251)
