Verteilte Abstimmungen in großen Netzwerken

Der Schwerpunkt des beantragten Projekts liegt im Entwurf und der Analyse von Algorithmen für verteilte Abstimmungen (voting) in großen Netzwerken. Dazu betrachtet man einen Graphen, in dem jeder Knoten zu Beginn eine gewisse Meinung besitzt. Der überwiegende Teil der bestehenden Literatur beschäftigt sich mit dem sogenannten single-sample-Modell, in dem jeder Knoten zufällig einen Nachbarknoten auswählt und dessen Meinung als eigene Meinung übernimmt. Wir setzten uns in diesem Projekt in erster Linie mit dem 2-sample- Modell auseinander, bei dem jeder Knoten in jedem Schritt zufällig zwei seiner Nachbarn auswählt und, falls deren Meinungen übereinstimmen, diese übernimmt. In Graphen mit guten Expansionseigenschaften zeigt dieses Verfahren gegenüber dem traditionellen (bereits gut analysierten) single-sample-Modell eine bedeutend höhere Effizienz. Wir verfolgen drei Hauptziele: Zu Beginn werden wir das 2-sample-Modell mit zwei Ausgangsmeinungen in regulären Graphen untersuchen. Dazu betrachten wir zunächst Graphen, für die der zweitgrößte Eigenwert der Transitionsmatrix des zugehörigen Random Walks sich nicht an 1 annähert. Erste Analysen zeigen, dass das Abstimmungsverfahren nach O(log n) Schritten endet, wenn < 3/5 ist und das Ausgangsungleichgewicht der beiden Meinungen in O(1) liegt. Um Aussagen über Graphen mit > 3/5 zu bekommen, werden wir den Zusammenhang zwischen der Größe von und der Laufzeit der verteilten Abstimmung analysieren. In einem weiteren Schritt werden wir die gewonnen Ergebnisse auf verteilte Abstimmungen mit k > 2 Ausgangsmeinungen verallgemeinern. Untersuchungen von realen Netzwerken zeigen, dass deren Struktur oftmals eine sogenannte Power-Law- Verteilung zu Grunde liegt. Infolgedessen werden wir das Laufzeitverhalten unserer Algorithmen in nicht- regulären Graphen mit dieser Verteilung untersuchen. Wir vermuten, dass das 2-sample-Modell mit zwei Ausgangsmeinungen mit hoher Wahrscheinlichkeit immer noch eine (poly-)logarithmische Laufzeit aufweisen wird, sofern die Struktur des Graphen genügend viel Zufälligkeit beinhaltet. Bei Abstimmungen mit k > 2 Ausgangsmeinungen lässt sich diese Laufzeit womöglich nur dann erreichen, wenn schon zu Beginn des Verfahrens eine Meinung ein deutliches Übergewicht gegenüber den anderen besitzt. Wir werden diese Fälle sowohl analytisch wie auch empirisch untersuchen. Letztlich werden wir verteilte Abstimmungen in allgemeinen Graphen analysieren. Ziel ist es, eine enge Beziehung zwischen Expansionseigenschaften und Knotengrad-Verteilung einerseits, und der Laufzeit im c- sample-Modell andererseits, wobei c eine beliebige Konstante ist, nachzuweisen. Wir sind der Überzeugung, dass die dabei gewonnen Resultate zu neuen Erkenntnissen über die allgemeinen Zusammenhänge zwischen der Struktur eines Graphen und seinen algorithmischen Eigenschaften führen werden.

Unser Haupziel war die Entwicklung und Analyse von effizienten verteilten Voting-Algorithmen in großen Netzwerken. Gegeben ist ein Graph und eine Menge von Meinungen, die den Knoten zugewiesen werden. Vor dem Beginn des Projektes behandelten die meisten Arbeiten das sog. single-sample Voting: jeder Knoten kontaktiert - in synchronen Schritten, einen zufällig gewählten Nachbarn und übernimmt seine Meinung. In diesem Projekt haben wir uns auf two-sample Voting konzentriert. D.h., jeder Knoten kontaktiert zwei zufällig gewählte Nachbarn und übernimmt die Meinung dieser Knoten, sofern die zwei Meinungen übereinstimmen. Dieses Protokoll ist in Graphen mit sehr guten Expansionseigenschaften viel schneller als das klassische single-sample Voting. Folgende Resultate wurden erzielt: - wir haben gezeigt, dass einfache Modifikationen des two-sample Voting in (poly-)logarithmischer Zeit Konsensus erreichen, wenn die Topologie des Graphen gute Expansionseigenschaften aufweist, auch in nicht-regulären Graphen. - wir haben den Fall analysiert, in dem die Anzahl der Meinungen mit der Anzahl der Knoten wachsen darf. Wir haben untere und obere Schranken vorgestellt und haben neue Algorithmen entwickelt, die das Konsensus-Problem in vollständigen Graphen effizient lösen. Durch die Anwendung der o.g. Modifikationen können diese Protokolle in beliebigen (regulären) Graphen angewendet werden, wobei die Laufzeit sich um die Mixing-Zeit des Graphen verschlechtert. - wir haben Voting-Prozesse in asynchronen Szenarien untersucht. Jeder Knoten besitzt eine Uhr und bei jedem Tick wird der Knoten aktiviert. Falls die Tickzeiten der Uhren der "positive aging" Eigenschaft unterliegen und der Unterschied zwischen der größten und zeitgrößten Meinung groß genug ist, so ist Voting effizient, auch wenn die Anzahl der initialen Meinungen n^{1/2-\epsilon} beträgt (\epsilon > 0 kann beliebig klein sein).