License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2019.22
URN: urn:nbn:de:0030-drops-118082
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11808/
Gotoh, Tsuyoshi ;
Flocchini, Paola ;
Masuzawa, Toshimitsu ;
Santoro, Nicola
Tight Bounds on Distributed Exploration of Temporal Graphs
Abstract
Temporal graphs (or evolving graphs) are time-varying graphs where time is assumed to be discrete. In this paper, we consider for the first time the problem of exploring temporal graphs of arbitrary unknown topology. We study the feasibility of exploration, under both the Fsync and Ssync schedulers, focusing on the number of agents necessary and sufficient to explore such graphs.
We first consider the minimal (i.e., less restrictive) assumption on the dynamics of the graph under which exploration is still feasible: temporal connectivity. Let ℋ be the class of temporally connected graphs; we show that for any temporal graph ? ∈ ℋ the number of agents sufficient to perform exploration is related to the number of its transient edges, a parameter η(?) we call evanescence of the graph. More precisely, any ? ∈ ℋ can be explored by a team of k ≥ 2 η(?) +1 agents; this bound is tight as we prove there are ? ∈ ℋ that cannot be explored by 2 η(?) agents.
We then turn our attention to the well-known stronger assumption on the dynamics of the graph, called 1-interval connectivity: the graph is connected at any time step. Let ? ⊂ ℋ be the class of these always-connected temporal graphs. For this class, we prove the existence of a difference between Fsync and Ssync when there is a bound ? on the number of edges missing at each time. In fact, we show a tight bound of 2 ? +1 on the number of agents necessary and sufficient in Ssync, and a smaller tight bound of 2 ? in Fsync. As a corollary, we re-establish two recently published bounds for 1-interval connected rings.
BibTeX - Entry
@InProceedings{gotoh_et_al:LIPIcs:2020:11808,
author = {Tsuyoshi Gotoh and Paola Flocchini and Toshimitsu Masuzawa and Nicola Santoro},
title = {{Tight Bounds on Distributed Exploration of Temporal Graphs}},
booktitle = {23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
pages = {22:1--22:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-133-7},
ISSN = {1868-8969},
year = {2020},
volume = {153},
editor = {Pascal Felber and Roy Friedman and Seth Gilbert and Avery Miller},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11808},
URN = {urn:nbn:de:0030-drops-118082},
doi = {10.4230/LIPIcs.OPODIS.2019.22},
annote = {Keywords: Distributed algorithm, Mobile agents, Exploration of dynamic networks, Arbitrary footprint}
}
|
Keywords: |
|
Distributed algorithm, Mobile agents, Exploration of dynamic networks, Arbitrary footprint |
|
Collection: |
|
23rd International Conference on Principles of Distributed Systems (OPODIS 2019) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
11.02.2020 |
