Source-linked AI summary
Differentially Private Average Consensus: Obstructions, Trade-Offs, and Optimal Algorithm Design
Erfan Nozari, Pavankumar Tallapragada, Jorge Cortés
TL;DR
The paper asks whether multi-agent average consensus can preserve privacy of initial states while reaching the exact average. It proves exact convergence is impossible under differential privacy, then designs and analyzes a noisy consensus algorithm that converges almost surely to an unbiased estimate, with minimum variance achieved by one-shot initial-state perturbation.
Problem
The paper studies average consensus in networked agents while preserving their initial states against adversaries eavesdropping on all communications.
Method
The paper designs a linear differentially private Laplacian consensus algorithm using noise in agents’ state transitions and message generation, and characterizes its convergence, accuracy, and privacy.
Results
Differential privacy is incompatible with convergence to the exact average even in distribution; the proposed algorithm instead converges almost surely to a consensus value.
Takeaways & Limitations
The most achievable objective is an unbiased consensus value with minimized variance, and the minimum variance is attained by one-shot perturbation of initial states.
Takeaways & Limitations
The parameter analysis restricts the design to P = {(s, c, q) | s ∈(0, 2), c > 0, q ∈(|s −1|, 1)}.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper places differentially private average consensus in privacy-sensitive networked systems and positions its contribution against prior privacy-preserving consensus approaches.
- Privacy preservation is important for networked cyberphysical systems, including social networking, power grids, and smart transportation.
- Average consensus lets neighboring agents agree on the average of their individual values for synchronization, network management, and distributed computation.
- Differential privacy provides a rigorous privacy formulation with resilience to post-processing and side information and independence from the adversary model.
- Prior work used decaying Laplace noise but could produce a convergence-point expectation dependent on network topology rather than the exact average.
- The proposed work targets almost sure convergence, asymptotic unbiasedness, explicit convergence-rate characterization, and independently chosen privacy levels.
- The minimum variance is achieved by one-shot Laplace perturbation of initial states, and simulations illustrate the results.
2 Preliminaries
The preliminaries establish notation for sequences, averages, graphs, probability, convergence, and discrete-time stability used in the paper’s consensus analysis.
- The paper defines Euclidean norms, vector-valued sequences, identity and all-ones matrices, component averages, orthogonal complements, and matrix stability.
- It introduces function-image and inverse-image notation and Borel subsets for measurable analysis.
- Graph Theory: A weighted undirected graph is described through vertices, edges, adjacency, neighbors, degrees, and the Laplacian.
- Graph Theory: The Laplacian is symmetric positive semidefinite, has the all-ones vector in its zero-eigenspace, and has rank characterized by graph connectivity.
- Probability Theory: The paper defines random variables, expectation, variance, Chebyshev’s inequality, and almost sure, mean-square, probabilistic, and distributional convergence.
- Input-to-State Stability of Discrete-Time Systems: Discrete-time input-to-state stability uses class KL and class K bounds, while linear time-invariant systems are input-to-state stable when their state matrix is stable.
3 Problem statement
The problem is to compute the initial-state average over a connected network while protecting those states from adversaries observing all communications.
- A connected group of agents exchanges information over an undirected graph to compute the average of its initial states.
- Privacy is required against eavesdroppers with access to all network communications, including possible communication leakages within the group.
- Each agent has a scalar state and transmits a scalar message derived from its current state and locally generated noise.
- The state-transition function depends only on an agent’s state and messages from itself and its neighbors, while the message function depends on its state and noise.
- Differential privacy compares message-sequence distributions generated from initial states differing in one agent’s value by at most δ.
- Because noise can shift the limit away from the exact average, accuracy requires an unbiased convergence point with a specified probability of lying within a radius r.
4 Obstructions to Exact Differentially Private Average Consensus
The paper proves that differential privacy rules out exact average consensus even under distributional convergence, motivating unbiased approximate consensus instead.
- For any δ, ϵ > 0, no distributed algorithm can both converge in distribution to the exact initial-state average and preserve ϵ-differential privacy.
- The contradiction argument compares two δ-adjacent initial conditions that differ in one agent’s state while requiring both executions to converge to their respective exact averages.
- Continuity makes finite-horizon message and state maps well defined, enabling privacy-event comparisons across the two executions.
- Since distributional convergence is the weakest listed notion, the impossibility extends to stronger convergence notions as well.
- The paper therefore relaxes exact convergence and seeks a convergence variable centered at the true average in expectation.
5 Differentially Private Average Consensus Algorithm
The paper develops a differentially private Laplacian consensus algorithm with exponentially decaying Laplace noise, proving almost-sure convergence to an unbiased estimate and characterizing its privacy, accuracy, and rate trade-offs.
- Algorithm: The proposed dynamics linearly perturb state transitions and message generation with Laplace noise whose scale decays geometrically over time.The step size satisfies h < (dmax)^-1, and the noise scales use agent-specific parameters with si ∈ (0, 2) and qi ∈ (|si − 1|, 1).
- Convergence: The agents’ states converge almost surely, and also in mean square, to a common random limit θ∞.The convergence proof uses the stability of the disagreement dynamics and the almost-sure convergence of the accumulated noise series.
- Convergence: The convergence rate is governed by the slower of the noise-decay rate q and the noise-free consensus rate λ.λ depends on the network topology, whereas q is independent of it.
- Accuracy and Differential Privacy: The limit θ∞ is an unbiased estimate of the initial average with bounded dispersion, while exact (0, 0)-accuracy is impossible under differential privacy.Differential privacy therefore requires a privacy–accuracy trade-off: reducing any privacy level ϵi increases the variance of the convergence point.
- Optimal Noise Selection: For fixed privacy levels and adjacency bound, variance minimization is achieved by one-shot perturbation of the initial states with no later noise injection.This identifies one-shot perturbation as optimal for static average consensus under the paper’s variance objective.
6 Simulations
Simulations on random networks examine convergence variance, settling time, privacy–accuracy behavior, convergence-point distribution, and exponential mean-square convergence rate. The results support the theoretical characterizations and show that one-shot noise is optimal for convergence speed.
- Simulation setup: n = 50 agents were simulated on a random graph with i.i.d. edge weights and initial states distributed as N(50, 100).Each edge weight equals the sum of two i.i.d. Bernoulli random variables with p = 0.1.
- Convergence speed: The fastest convergence occurs at s = 1, showing that one-shot noise is optimal in convergence speed.The settling time counts rounds until reaching tolerance 10^-2; the convergence rate remains µ = λ = 0.84 for s ∈ [0.8, 1.2].
- Convergence speed: Figure 3(a) reports empirical convergence-point variance, while Figure 3(b) reports settling time and supports the theoretical optimality of one-shot perturbation.The variance trend validates Proposition 5.10, and the settling-time trend supports one-shot perturbation for convergence speed.
- Privacy–accuracy trade-off: The privacy–accuracy trade-off exhibits an inversely proportional relationship between accuracy and privacy as ϵ varies over [10^-2, 10^2].Figure 4 compares errors from 25 noise realizations and sample variance over 100 realizations with the theoretical value from Proposition 5.10.
- Convergence-point distribution: The convergence-point distribution has a bell-shaped curve whose sample mean matches the true average, although the distribution is provably non-Gaussian.For a large number of agents, the central limit theorem implies the distribution is very close to Gaussian.
- Convergence rate: The supremum of the empirical convergence-rate curves approaches the theoretical exponential mean-square rate µ as k → ∞.Figure 6 compares empirical estimates with the theoretical value of µ, which equals λ in the reported setting.
7 Conclusions
The paper shows that exact-average convergence is incompatible with differential privacy, and designs a linear consensus algorithm targeting unbiased, minimum-variance agreement. It characterizes the algorithm’s convergence, accuracy, and privacy, with one-shot perturbation emerging as optimal for static average consensus.
- Conclusions: Differential privacy cannot be satisfied when agents’ states weakly converge to the exact average of their initial states.The conclusion identifies unbiased consensus with minimized variance as the strongest supported objective.
- Conclusions: The proposed linear consensus algorithm is designed to produce an unbiased consensus value while minimizing its variance around the true average.The paper characterizes its convergence, accuracy, and differential privacy properties.
- Conclusions: One-shot perturbation is optimal for static average consensus in the sense of minimizing the convergence-point variance.The conclusion connects this result to an earlier information-theoretic entropy interpretation.