Differentially private average consensus: Obstructions, trade-offs, and optimal algorithm design

By Erfan Nozari, Pavankumar Tallapragada, Jorge Cortés. at - Automatisierungstechnik, 2015

323 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/ae126a77e5d63b8aa0efdd1c8132029451c58c7d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Mohammad Pirani
2. Karl Henrik Johansson
3. Aranya Chakrabortty
4. Nicolas Loizou
5. Anuradha M. Annaswamy
6. Seyed Mehran Dibaji
7. David Bezalel Flamholz
8. Peter Richtárik

In Computer Networks and Communications

1. Karl Henrik Johansson
2. Nicolas Loizou
3. Peter Richtárik
4. Gang Feng
5. Qing-Long Han

In Electrical and Electronic Engineering

1. Karl Henrik Johansson
2. Nicolas Loizou
3. Anuradha M. Annaswamy

Citations in the corpus

• Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “A different approach with a more stricter goal is the design of privacy-preserving average consensus protocols that guarantee protection of the initial values ci of the nodes [142, 123, 124].”
• A systems and control perspective of CPS security (2019, methodology): “Disclosure attacks refer to any intrusions that include eavesdropping [12].”