The role of quadratic Lyapunov functions in averaging based consensus algorithms

Abstract

Ortak bir değere ulaşma olarak tanımlanan dağıtık onaylaşım, son yıllarda populer bir araştırma konusudur. Ortalama hesaplama tabanlı dağıtık onaylaşım algoritmaları genellikle dağıtık kestirim, kaplam kontrolü, dağıtık görev tahsisi, saat eşzamanlama gibi bircok alanda uygulanr. Bu tezde, ortalama hesaplama tabanlı dağıtık onaylaşım algoritmalarının analizinde karesel Lyapunov fonksiyonlarının oluşumu ve rolu incelenmistir. Öncelikle, bir kapsama ağacı içeren ağlarda onaylaşım algoritmasının ayrık zamanlı anahtar sistem modeli oluşturulmuş ve bu durumda algoritmanın yakınsayacağının bilinmesine rağmen, ortak karesel Lyapunov fonksiyonunun beş ya da daha fazla düğüm iceren ağlarda olmadığı gösterilmiştir. Daha sonra bir fonksiyonun stokastik sistem matrisli bir doğrusal sistem için Lyapunov fonksiyonu olup olmadığını belirlemek üzere yeni bir yaklaşım sunulmuştur ve söz konusu sistemler için karesel Lyapunov fonksiyonlarından özel bir türün karesel Lyapunov fonksiyonu olmasını döngelik katsayısıyla ilişkilendiren yeter koşul belirlenmiştir. Bu sonuçlar kullanılarak, ortalama hesaplama tabanlı algoritmaların matrislerinin çarpımlarıyla tanımlanan sistemler için ortak bir karesel Lyapunov fonksiyonu türetilmistir. Önerilen yöntem, kapsama ağacı içeren ağlarda ortalama hesaplama tabanlı onaylaşım algoritmalarının yakınsamasını ispatlamak için alternatif bir yol sağlamaktadır.

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 first 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 sufficient condition that relates the coefficient 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 dened by products of averagingalgorithm matrices, which provides an alternative way of proving convergence ofaveraging based distributed consensus algorithms in networks having a spanning tree.