Differentially private iterative synchronous consensus

By Zhenqi Huang, Sayan Mitra, Geir E. Dullerud. 2012

288 citations recorded by the source corpus.

The iterative consensus problem requires a set of processes or agents with different initial values, to interact and update their states to eventually converge to a common value. Protocols solving iterative consensus serve as building blocks in a variety of systems where distributed coordination is required for load balancing, data aggregation, sensor fusion, filtering, and synchronization. In this paper, we introduce the private iterative consensus problem where agents are required to converge while protecting the privacy of their initial values from honest but curious adversaries. Protecting the initial states, in many applications, suffice to protect all subsequent states of the individual participants. We adapt the notion of differential privacy in this setting of iterative computation. Next, we present (i) a server-based and (ii) a completely distributed randomized mechanism for solving differentially private iterative consensus with adversaries who can observe the messages as well as the internal states of the server and a subset of the clients. Our analysis establishes the tradeoff between privacy and the accuracy: for given ε, b >0, the ε-differentially private mechanism for N agents, is guaranteed to convergence to a value within O(⁄1/ε √bN) of the average of the initial values, with probability at least (1-b).

Subfields: Artificial Intelligence, Computer Networks and Communications

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

In Computer Networks and Communications

Citations in the corpus

Differentially Private Distributed Optimization (2014, methodology): “Thus, unlike the standard algorithms and our previous algorithm for private consensus [8], our algorithm for PDOP uses step sizes that sum to a finite quantity.”
Differentially Private Filtering (2012, background): “A differentially private version of the iterative averaging algorithm for consensus is considered in [16].”
Privacy preserving average consensus (2014, background): “[16] propose a differentially private consensus algorithm, where an independent and exponentially decaying Laplacian noise process is added to the consensus computation.”
Hiding in the Crowd: A Massively Distributed Algorithm for Private Averaging with Malicious Adversaries (2018, background): “For an adversary able to observe all communications in the network, Huang et al. (2012) proposed an (cid:15) -diﬀerentially private protocol where users add exponentially decaying Laplacian noise to their value.”
Entropy-minimizing mechanism for differential privacy of discrete-time linear feedback systems (2014, background): “In dynamic systems, this hinders efficient communications between system components, especially in multi-agent systems [4], [5].”
Differentially private average consensus: Obstructions, trade-offs, and optimal algorithm design (2015, methodology): “As we show later, this particular choice results in an unbiased convergence point, while in general the expected value of the convergence point of the algorithm in Huang et al. (2012) depends on the graph structure andmay not be the true average. Furthermore, this algorithm is only shown to exhibit ”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “In [86], the concept of differential privacy [47] is used to protect the output value c̄ computed by all nodes.”
Secure and Privacy-Preserving Consensus (2017, methodology): “tate, as depicted in Fig. 9. On the contrary, such external eavesdropper gains no information from our protocol where transmitted messages are encrypted inherently. 3) Comparison with the approach in [11]: We next show the vulnerability of the approach in [11] to an external eavesdropper. We built a”
The optimal mechanism in differential privacy (2012, unknown): “, [10], [11], [12], [13], [14], [5], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30], [31], [32], [33], [34], [35], [36], [37], [38], [39], [40], [41], [42], [43], [44], [45], [46].”