A4 Refereed article in a conference publication
Distributed Algorithms for Verifying and Ensuring Strong Connectivity of Directed Networks
Authors: Atman, Made Widhi Surya; Gusrialdi, Azwirman
Publisher: IEEE
Publication year: 2021
Journal: IEEE Conference on Decision and Control
Book title : 2021 60TH IEEE CONFERENCE ON DECISION AND CONTROL (CDC)
Journal name in source: Proceedings of the IEEE Conference on Decision and Control
Volume: 2021-December
First page : 4798
Last page: 4803
ISSN: 25762370 07431546
eISSN: 2576-2370
DOI: https://doi.org/10.1109/CDC45484.2021.9683729
Web address : https://doi.org/10.1109/cdc45484.2021.9683729
Abstract
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.
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.
UTU Research Portal