Paper 2
Invariant Properties and Bounds on a Finite Time Consensus AlgorithmAuthors: Michel Toulouse, Bùi Quang Minh, Quang Tran Minh |
AbstractFinite time consensus algorithms compute consensus values exactly and in a finite number of steps, contrasting with asymptotic consensus algorithms. In the literature, there exists few approaches deriving finite time convergence for discrete consensus algorithms. In this paper we focus on an analysis of finite time convergence based on the observability matrix for consensus networks. We introduce analytical results extending the applicability of network observability theory to consensus and other distributed algorithms. New analytical bounds on the number of steps to compute consensus are provided as well as counterexamples which are disproving a conjecture on the minimum of steps to compute consensus. A polynomial time algorithm is described to calculate empirically the exact number of steps to compute consensus values. We have implemented a consensus-based network intrusion detection system based on the observability matrix approach of consensus networks. This implementation validates empirically our analytical results. We also compare the performance of the finite time consensus with an implementation of the same intrusion detection system using asymptotic consensus. Although the finite time algorithm provides exact solutions, tests show that it needs less iterations to obtain a consensus solution. Keywords: Consensus algorithms, Finite time convergence, Observability theory, Distributed computing. |