A Privacy-Preserving Asynchronous Averaging Algorithm based on State Decomposition

Abstract

Average consensus algorithms are used in many distributed systems such as distributed optimization, sensor fusion and the control of dynamic systems. Consensus algorithms converge through an explicit exchange of state variables. In some cases, however, the state variables are confidential. In this paper, a privacy-preserving asynchronous distributed average consensus method is proposed, which decomposes the initial values into two states; alpha states and beta states. These states are initialized such that their sum is twice the initial value. The alpha states are used to communicate with the other nodes, while the beta states are used internally. Although beta states are not shared, they are used in the update of the alpha states. Unlike differential privacy based methods, the proposed algorithm achieves the exact average consensus, while providing privacy to the initial values. Compared to the synchronous state decomposition algorithm, the convergence rate is improved without any privacy compromise. As the variances of coupling weights become infinitely large, the semi-honest adversary does not have any range to estimate the initial value of the nodes given that there is at least one coupling weight hidden from the adversary.