Differentially Private Average Consensus: Obstructions, Trade-Offs, and Optimal Algorithm Design
Erfan Nozari Pavankumar Tallapragada Jorge Cortés Department of Mechanical and Aerospace Engineering, University of California, San Diego,
Abstract
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
中文速览
多智能体网络中，各节点希望通过与邻居交换信息来协同计算所有人初始值的均值，但这一过程会暴露个体隐私。针对这一矛盾，研究者首先从理论上严格证明了一个不可能性定理：只要算法满足差分隐私（differential privacy）保证，就无法在任何收敛意义上保证智能体状态精确收敛到真实均值。在此基础上，研究者设计了一种新型差分隐私拉普拉斯共识（differentially private Laplacian consensus）算法——让每个智能体在状态更新和消息传递中叠加指数衰减的拉普拉斯噪声，并证明该算法几乎必然（almost surely）收敛到初始均值的无偏估计，同时给出了指数均方收敛速率的精确刻画。进一步的优化分析揭示，在给定隐私预算下，将拉普拉斯噪声一次性注入初始状态（one-shot perturbation）是使收敛点方差最小的最优策略，这为分布式系统中隐私与精度之间的基本权衡提供了清晰的理论边界和可操作的算法设计方案。
原文 arXiv:1512.09039;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1512.09039v3