Paper detail

Collection and Dissemination of Data on Time-Varying Digraphs

Given a network of fixed size $n$ and an initial distribution of data, we derive sufficient connectivity conditions on a sequence of time-varying digraphs for (a) data collection and (b) data dissemination, within at most $(n-1)$ iterations. The former is shown to enable distributed computation of the network size $n$, while the latter does not. Knowledge of $n$ subsequently enables each node to acknowledge the earliest time point at which they can cease communication, specifically we find the number of redundant signals can be truncated at the finite time $n$. Using a probabilistic approach, we obtain tight upper and lower bounds for the expected time until the $\textit{last}$ node obtains the entire collection of data, in other words complete data dissemination. Similarly tight upper and lower bounds are also found for the expected time until the $\textit{first}$ node obtains the entire collection of data. Interestingly, these bounds are both $Θ(\text{log}_2(n))$ and in fact differ by only two iterations. Numerical results are explored and verify each result.