to disseminate information from some or all of the nodes in the network
to the other nodes. In this talk, we discuss a linear iterative
strategy for information dissemination, where each node repeatedly
updates its value to be a weighted linear combination of its previous
value and those of its neighbors. We show that this strategy can be
compactly modeled as a linear dynamical system, and use
control-theoretic tools (such as observability theory, structured
system theory, and linear system theory) to characterize its
capabilities.
First, we show that in connected networks with time-invariant
topologies, the linear iterative strategy allows every node to obtain
the values of all other nodes after a finite number of iterations (or
time-steps). The number of time-steps required is determined by the
network topology and, in fact, may be minimal over all possible
strategies for information dissemination.
Next, we demonstrate the ability of the linear iterative strategy to
handle a set of malicious (and possibly coordinated) nodes that update
their values arbitrarily at each time-step. It has been established in
the literature that when there are up to f malicious nodes, the network
connectivity must be at least 2f+1 in order to accurately transmit
information (with any protocol). Surprisingly, we show that the linear
iterative strategy achieves this lower bound. Specifically, after
running the linear iteration for a finite number of time-steps, each
node in the network will have enough information (and a checking
scheme) to correctly determine the values of the other nodes despite
the actions of up to f malicious nodes. We thus establish linear
iterative strategies as viable and effective means of disseminating
information in networks.