Source-linked AI summary
Privacy-Preserving Average Consensus via State Decomposition
Yongqiang Wang
TL;DR
Distributed average consensus typically exposes node states, creating privacy risks for sensitive information and vulnerability to wiretapping. The paper decomposes each state into two sub-states, keeping one invisible externally while fixing their mean to the original state. The approach preserves privacy and guarantees accurate, exact average consensus, including against external eavesdroppers.
Problem
Existing average-consensus methods disclose state information to neighbors, while privacy-preserving alternatives can impose computational overhead or trade privacy against consensus accuracy.
Method
Each node decomposes its state into two randomly initialized sub-states whose mean equals the original state; one interacts across nodes and the other remains internal.
Results
The approach guarantees convergence of all sub-states to the average consensus value while protecting initial states against honest-but-curious nodes and external eavesdroppers.
Takeaways & Limitations
Privacy preservation need not compromise accurate average consensus, including when an adversary directly connects to a target node and all its neighbors.
Abstract
from arXiv · showhide
Average consensus underpins key functionalities of distributed systems ranging from distributed information fusion, decision-making, distributed optimization, to load balancing and decentralized control. Existing distributed average consensus algorithms require each node to exchange and disclose state information to its neighbors, which is undesirable in cases where the state is private or contains sensitive information. In this paper, we propose a novel approach that avoids disclosing individual state information in average consensus by letting each node decompose its state into two sub-states. For each node, one of the two sub-states involves in computation and inter-node interactions as if it were the original state, while the other sub-state interacts only with the first sub-state of the same node, being completely invisible to other nodes. The initial values of the two sub-states are chosen randomly but with their mean fixed to the initial value of the original state, which is key to guarantee convergence to the desired consensus value. In direct contrast to differential-privacy based privacy-preserving average-consensus approaches which enable privacy by compromising accuracy in the consensus value, the proposed approach can guarantee convergence to the \emph{exact} desired value without any error. Not only is the proposed approach able to prevent the disclosure of a node's initial state to honest-but-curious neighbors, it can also provide protection against inference by external eavesdroppers able to wiretap communication links. Numerical simulations demonstrate the effectiveness of the approach and its advantages over state-of-the-art counterparts.
I. INTRODUCTION
Average consensus is increasingly used in distributed and cyber-physical applications, but conventional methods disclose node states and expose sensitive information to neighbors and eavesdroppers. Existing privacy solutions can be computationally heavy or trade consensus accuracy for privacy, motivating state decomposition.
- Average consensus supports distributed information fusion, control, signal processing, robotics, social sciences, and optimization.
- Conventional methods exchange explicit state values, potentially exposing private opinions and generation information.
- Communication links can be tapped by eavesdroppers seeking sensitive exchanged information.
- Secure multiparty computation can be too computationally and communicationally heavy for fast-evolving, hard-real-time systems.Yao’s Garbled Circuit is described as having computational latency on the order of seconds, versus millisecond-scale tolerances in cited control applications.
- Cryptography-based protection is difficult to extend to fully decentralized consensus without an aggregator and can increase communication and computation overhead.
- The proposed state-decomposition approach uses two randomly initialized sub-states whose mean equals the original state, preserving privacy while converging to the exact average.One sub-state participates in inter-node interactions, while the other remains invisible outside its node.
A. Average Consensus
The paper models average consensus on a connected, undirected network with possibly time-varying coupling weights. Consensus means all node states converge to the average of their initial values under suitable positive weight bounds.
- The network is represented by a graph with nodes, edges, adjacency weights, and neighbor sets whose coupling weights may vary over time.
- The graph is assumed undirected and connected, with symmetric weights and a path between every pair of nodes.
- Each node i has a scalar state x_i[k], and the results are stated to extend easily to vector states.
- Average consensus requires all states x_i[k] to converge to the average of the initial values.
- Connected networks achieve average consensus when coupling weights satisfy η < a_ij[k] < 1 for all time indices.
B. Attack Model
The paper distinguishes honest-but-curious nodes from external eavesdroppers based on their protocol behavior and access to exchanged information. It analyzes privacy against both adversary types.
- An honest-but-curious adversary follows the protocol but collects received data to learn other nodes’ information.
- An eavesdropper is an external attacker who knows the network topology and wiretaps communication links to access exchanged messages.
- Eavesdroppers can access messages on many channels, while honest-but-curious nodes access only messages destined for them.The honest-but-curious node may nevertheless know its own internal initial state, which an external eavesdropper does not.
III. PRIVACY-PRESERVING APPROACH
The approach decomposes each node’s state into a visible interaction sub-state and an internal sub-state, using private random initialization and weighted coupling to preserve privacy while retaining exact average consensus.
- Decomposition Mechanism: Each node decomposes its state into two sub-states: one participates in inter-node interactions, while the other interacts only within the same node.The second sub-state is invisible to neighboring nodes, although it affects the visible sub-state’s evolution.
- Weight Mechanism: The weight mechanism permits arbitrary symmetric real-valued weights at k = 0, then constrains later nonzero weights to η ≤ aij[k] < 1 and η ≤ ai,αβ[k] < 1.This initialization flexibility supports the privacy analysis while later weights satisfy a uniform lower bound and remain below one.
- Convergence: The decomposition and weight mechanisms preserve convergence to the same average-consensus value as conventional average consensus.Theorem 1 states that all sub-states converge to the average consensus value under the graph and weight assumptions.
- Privacy Guarantees: An honest-but-curious node cannot infer a target node’s initial state with guaranteed accuracy when the target has a noncolluding neighboring node.The result holds under the Decomposition Mechanism and Weight Mechanism.
- Privacy Guarantees: The approach can protect a node even when that node and all its neighbors are directly connected to the honest-but-curious neighbor.This setting is identified as an advantage over the cited privacy-preserving approaches that do not allow it.
- Privacy Guarantees: An eavesdropper cannot infer a node’s initial state with guaranteed accuracy when at least one neighboring interaction weight at k = 0 is inaccessible.Changes in the initial state can be compensated by changes in inaccessible initial coupling weights without changing the eavesdropper’s accessible information.
IV. NUMERICAL COMPARISON WITH EXISTING RESULTS
The numerical comparisons evaluate privacy-preserving consensus methods against eavesdropper inference and accuracy–privacy trade-offs. The proposed approach protects initial states while achieving accurate average consensus.
- The simulations compare the proposed state-decomposition approach with existing privacy-preserving methods,, and [18].
- Accurate average consensus under still allows an eavesdropper to infer node 1’s initial internal state x1[0].
- The approach in likewise guarantees accurate average consensus but does not preserve the privacy of x1[0].
- The proposed approach protects all nodes’ initial values against an eavesdropper while achieving accurate average consensus.
- Differential privacy can prevent accurate state estimation with high noise, but increasing noise also increases consensus error.
V. CONCLUSIONS
The paper concludes that state decomposition provides privacy-preserving average consensus without the accuracy compromise of differential privacy and with stronger adversarial resilience than correlated-noise obfuscation.
- State decomposition enables privacy preservation while guaranteeing accurate average consensus, unlike differential privacy’s privacy–accuracy trade-off.
- The approach improves resilience over correlated-noise obfuscation against adversaries directly connected to a target node and all its neighbors.
- Simulation results confirmed the theoretical predictions.