Designing communication networks for discrete-time consensus for performance and privacy guarantees

Discrete-time consensus plays a key role in multi-agent systems and distributed protocols. Unfortunately, due to the self-loop dynamics of the agents (an agent's current state depends only on its own immediately previous state, i.e., one time-step in the past), they often lack privacy guarantees. Therefore, in this paper, we propose a novel design that consists of a network augmentation, where each agent uses the previous iteration values and the newly received ones to increase the privacy guarantees. To formally evaluate the privacy of a network of agents, we define the concept of privacy index, which intuitively measures the minimum number of agents that should work in coalition to recover all the initial states. Moreover, we aim to explore if there is a trade-off between privacy and accuracy (rate of convergence) or if we can increase both. We unveil that, with the proposed method, we can design networks with higher privacy index and faster convergence rates. Remarkably, we further ensure that the network always reaches consensus even when the original network does not. Finally, we illustrate the proposed method with examples and present networks that lead to higher privacy levels and, in the majority of the cases, to faster consensus rates