Autori
Gabriele Oliva, Roberto Setola and Luigi Glielmo
Abstract
Recently, agreement problems among distributed agents under arbitrary interconnection topologies have gained significant attention from the scientific community. The agreement problem has been traditionally solved by iterative protocols where each agent updates its state values based on the states of its neighbors. The average-consensus and the max-consensus problems are of particular interest for our developments in this paper. Though both algorithms are based on a local update rule, they are intrinsically different. Average-consensus is typically achieved asymptotically, while max-consensus is known to converge in finite time (in δ steps, where δ is the diameter of the network). The max-consensus algorithm, moreover, can be implemented in an asynchronous manner, while average-consensus algorithms are typically synchronous. This paper presents recent results in the field of finite-time distributed algorithms, obtained as a cooperation among the University Campus Bio- Medico of Rome (Rome, Italy), University of Sannio (Benevento, Italy) and University of Cyprus (Nicosia, Cyprus). Specifically, we discuss the Finite-Time Average-Consensus by Iterated Max-Consensus (FAIM) Algorithm, which implements a finite- time distributed averaging scheme by means of repeated max-consensus procedures, and has nice computational and robustness properties. In Table I (left table) we compare the main features of FAIM algorithm against the state of the art. Notice that FAIM relies on the assumption that the agents know at least an upper bound δ ̃ on the diameter δ of the network. In order to relax such an assumption, we develop in a distributed finite-time algorithm to let the agents calculate the diameter exactly over a strongly connected graph (directed or undirected). Table I (right table) summarizes the comparison between the proposed approach to calculate the network diameter and the state of the art. We conclude the paper by discussing a distributed algorithm that aims at detecting and removing cycles from a directed network by swapping the orientation of a small fraction of the links. Removing cycles allows to overcome deadlocks and stalls or to resolve logic ambiguities; in the field of distributed control, moreover, an acyclic directed graph is beneficial in several problems including cluster consensus and formation control. Notice that our algorithm aims at preserving as much as possible the original graph structure; however in we prove that swapping a minimum number of links to make the graph acyclic is NP-Complete and APX-Hard. Therefore, the proposed distributed algorithm has no guarantee to swap a minimum number of links.
