  This paper studies the multi-agent average consensus problem under the
requirement of differential privacy of the agents' initial states against an
adversary that has access to all the messages. We first establish that a
differentially private consensus algorithm cannot guarantee convergence of the
agents' states to the exact average in distribution, which in turn implies the
same impossibility for other stronger notions of convergence. This result
motivates our design of a novel differentially private Laplacian consensus
algorithm in which agents linearly perturb their state-transition and
message-generating functions with exponentially decaying Laplace noise. We
prove that our algorithm converges almost surely to an unbiased estimate of the
average of agents' initial states, compute the exponential mean-square rate of
convergence, and formally characterize its differential privacy properties. We
show that the optimal choice of our design parameters (with respect to the
variance of the convergence point around the exact average) corresponds to a
one-shot perturbation of initial states and compare our design with various
counterparts from the literature. Simulations illustrate our results.
