On the Time Complexity of Information Dissemination via Linear Iterative Strategies

Given an arbitrary network of interconnected nodes, each with an initial value, we study the number of timesteps required for some (or all) of the nodes to gather all of the initial values via a linear iterative strategy. At each time-step in this strategy, each node in the network transmits a weighted linear combination of its previous transmission and the most recent transmissions of its neighbors. We show that for almost any choice of real-valued weights in the linear iteration (i.e., for all but a set of measure zero), the number of time-steps required for any node to accumulate all of the initial values is upper-bounded by the size of the largest tree in a certain subgraph of the network; we use this fact to show that the linear iterative strategy is time-optimal for information dissemination in certain networks. In the process of deriving our results, we also obtain a characterization of the observability index for a class of linear structured systems.