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:Article
Entered by:
TitleCausality, Influence, and Computation in Possibly Disconnected Synchronous Dynamic Networks
Bibtex cite IDRACTI-RU1-2014-6
Journal Journal of Parallel and Distributed Computing (JPDC)
Year published 2014
Month January
Volume 74
Number 1
Pages 2016-2026
DOI 10.1016/j.jpdc.2013.07.007
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 distributed computing systems that are possibly disconnected at every instant. We focus on a synchronous message-passing communication model with broadcast and bidirectional links. Our network dynamicity assumption is a worst-case dynamicity controlled by an adversary scheduler, which has received much attention recently. We replace the usual (in worst-case dynamic networks) assumption that the network is connected at every instant by minimal temporal connectivity conditions. Our conditions only require that another causal influence occurs within every time window of some given length. Based on this basic idea, we define several novel metrics for capturing the speed of information spreading in a dynamic network. We present several results that correlate these metrics. Moreover, we investigate termination criteria in networks in which an upper bound on any of these metrics is known. We exploit our termination criteria to provide efficient (and optimal in some cases) protocols that solve the fundamental counting and all-to-all token dissemination (or gossip) problems.
Michail, Othon
Chatzigiannakis, Ioannis
Spirakis, Paul
MCS13-JPDC.pdf (main file)
Publication ID984