Convergence analysis of distributed consensus algorithms

Abstract

Motiviert durch eine Vielzahl neuartiger Technologien und Netzen aus Geräten mit hoher kollektiver Leistungsfähigkeit, konzentriere ich mich in der vorliegenden Arbeit auf die Probleme verteilter Algorithmen.<br />Währende einzelne Teilnehmer dieser Netze nur sehr beschränkte Fähigkeiten aufweisen, wird die hohe Gesamtleistungsfähigkeit durch die Gruppe bestimmt. Üblicherweise verfügen die Geräte über einen eigenen Speicher und eine Prozessoreinheit, und können über ihre Verbindungen Informationen austauschen. Genau genommen konzentriert sich die vorliegende Arbeit auf verteilte Konsens-Algorithmen. Diese Algorithmen erlauben es den Teilnehmern, ihr Verhalten zu koordinieren und in einen gemeinschaftlichen Konsens zu finden. Um ihr Verhalten besser zu verstehen, ist es notwendig, das Konvergenzverhalten der Algorithmen zu analysieren, das heißt, unter welchen Umständen erzielen die Teilnehmer des Netzes einen Konsens und unter welchen nicht. Es ist dabei natürlich anzunehmen, dass die Verbindungen sich über der Zeit verändern, die Teilnehmer asynchron kommunizieren und Einzelne sich möglicherweise auch fehlerhaft verhalten. All diese Fehler können zu ernsthaften Problemen führen und den Konsens beeinflussen. Auch wenn das betrachtete Netz ein Funksensornetz darstellt, ist die Anwendung der verteilten Algorithmen viel breiter, die erzielten Ergebnisse mögen auch auf andere Gebiete übertragbar sein. Die vorliegende Arbeit kann in zwei Abschnitte geteilt werden.<br />Zum einen konzentriere ich mich auf die Konvergenzanalyse verteilter Konsens Algorithmen.<br />Ich beginne mit der Spektralen Graphentheorie und präsentiere klassische Konvergenzergebnisse des Mittelnden Konsens Algorithmus. Als nächstes schlage ich eine allgemeine Methode zur Beschreibung verteilter Algorithmen vor. Mit dieser Methode analysiere ich das Verhalten quantisierter Konsens Algorithmen und leite Grenzen des Quantisierungsfehlers her. Weiters diskutiere ich asynchrone Methoden und leite notwendige Konvergenzbedingungen her. Später gebe ich auch Grenzen der Gewichte solcher asynchronen Algorithmen an. Die asynchronen Algorithmen werden mit Hilfe so-genannter Zustandsmatrizen durchgeführt.<br />Der erste Teil der vorliegenden Arbeit wird mit der Analyse des dynamischen Konsens Algorithmus abgeschlossen, wobei ich neuartige Grenzen zur Konvergenzrate und Konvergenzzeit aufzeige und einen allgemeinen dynamischen Konsens Algorithmus vorschlage.<br />Im zweiten Teil der Arbeit schlage ich zwei neue verteilte Algorithmen vor, die auf den Erkenntnissen des ersten Teils beruhen. Der so-genannte "Likelihood Consensus" Algorithmus erlaubt es, eine Joint-Likelihood Funktion verteilt zu berechnen und damit statistische Inferenz-Methoden (beispielsweise zur Zielnachführung) zu berechnen. Der verteilte Gram-Schmidt Orthogonalisierungs-Algorithmus ist in der Lage aus einer Menge von Vektoren,die auf den Knoten des Netzes verteilt vorliegt, einen Satz orthogonaler Vektoren zu finden. Eine Anwendung hierzu besteht in der Schätzung der Netzgröße wie weiter ausgeführt wird.<br />

Inspired by new emerging technologies and networks of devices with high collective computational power, I focus my work on the problematics of distributed algorithms.<br />While each device runs a relatively simple algorithm with low complexity, the group of interconnected units (agents) determines a behavior of high complexity. Typically, such units have their own memory and processing unit, and are interconnected and capable to exchange information with each other. More specifically, this work is focused on the distributed consensus algorithms.<br />Such algorithms allow the agents to coordinate their behaviour and to distributively find a common agreement (consensus). To understand and analyze their behaviour, it is necessary to analyze the convergence of the consensus algorithm, i.e., under which conditions the algorithm reaches a consensus and under which it does not. Naturally, the communication channel can change and the agents may function asynchronously and improperly. All such errors may lead to severe problems and influence the reached consensus.<br />Note that the target platform of the algorithms presented in this thesis is a wireless sensor network. Nevertheless, since the area of potential applications of distributed algorithms is, in general, much broader, the results of this thesis may be applicable also elsewhere, without significant changes.<br />The work can be divided into two main parts.<br />First, I focus on the convergence analysis of the distributed consensus algorithms.<br />At the beginning, I review the spectral graph theory and classical results on the convergence of the average consensus algorithm. Next, I propose a unifying framework for describing distributed algorithms. In this framework, I analyze the behaviour of a quantized consensus algorithm and show bounds on the quantization error. Furthermore, I discuss the asynchronous consensus algorithms and derive necessary conditions on the convergence.<br />Later on, I derive also bounds on the mixing weights of such asynchronous algorithms. The asynchronous consensus algorithms are analyzed by the concept of so-called "state-transition" matrices.<br />The first part of the thesis is concluded with the analysis of a dynamic consensus algorithm, where I prove novel bounds on the convergence time and rate, and propose a generalized dynamic consensus algorithm.<br />In the second part, I propose two novel distributed algorithms which directly utilize the consensus algorithms discussed in the first part. The "likelihood consensus" algorithm allows to distributively compute a joint-likelihood function, and thus, to distributively solve statistical inference problems (e.g., target tracking). The distributed Gram-Schmidt orthogonalization algorithm, on the other hand, can find a set of orthogonal vectors from general vectors stored at the nodes. As an application of the orthogonalization algorithm, I further propose algorithms for estimating the size of a network.