Finite-Time Distributed Algorithms for Verifying and Ensuring Strong Connectivity of Directed Networks

Abstract

The strong connectivity of a directed graph associated with the communication network topology is crucial in ensuring the convergence of many distributed estimation/control/optimization algorithms. However, the assumption on the network's strong connectivity may not always be satisfied in practice. In addition, information on the overall network topology is often not available, e.g., due to privacy concerns or geographical constraints which calls for a distributed algorithm. This paper aims to fill a crucial gap in the literature due to the absence of a fully distributed algorithm to verify and ensure in finite-time the strong connectivity of a directed network. Specifically, inspired by the maximum consensus algorithm we propose distributed algorithms that enable individual node in a networked system to verify the strong connectivity of a directed graph and further, if necessary, augment a minimum number of new links to ensure the directed graph's strong connectivity. The proposed distributed algorithms are implemented without requiring information of the overall network topology and are scalable as they only require finite storage and converge in finite number of steps. Furthermore, the algorithms also preserve the privacy in terms of the overall network's topology. Finally, the proposed distributed algorithms are demonstrated and evaluated via numerical results.