Gossip Algorithms that Preserve Privacy for Distributed Computation Part I: The Algorithms and Convergence Conditions

Gossip protocols play an important role in disseminating information and solving global tasks over networks in a distributed fashion. In this paper, we propose gossip algorithms that preserve the sum of network states (and therefore the average), while fully protecting node privacy even against eaves-droppers possessing the entire information flow and network knowledge. At each time step, a node is selected to interact with one of its neighbors via deterministic or random gossiping. The selected node generates a random number to replace its current state, and sends to the neighbor the difference between the current state and the random number. On receiving the data from the selected node, the neighbor sets its new state as the sum of its current state and the difference. The algorithms can be used as a simple encryption step in distributed optimization and computation algorithms. In this Part I, we study the output statistics of the proposed algorithms with deterministic edge sequence selection, in addition to the convergence limits and encryption time of their randomized version.