A control-theoretic approach to disseminating values and overcoming malicious links in wireless networks

We consider a network in which every node has a value that it wishes to disseminate to all other nodes, despite an attack by an adversary that can falsify messages on a number of the links. To achieve this objective, we study a class of linear iterative strategies in which, at each time-step, each node in the network broadcasts a value to its neighbors that is a linear combination of its previous value and the values received from its neighbors. We take the number of unreliable links to be bounded, in that the number of incoming unreliable links to any node plus the total number of other nodes with incoming unreliable links is no greater than some nonnegative integer f. We show that the linear iterative strategy will be resilient to the unreliable links if and only if the vertex connectivity is at least 2f+1. If this condition is satisfied, we show that almost any choice of weights in the linear combinations will suffice to provide resilience. We further show that each node can identify the exact set of unreliable links that directly enter that node, and can communicate this information to the other nodes via the linear strategy.