Distributed Identification of the Most Critical Node for Average Consensus

In communication networks, cyber attacks, such as resource depleting attacks, can cause failure of nodes and can damage or significantly slow down the convergence of the average consensus algorithm. In particular, if the network topology information is learned, an intelligent adversary can attack the most critical node in the sense that deactivating it causes the largest destruction, among all the network nodes, to the convergence speed of the average consensus algorithm. Although a centralized method can undoubtedly identify such a critical node, it requires global information and is computationally intensive and, hence, is not scalable. In this paper, we aim to identify the most critical node in a distributed manner. The network algebraic connectivity is used to assess the destruction caused by node removal and further the importance of a node. We propose three low-complexity algorithms to estimate the descent of the algebraic connectivity due to node removal and theoretically analyze the corresponding estimation errors. Based on these estimation algorithms, distributed power iteration, and maximum-consensus, we propose a fully distributed algorithm for the nodes to iteratively find the most critical one. Extensive simulation results demonstrate the effectiveness of the proposed methods.