Collection and Dissemination of Data on Time-Varying Digraphs
This provides foundational theoretical guarantees for distributed data aggregation in dynamic networks, enabling nodes to determine when to cease communication.
The paper derives sufficient connectivity conditions for data collection and dissemination in time-varying digraphs, achieving complete dissemination within Θ(log₂(n)) expected time, with tight upper and lower bounds differing by only two iterations.
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.