The role of quadratic lyapunov functions in averaging based consensus algorithms

Abstract

Distributed consensus, that is described as the notion of achieving a common value by local information exchange, has been a popular research subject in recent years. Averaging based distributed consensus algorithms are applied in many areas such as distributed estimation, coverage control, distributed task assignment and clock synchronization. The focus of this thesis is to study the existence and the role of common quadratic Lyapunov functions in convergence analysis of averaging based distributed consensus algorithms. We rst consider a discrete-time switched system model of the consensus algorithm where the network graph has a spanning tree. Although the algorithm is known to converge in this case, we show that there exists no common quadratic Lyapunov function for networks with ve or more nodes. Subsequently, an approach is presented to determine whether a quadratic function is a Lyapunov function for a linear system with a stochastic system matrix. We also provide a su cient condition that relates the coe cient of ergodicity to the existence of a special type of quadratic Lyapunov function for such systems. Based on these results, we generate a common quadratic Lyapunov function for systems de ned by products of averaging algorithm matrices, which provides an alternative way of proving convergence of averaging based distributed consensus algorithms in networks having a spanning tree.