Privacy Preserving Maximum Consensus

Maximum consensus is useful in many applications such as leader selection and time synchronization, and it is advantageous for its decentralization and finite time convergence. However, without preservation mechanisms for maximum consensus, nodes´ initial states and especially the identity of the node with the maximum initial state will be disclosed, which is undesirable in some application scenarios. To preserve the privacy of maximum consensus while maintaining its advantages, we propose a Privacy Preserving Maximum Consensus (PPMC) algorithm, where all nodes independently generate and transmit random numbers before sending out their initial states. We prove that PPMC converges in finite time. Meanwhile, explicit formulas are given to characterize the probability that the maximum state owner´s identity is inferred by its neighbors. Extensive simulations are conducted to demonstrate the effectiveness of the proposed algorithm.