Distributed Cycle Detection and Removal
Ημερομηνία
2018ISSN
2325-5870Source
IEEE Transactions on Control of Network SystemsVolume
5Issue
1Pages
194-204Google Scholar check
Metadata
Εμφάνιση πλήρους εγγραφήςΕπιτομή
In this paper, we provide distributed algorithms to detect and remove cycles in a directed relational graph by exploiting the underlying undirected communication graph the relational graph models a relation among the agents, e.g., a pairwise ordering, while the communication graph captures how information can be shared among them. Specifically, we provide a synchronous distributed algorithm to detect cycles in the relational graph, by exploiting the fact that nodes with zero in-degree or zero outdegree can not be part of a cycle, and can be iteratively removed without creating new loops in the relational topology. The proposed algorithm considerably improves transmission efficiency (the number of messages and bandwidth required) compared to the state of the art. We demonstrate that the problem of making the relational graph acyclic by swapping the orientation of a minimum number of edges is NP-Complete and APX-Hard for this reason, we develop an efficient, yet suboptimal, distributed algorithm to remove the cycles by swapping the direction of some of the links. The methodology provided in this paper finds application in several distributed control problems where the agents must be interconnected via a directed acyclic graph, such as cluster consensus, formation control or multiple leader election. Extensive numerical analysis emphasizes the effectiveness of the proposed solution with respect to the state of the art.