Privacy-preserving asymptotic average consensus

Abstract

In this paper, we develop and analyze a distributed privacy-preserving average consensus algorithm that enables all of the components of a distributed system, each with some initial value, to asymptotically reach average consensus on their initial values, without having to reveal the specific value they contribute to the average calculation. We consider a set of components (nodes) that interact via directional communication links (edges) that form a generally directed communication topology (digraph). The proposed protocol can be followed by each node that does not want to reveal its initial value and, under certain conditions on the communication topology that we characterize precisely, all nodes can calculate the average of their initial values while maintaining privacy (i.e., the initial values contributed to the average by the nodes that follow the protocol are not exposed to malicious nodes). We assume that malicious nodes try to identify the initial values of other nodes but do not interfere in the computation in any other way; malicious nodes are assumed to know the predefined linear strategy and topology of the network (but not the actual values used by the nodes that want to preserve their privacy).