Differentially private iterative synchronous consensus

Zhenqi Huang, Sayan Mitra, Geir Dullerud

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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).

Original languageEnglish (US)
Title of host publicationWPES'12 - Proceedings of the Workshop on Privacy in the Electronic Society
Pages81-89
Number of pages9
DOIs
StatePublished - Nov 22 2012
Event2012 ACM Workshop on Privacy in the Electronic Society, WPES 2012 - Raleigh, NC, United States
Duration: Oct 15 2012Oct 15 2012

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221

Other

Other2012 ACM Workshop on Privacy in the Electronic Society, WPES 2012
CountryUnited States
CityRaleigh, NC
Period10/15/1210/15/12

Keywords

  • Convergence
  • Distributed agreement
  • Iterative consensus
  • Privacy

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Differentially private iterative synchronous consensus'. Together they form a unique fingerprint.

Cite this