  In this work, we focus on solving a decentralized consensus problem in a
private manner. Specifically, we consider a setting in which a group of nodes,
connected through a network, aim at computing the mean of their local values
without revealing those values to each other. The distributed consensus problem
is a classic problem that has been extensively studied and its convergence
characteristics are well-known. Alas, state-of-the-art consensus methods build
on the idea of exchanging local information with neighboring nodes which leaks
information about the users' local values. We propose an algorithmic framework
that is capable of achieving the convergence limit and rate of classic
consensus algorithms while keeping the users' local values private. The key
idea of our proposed method is to carefully design noisy messages that are
passed from each node to its neighbors such that the consensus algorithm still
converges precisely to the average of local values, while a minimum amount of
information about local values is leaked. We formalize this by precisely
characterizing the mutual information between the private message of a node and
all the messages that another adversary collects over time. We prove that our
method is capable of preserving users' privacy for any network without a
so-called "generalized leaf", and formalize the trade-off between privacy and
convergence time. Unlike many private algorithms, any desired accuracy is
achievable by our method, and the required level of privacy only affects the
convergence time.
