Linear iterative strategies for information dissemination and processing in distributed systems.

摘要

Given an arbitrary network of interconnected nodes, each with some initial value, we develop and analyze distributed strategies that enable a subset of the nodes to calculate any function of the initial values of the nodes. Specifically, we focus on linear iterative strategies where each node updates its value to be a weighted average of its previous value and those of its neighbors over the course of several time-steps.;We start by showing that in networks with time-invariant topologies, choosing the weights for the linear iteration randomly from a field of sufficiently large size will (with high probability) allow every node to calculate any arbitrary function of the initial node values after running the linear iteration for a finite number of time-steps. We show that the number of time-steps required can be determined from the structure of the network topology, and in fact, may be minimal over all possible strategies for information dissemination.;We then apply our results to calculate linear functions in networks with real-valued transmissions and updates, where communications between nodes are corrupted by additive noise. We show that by using a linear iterative strategy with almost any set of real-valued weights for a finite number of time-steps, any node in the network will be able to calculate an unbiased estimate of any linear function by taking a linear combination of the values that it sees over the course of the linear iteration. Furthermore, for a given set of weights, we describe how to choose this linear combination to minimize the variance of the unbiased estimate calculated by each node.;Next, we consider the problem of distributed function calculation in the presence of faulty or malicious agents, and we study the susceptibility of linear iterative strategies to misbehavior by some nodes in the network; specifically, we consider a node to be malicious if it updates its value arbitrarily at each time-step, instead of following the predefined linear iterative strategy. Our analysis is constructive, in that it provides specific attacking and decoding strategies which the malicious and non-malicious nodes can use to achieve their objectives.;We then utilize our framework to study the topic of network coding in the presence of malicious nodes. We consider the wireless broadcast communication model, where each transmission by a node is received by all of its neighbors in the network. We use linear network coding to disseminate information, whereby at each time-step, each node transmits a value that is a linear combination of the most recent transmissions of its neighbors. We allow for the possibility that the malicious nodes conspiratorially transmit arbitrary values in an effort to disrupt the network, and we show that linear network codes in the presence of such attackers can be conveniently modeled as a linear dynamical system with unknown inputs.;Finally, we generalize existing theory on structured linear systems to encompass finite fields, and apply these results at various points in the thesis. Specifically, we show that certain structural properties of linear systems remain valid with high probability if the parameters are chosen from a finite field of sufficiently large size. In the process, we obtain new insights into structural properties of linear systems (such as an improved upper bound on the observability index in terms of the topology of the graph associated with the system). (Abstract shortened by UMI.)