TY - GEN
T1 - Deterministic computations in time-varying graphs
T2 - 6th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science, TCS 2010, Held as Part of 21st IFIP World Computer Congress, WCC 2010
AU - Casteigts, Arnaud
AU - Flocchini, Paola
AU - Mans, Bernard
AU - Santoro, Nicola
PY - 2010
Y1 - 2010
N2 - Most highly dynamic infrastructure-less networks have in common that the assumption of connectivity does not necessarily hold at a given instant. Still, communication routes can be available between any pair of nodes over time and space. These networks (variously called delay-tolerant, disruptive-tolerant, challenged) are naturally modeled as time-varying graphs (or evolving graphs), where the existence of an edge is a function of time. In this paper we study deterministic computations under unstructured mobility, that is when the edges of the graph appear infinitely often but without any (known) pattern. In particular, we focus on the problem of broadcasting with termination detection. We explore the problem with respect to three possible metrics: the date of message arrival (foremost), the time spent doing the broadcast (fastest), and the number of hops used by the broadcast (shortest). We prove that the solvability and complexity of this problem vary with the metric considered, as well as with the type of knowledge a priori available to the entities. These results draw a complete computability map for this problem when mobility is unstructured.
AB - Most highly dynamic infrastructure-less networks have in common that the assumption of connectivity does not necessarily hold at a given instant. Still, communication routes can be available between any pair of nodes over time and space. These networks (variously called delay-tolerant, disruptive-tolerant, challenged) are naturally modeled as time-varying graphs (or evolving graphs), where the existence of an edge is a function of time. In this paper we study deterministic computations under unstructured mobility, that is when the edges of the graph appear infinitely often but without any (known) pattern. In particular, we focus on the problem of broadcasting with termination detection. We explore the problem with respect to three possible metrics: the date of message arrival (foremost), the time spent doing the broadcast (fastest), and the number of hops used by the broadcast (shortest). We prove that the solvability and complexity of this problem vary with the metric considered, as well as with the type of knowledge a priori available to the entities. These results draw a complete computability map for this problem when mobility is unstructured.
UR - https://www.scopus.com/pages/publications/84872076644
U2 - 10.1007/978-3-642-15240-5_9
DO - 10.1007/978-3-642-15240-5_9
M3 - Conference proceeding contribution
AN - SCOPUS:84872076644
SN - 3642152392
SN - 9783642152399
T3 - IFIP Advances in Information and Communication Technology
SP - 111
EP - 124
BT - Theoretical Computer Science
A2 - Calude, Cristian S.
A2 - Sassone, Vladimiro
PB - Springer, Springer Nature
CY - Berlin; Heidelberg
Y2 - 20 September 2010 through 23 September 2010
ER -