research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleCausality, Influence, and Computation in Possibly Disconnected Synchronous Dynamic Networks
Bibtex cite IDRACTI-RU1-2012-26
Booktitle 16th International Conference On Principles Of DIstributed Systems (OPODIS)
Series Lecture Notes in Computer Science
Year published 2012
Volume 7702
Pages 269-283
Publisher Springer-Verlag Berlin Heidelberg
Location Rome, Italy
DOI 10.1007/978-3-642-35476-2_19
Keywords dynamic graph,mobile computing,worst-case dynamicity,adversarial schedule,temporal connectivity,termination,counting,information dissemination,optimal protocol
In this work, we study the propagation of influence and computation in dynamic networks that are possibly disconnected at every instant. We focus on a synchronous message passing communication model with broadcast and bidirectional links. To allow for bounded end-to-end communication we propose a set of minimal temporal connectivity conditions that bound from the above the time it takes for information to make progress in the network. We show that even in dynamic networks that are disconnected at every instant information may spread as fast as in networks that are connected at every instant. Further, we investigate termination criteria when the nodes know some upper bound on each of the temporal connectivity conditions. We exploit our termination criteria to provide efficient protocols (optimal in some cases) that solve the fundamental counting and all-to-all token dissemination (or gossip) problems. Finally, we show that any protocol that is correct in instantaneous connectivity networks can be adapted to work in temporally connected networks.
Michail, Othon
Chatzigiannakis, Ioannis
Spirakis, Paul
MCS-OPODIS12.pdf (main file)
Publication ID975