Brief announcement: Waiting in dynamic networks

Arnaud Casteigts, Paola Flocchini, Emmanuel Godard, Nicola Santoro, Masafumi Yamashita

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

1 Citation (Scopus)


We consider infrastructure-less highly dynamic networks, where connectivity does not necessarily hold, and the network may actually be disconnected at every time instant. These networks are naturally modeled as time-varying graphs. Clearly the task of designing protocols for these networks is less difficult if the environment allows waiting (i.e., it provides the nodes with store-carry-forward-like mechanisms such as local buffering) than if waiting is not feasible. We provide a quantitative corroboration of this fact in terms of the expressivity of the corresponding time-varying graph; that is in terms of the language generated by the feasible journeys in the graph. We prove that the set of languages L nowait when no waiting is allowed contains all computable languages. On the other end, we prove that L wait is just the family of regular languages. This gap is a measure of the computational power of waiting. We also study bounded waiting; that is when waiting is allowed at a node only for at most d time units. We prove the negative result that L wait[d] = L nowait.

Original languageEnglish
Title of host publicationPODC'12 - Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing
Number of pages2
Publication statusPublished - 2012
Event2012 ACM Symposium on Principles of Distributed Computing, PODC'12 - Madeira, Portugal
Duration: Jul 16 2012Jul 18 2012

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing


Other2012 ACM Symposium on Principles of Distributed Computing, PODC'12

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Brief announcement: Waiting in dynamic networks'. Together they form a unique fingerprint.

Cite this