Privacy Preserving Distributed Summation in a Connected Graph

Most decentralized algorithms for multi-agent systems used in control, signal processing and machine learning for example, are designed to fit the problem where agents can only communicate with immediate neighbors in the network. For instance, decentralized and distributed optimization algorithms are based on the fact that every agent in a network will be able to influence every other agent in the network even if each agent only communicates with its immediate neighbors (given that the network is connected). That is, a distributed optimization problem can be solved in a decentralized manner by letting the agents exchange messages with their neighbors iteratively. In many algorithms that solve this kind of problem, agents in the network does not need individual values from their neighbors, rather they need a function of the values from its neighbors. This observation makes it interesting to consider privacy preservation in such algorithms. By privacy preservation, we mean that raw data from individual agents will not be exposed at any time during calculations.

This paper is concerned with decentralized algorithms, where each agent must learn the sum of its neighbors values, and we propose a privacy preserving method to compute this sum. Employing this method in corresponding decentralized algorithms makes the whole algorithm privacy preserving. The only restriction we make on the graph topology of the network is that each agent must have at least two neighbors. We provide simulations of the proposed method, which illustrates the scalability of it.