  We find large deviations rates for consensus-based distributed inference for
directed networks. When the topology is deterministic, we establish the large
deviations principle and find exactly the corresponding rate function, equal at
all nodes. We show that the dependence of the rate function on the stochastic
weight matrix associated with the network is fully captured by its left
eigenvector corresponding to the unit eigenvalue. Further, when the sensors'
observations are Gaussian, the rate function admits a closed form expression.
Motivated by these observations, we formulate the optimal network design
problem of finding the left eigenvector which achieves the highest value of the
rate function, for a given target accuracy. This eigenvector therefore
minimizes the time that the inference algorithm needs to reach the desired
accuracy. For Gaussian observations, we show that the network design problem
can be formulated as a semidefinite (convex) program, and hence can be solved
efficiently. When observations are identically distributed across agents, the
system exhibits an interesting property: the graph of the rate function always
lies between the graphs of the rate function of an isolated node and the rate
function of a fusion center that has access to all observations. We prove that
this fundamental property holds even when the topology and the associated
system matrices change randomly over time, with arbitrary distribution. Due to
generality of its assumptions, the latter result requires more subtle
techniques than the standard large deviations tools, contributing to the
general theory of large deviations.
