Distributed Algorithms for Verifying and Ensuring Strong Connectivity of Directed Networks

: Atman, Made Widhi Surya; Gusrialdi, Azwirman

Publisher: IEEE

: 2021

: IEEE Conference on Decision and Control

: 2021 60TH IEEE CONFERENCE ON DECISION AND CONTROL (CDC)

: Proceedings of the IEEE Conference on Decision and Control

: 2021-December

: 4798

: 4803

: 25762370 07431546

: 2576-2370

DOI: https://doi.org/10.1109/CDC45484.2021.9683729

: https://doi.org/10.1109/cdc45484.2021.9683729

This paper considers the problem of distributively verifying and ensuring strong connectivity of directed networks. Strong connectivity of a directed graph associated with the communication network topology is crucial in ensuring the convergence of many distributed algorithms. Specifically, inspired by maximum consensus algorithm, we first propose a distributed algorithm that enables nodes in a networked system to verify strong connectivity of a directed graph. Then, given an arbitrary weakly connected directed graph, we develop a distributed algorithm to augment additional links to ensure the directed graph's strong connectivity. Both algorithms are implemented without requiring information of the overall network topology and are scalable (linearly with the number of nodes) as they only require finite storage and converge in finite number of steps. Finally, the proposed distributed algorithms are demonstrated via several examples.