[Back]

O. Sluciak:
"Convergence Analysis of Distributed Consensus Algorithms";
Supervisor, Reviewer: M. Rupp, W. Gansterer; E389, 2013; oral examination: 06-27-2013.

Inspired by new emerging technologies and networks of devices with high collective computational
power, I focus my work on the problematics of distributed algorithms. 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.
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. 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.
The work can be divided into two main parts.
First, I focus on the convergence analysis of the distributed consensus algorithms.
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. 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.
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.
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.

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. 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.
Zum einen konzentriere ich mich auf die Konvergenzanalyse verteilter Konsens Algorithmen.
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.
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.
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.

http://publik.tuwien.ac.at/files/PubDat_224903.pdf

Project Head Markus Rupp:
Signal and Information Processing in Science and Engineering II: Theory and Implementation of Distributed Algorithms