Deterministic computations in time-varying graphs

Broadcasting under unstructured mobility

Arnaud Casteigts, Paola Flocchini, Bernard Mans, Nicola Santoro

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

21 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationTheoretical Computer Science
Subtitle of host publication6th IFIP TC 1/WG 2.2 International Conference TCS 2010, Held as Part of WCC 2010 Brisbane, Australia, September 20-23, 2010, Proceedings
EditorsCristian S. Calude, Vladimiro Sassone
Place of PublicationBerlin; Heidelberg
PublisherSpringer, Springer Nature
Pages111-124
Number of pages14
ISBN (Print)3642152392, 9783642152399
DOIs
Publication statusPublished - 2010
Event6th 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 - Brisbane, QLD, Australia
Duration: 20 Sep 201023 Sep 2010

Publication series

NameIFIP Advances in Information and Communication Technology
Volume323
ISSN (Print)1868-4238

Other

Other6th 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
CountryAustralia
CityBrisbane, QLD
Period20/09/1023/09/10

Fingerprint Dive into the research topics of 'Deterministic computations in time-varying graphs: Broadcasting under unstructured mobility'. Together they form a unique fingerprint.

  • Cite this

    Casteigts, A., Flocchini, P., Mans, B., & Santoro, N. (2010). Deterministic computations in time-varying graphs: Broadcasting under unstructured mobility. In C. S. Calude, & V. Sassone (Eds.), Theoretical Computer Science: 6th IFIP TC 1/WG 2.2 International Conference TCS 2010, Held as Part of WCC 2010 Brisbane, Australia, September 20-23, 2010, Proceedings (pp. 111-124). (IFIP Advances in Information and Communication Technology; Vol. 323). Berlin; Heidelberg: Springer, Springer Nature. https://doi.org/10.1007/978-3-642-15240-5_9