Causality, influence, and computation in possibly disconnected synchronous dynamic networks

Michail, Othon ORCID: 0000-0002-6234-3960, Chatzigiannakis, Ioannis and Spirakis, Paul G ORCID: 0000-0001-5396-3749
(2014) Causality, influence, and computation in possibly disconnected synchronous dynamic networks. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 74 (01). pp. 2016-2026.

[img] Text
jpdc14.pdf - Author Accepted Manuscript

Download (614kB)


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.

Item Type: Article
Additional Information: 14 pages, 1 figure
Uncontrolled Keywords: Dynamic graph, Mobile computing, Worst-case dynamicity, Adversarial schedule, Temporal connectivity, Termination, Counting, Information dissemination, Optimal protocol
Depositing User: Symplectic Admin
Date Deposited: 20 Sep 2016 07:32
Last Modified: 19 Jan 2023 07:29
DOI: 10.1016/j.jpdc.2013.07.007
Related URLs: