Deterministic Computations in Time-Varying Graphs: Broadcasting under Unstructured Mobility

Abstract : 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.
Type de document :
Communication dans un congrès
Cristian S. Calude; Vladimiro Sassone. 6th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science (TCS) / Held as Part of World Computer Congress (WCC), Sep 2010, Brisbane, Australia. Springer, IFIP Advances in Information and Communication Technology, AICT-323, pp.111-124, 2010, Theoretical Computer Science. 〈10.1007/978-3-642-15240-5_9〉
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01054440
Contributeur : Hal Ifip <>
Soumis le : mercredi 6 août 2014 - 16:24:37
Dernière modification le : jeudi 29 novembre 2018 - 16:02:57
Document(s) archivé(s) le : mercredi 26 novembre 2014 - 00:55:36

Fichier

03230111.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Arnaud Casteigts, Paola Flocchini, Bernard Mans, Nicola Santoro. Deterministic Computations in Time-Varying Graphs: Broadcasting under Unstructured Mobility. Cristian S. Calude; Vladimiro Sassone. 6th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science (TCS) / Held as Part of World Computer Congress (WCC), Sep 2010, Brisbane, Australia. Springer, IFIP Advances in Information and Communication Technology, AICT-323, pp.111-124, 2010, Theoretical Computer Science. 〈10.1007/978-3-642-15240-5_9〉. 〈hal-01054440〉

Partager

Métriques

Consultations de la notice

108

Téléchargements de fichiers

85