| This thesis analyzes large deviations performance of linear consensus-based algorithms for distributed inference (detection and estimation). With consensus-based algorithms, agents communicate locally with their neighbors, through intermittently failing links, and assimilate their streaming observations in real time. While existing work usually focuses on asymptotic consistency and asymptotic normality measures, we establish the large deviations rates, thus giving parallels of the classical Chernoff lemma and Cramer's theorem for distributed systems. Our main contributions are two-fold. (1) We find the large deviation rate J for convergence in probability of products of random stochastic matrices that model the local inter-agent interactions. Our analysis includes a wide range of random stochastic matrix models, including asymmetric matrices and temporal dependencies. Further, for commonly used gossip and link failure models, we show how the rate J can be computed by solving a min-cut problem. (2) We find tight upper and lower bounds on the large deviations performance of linear consensus-based inference, as well as the full large deviation principle when the underlying network is regular. When translated into distributed detection, our results reveal a phase transition behavior with respect to the network connectivity, measured by J. If J is above a threshold, each agent is an asymptotically optimal detector with the error exponent equal to the total Chernoff information of the network; if below the threshold, we characterize what fraction of the total Chernoff information can be achieved at each agent. When translated into distributed estimation, our results show that distributed system's performance relative to the performance of an ideal, centralized system, is a highly nonlinear function of the required estimation accuracy. Finally, our methodology develops new tools that are of general interest in the large deviations theory and products of random matrices. |
