On the time complexity of information dissemination via linear iterative strategies

Abstract

Given an arbitrary network of interconnected nodes, each with an initial value, we study the number of time-steps 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. © 2010 AACC.