On the time complexity of information dissemination via linear iterative strategies
Date
2010ISBN
978-1-4244-7426-4Source
Proceedings of the 2010 American Control Conference, ACC 2010Proceedings of the 2010 American Control Conference, ACC 2010
Pages
6789-6794Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
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.