1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 02.07.2004 11. Vorlesung

1

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

Algorithmen für Peer-to-Peer-Netzwerke

Sommersemester 200402.07.2004

11. Vorlesung

Christian Schindelhauer

Algorithmen für Peer-to-Peer-Netzwerke 2


Algorithmen und KomplexitätChristian Schindelhauer

ORGANISATIONAbschlussveranstaltung: Terminvorschläge:

Freitag 30.07. 10-15 UhrFreitag 30.07. 19-23 UhrDienstag 03.08. 20-24 Uhr

Mögliche Veranstaltungsform:1. Barbecue/Grillen 6. Fahrt mit Almetalbahn 01.08.2. Fußball 7. Freibadbesuch3. Basketball 8. Paintball4. Kegeln/Bowlen 9. Kartbahn5. Wandern 10. Wasserski

11. Radtour 12. Bungee-Springen13. Kino 14. ...




ORGANISATIONMündliche Prüfung: Termine: 13.-17.09.2004 (10-17 Uhr)

04.-08.10.2004 (10-17 Uhr)

Angebot:Öffentliche mündliche Prüfung am 30.07.2004 09:00 Uhr

mit einem freiwilligen Teilnehmer

(als Abschluss der Vorlesung)




Kapitel III

Epidemische Informationsausbreitung

und

Datenaggregation

Algorithmen für Peer-to-Algorithmen für Peer-to-Peer-NetzwerkePeer-Netzwerke




Epidemische Algorithmen

Synonym:– Gerücht, Virus, Nachricht, Epidemie

Epicast– Neue Information wird zum Gerücht– Solange das Gerücht neu ist, wird es weiterverbreitet– Ist das Gerücht alt, soll es schon allen bekannt sein

Epidemischer Algorithmus [Demers et al 87]– verbreitet Information wie einen Virus– robuste Alternative zu Broadcast

Kommunikationsform:– Random-Call-Modell

Für die Analyse betrachten wir nur ein Gerücht– Gelten die Eigenschaften mit hoher Wahrscheinlichkeit, dann gilt es auch für

polynomiell viele Gerüchte




Anruf-Model (Random Call)

Kommunikation wird synchronisiert modelliert in Runden

In jeder Runde kontaktiert jeder Teilnehmer einen uniform zufällig gewählten Teilnehmer

Man unterscheidet dei Kommunikationsmodelle

– Push: Der Anrufer gibt die Information dem Angerufenen

– Pull: Der Angerufene gibt die Information dem Anrufer

– Push&Pull: Kombination von Push und Pull

Push

Pull

Push&Pull




Epidemische Algorithmen in Peer-to-Peer-Netzwerken

Epidemische Algorithmen sind älter als Peer-to-Peer-Netzwerke

– 1987 versus 1999Epidemische Algorithmen brauchen zufällige Adressierung

– Viele Peer-to-Peer-Netzwerke unterstützen dies

– Gnutella

• Random Walk erreicht zufällige Adressierung

– CAN:

• Verwende Sprung zwischen den Realitäten

• Dadurch zufälliger Sprung in O(1) Hops

– CHORD, Koorde, Viceroy

• Zufälliger Sprung in log n Hops

– Pastry, Tapestry

• Zufälliger Sprung in log n Hops




Notation

Betrachte eine Nachricht

n: Anzahl Teilnehmer

I(t): Menge der informierten/infizierten KnotenS(t) = n-I(t) Menge der noch nicht Informierten

i(t) = |I(t)|/n Relativer Anteil der Informiertens(t) =1-i(t) Relativer Anteil der Nicht-Informierten




Struktur des Anruf-Modells

Betrachte feste Runde

Ausgrad: immer 1

Eingrad

– 0 mit Wahrscheinlichkeit

– 1 mit Wahrscheinlichkeit

– k mit Wahrscheinlichkeit

Für große n und kleineres k Poisson-Verteilung mit Erwartungswert 1




Push-Modell: Anfangsphase s(t) = o(1)

3 Möglichkeiten in Runde t:

– Ein infomierter Anrufer ruft einen bereits informierten Knoten an, W’keit i(t)

– Ein informierter Anrufer ruft den selben Knoten wie ein anderer Knoten an: W’keit i(t)

W’keit, dass ein Knoten ohne Erfolg anruft: 2i(t)

W’keit für Infektion eines neuen Knoten, falls i(t) s(t)/2: 1 – 2i(t)

E[i(t+1)] i(t) + i(t) (1-2 i(t)) = 2 i(t) – 2i(t)2 2 i(t)




Push-Modell: Startphase & Exponentielles Wachstum

W’keit für Infektion eines neuen Knoten, falls i(t) s(t)/2: 1 – 2i(t)

E[i(t+1)] 2 i(t) – 2i(t)2 2 i(t)

1.Startphase: I(t) 2 c (ln n)2

o Varianz von i(t+1) relativ groß

o daher Verdopplung von i(t) erst nach O(1) Runden mit hoher W’keit

Exponentielles Wachstum: I(t) [2 c (ln n)2, n/(log n)]

1.(fast) Verdopplung mit hoher W’keit, d.h. 1-O(n-c)

2.Beweis durch Chernoff-Schranke:

3.Für unabhängige Zufallsvariablen Xi0,1 und mit





Beweis durch Chernoff-Schranke:

Für unabhängige Zufallsvariablen Xi0,1 und mit

Sei = 1/(ln n) und E[Xm] 2 c (ln n)3

Dann gilt 2 E[Xm] /2 c ln n

Damit ist





W’keit für Infektion eines neuen Knoten, falls i(t) s(t)/2: 1 – 2i(t)E[i(t+1)] 2 i(t) – 2i(t)2 2 i(t)

3.Zwischenphase I(t) [n/(log n), n/3]o Term 2i(t)2 2i(t)/(log n) kann nicht mehr vernachlässigt werdeno Trotzdem mit 2i(t) – 2i(t)2 4/3 i(t) noch exponentielles Wachstum,

aber Basis < 2 Sättigung: I(t) n/3

3.W’keit, dass ein Gesunder von I(t) = c n Infizierten nicht kontaktiert wird:

• Damit konstante W’keit für Infektion: 1 – e–1/3 und 1 – e–1

4.Daher E[s(t+1)] e–i(t) s(t) e–1/3 s(t)3.Gilt mittels Chernoff-Schranke auch mit hoher W’keit4.Exponentielles Schrumpfen der Gesunden5.Basis konvergiert gegen 1/e




Gerüchteausbreitung: Push

Startphase: i(t)<1/2 Sättigung: s(t) < 1/2

Sicherung

Zeit

i(t)

s(t)

1

0

log2 n ln n c ln n




Anruf-Model (Random Call)

Infektionsmodelle:

– Push-Modell:

• Der Anrufer infiziert den Angerufenen

– Pull-Modell:

• Der Angerufene infiziert den Anrufer

– Push&Pull-Modell:

• Beides




Pull-Modell

Gegeben: Rel. Anteil s(t) gesunder Knoten und i(t) Infizierter

– W’keit, dass gesunder Knoten einen Infizierten kontaktiert: i(t)

E[s(t+1)] = s(t) – s(t) i(t) = s(t) (1 – i(t)) = s(t)2

E[i(t+1)] = 1-s(t)2 = 1 – (1 – i(t))2 = 2 i(t) – i(t)2 2 i(t)

– Approximation funktioniert nur, falls i(t) klein Problem:

– falls i(t) (log n)2 exponentielles Wachstum nicht sicher

– Bis exponentielles Wachstum sicher startet, dauert es O(log n) SchritteAber dann:

– Falls s(t) 1/2: Anteil Gesunder wird in jedem Schritt quadriert,

• d.h. E[s(t+ O(log log n))] = 0,

– Falls i(t) 1/2, dann sind nach O(log log n) Schritten sind alle infiziert




Gerüchteausbreitung: Pull

Startphase i(t) < 1/2

Sättigung s(t) < 1/2

Sicherung

Zeiti(t)

s(t)

1

0

O(ln n) + log2n log log n O(log log n)




Push&Pull-Modell

o Kombiniert Wachstumsverhalten von Push und Pull1. Startphase: i(t) 2 c (ln n)2

• Push: Verdopplung von i(t) nach O(1) Runden mit hoher W’keit2. Exponentielles Wachstum: I(t) [2 c (ln n)2, n/(log n)]

• Push und Pull: (fast) Verdreifachung mit hoher W’keit in jeder Runde, d.h. i(t+1) 3 (1-1/(log n)) i(t)

3. Zwischenphase I(t) [n/(log n), n/3]• Push und Pull: Verlangsamtes exponentielles Wachstum

4. Quadratisches Schrumpfen I(t) n/3• durch Pull:

E[s(t+1)] s(t)2

1. Mit Chernoff-Schranke gilt mit hoher W’keits(t+1) 2 s(t)2

und damit nach zwei Runden für s(t) 1/21/2

s(t+2) s(t)2




Gerüchteausbreitung: Push & Pull

Startphase i(t)<1/2 Sättigung

s(t) < 1/2Sicherung

Zeiti(t)

s(t)

1

0

log3n log log n c log log n




Shenkers Min-Counter-Algorithmus

Einfache Terminierungsstrategie:

– Falls Gerücht älter als maxctr, dann stoppe Weitergabe

Vorteil:– Einfaches Verfahren

Nachteile:

– Wahl von maxctr entscheidend

• Falls maxctr zu niedrig, werden nicht alle Knoten informiert

• Falls maxctr zu hoch, entsteht Nachrichtenoverhead (n maxctr)

– Optimale Wahl bei

• Push-Kommunikation: maxctr = O(log n)

Nachrichtenmenge: O(n log n)

• Pull-Kommunikation: maxctr = O(log n)

Nachrichtenmenge: O(n log n)

• Push&Pull-Kommunikation: maxctr = log3n + O(log log n)

Nachrichtenmenge: O(n log log n)




Terminierung von GerüchtenMin-Counter-Algorithmus

Jeder für sich schätzt ein Gerücht für

– „neu“, „alt“, „sehr alt“, „sehr sehr alt“, „sehr sehr sehr alt“, ... ,

– „sehrmaxctr alt“ = „uralt“ ein.

Am Anfang ist jedes Gerücht „neu“.

Gerüchte werden nicht jünger.

Erfährt jemand ein Gerücht

– zum ersten Mal übernimmt er das Alter.

– zum zweiten Mal oder mehr als zweimal gleichzeitig, setzt er das Alter um eins höher.

Solange ein Gerücht nicht „uralt“ ist, erzählt man es weiter.

Falls ein Gerücht „uralt“ ist, wird es noch maxctr Runden lang in jeder Runde erzählt und dann vergessen.




Der Min-Counter-Algorithmus

Benutzt Kommunikation– Wird das Gerücht von allen Kontaktpartnern als älter erachtet,

wird der Alter-Zähler erhöhtShenkers Min-Counter-Algorithmus für maxctr = O( log log n)

– Jeder Spieler P führt Variable für Gerücht Variable

– A: Spieler P kennt Gerücht P nicht: ctrr(P) initialisiert mit 0

– B: Falls Teilnehmer P hört Gerücht R zum ersten Mal:

ctrR(P) 1

– B: Falls Teilnehmer Q1, Q2, …, Qm Kommunikationspartner von P in dieser Runde

Falls mini(ctrR(Qi) ctrR(P) dann ctrR(P) ctrR(P) + 1

– C: Falls ctrR(P) maxctr erzählte Gerücht für weitere maxctr Rundendanach D: stoppe Weiterübertragung des Gerüchts

Theorem

Der Min-Counter-Algorithmus informiert für Push&Pull-Kommunikation alle Teilnehmer in log3n + O(log log n) Runden mit W’keit 1nc, wobei maximal O(n log log n) Gerüchte übertragen werden.




Der Min-Counter-Algorithmus

Theorem

Shenkers Min-Counter-Algorithmus informiert für Push&Pull-Kommunikation alle Teilnehmer mit W’keit 1nc, wobei maximal O(n log log n) Nachrichten übertragen werden.




Push, Pull und Push&Pull

Verwendet man

...

OperationenPush Pull Push&Pull

dann muss man maxctr auf

...

setzen

O(log n) O(log log n) O(log log n)

und informiert in

...

Runden (Zeit) O(log n) O(log n)

log3n + O(log log n)

alle Knoten mit ... Nachrichten mit

Wahrscheinlich-keit 1—n —c O(n log n) O(n log log n) O(n log log n)




Wie gut sind O(n log log n) Nachrichten?

Theorem

Solange die Namen der Peers nicht verwendet werden, benötigt man im Random-Call-Modell

1. mindestens Ω(log n) Runden und

2. mindestens Ω(n log log n) Nachrichten

o Sind die Namen verfügbar, kann man in O(n) Nachrichten die Information verteilen

o Lösung:

o Verwende Verbindungen nur, wenn ein Baum addressiert wird




Anwendung von epidemischer Informationsausbreitung

DatenaggregationAlberto Montresor

Márk Jelasity

Ozalp Babaoglu

Universität Bologna

2003




Zählen als Beispiel

Wie kann man die Anzahl der Teilnehmer bestimmen?

1. Ansatz

– Setze Zähler auf 1 und gib diese Information den Nachbarn weiter

– Dieser erhöht den Zähler um 1 und gibt sie wieder weiter

Problem:

– Funktioniert nur mit Ring, benötigt Zeit n-1

2. Ansatz

– Epidemische Verbreitung einer Liste, in die sich jeder Teilnehmer einträgt

– Laufzeit O(log n)

– Nachricht O(n log log n) mit Push/Pull

– Nachteil: Nachrichtenlänge O(n)

– Eigenliche Nachrichtenmenge: n2 log log n




3. Ansatz für Zählen

In Chord-Datenstruktur

– Betrachte Abstand zu den nächsten O(log n) Nachbarn auf den Ring

– Abweichung um Faktor 1-c mit Faktor n-c

– Distanz1/n kann mit O(log n) Samples hinreichend genau bestimmt werden

Funktioniert nur für solche P2P-Netzwerke

Kann man auch exakt zählen mit Hilfe von Push & Pull ?




Datenaggregation: Zählen[Jelaisty, Montresor `03]

Betrachte folgenden Prozess

Initalisierung:

– Ein Teilnehmer startet den Zählvorgang und setzt seine Variable s1=1

Verbreitung:

– Jeder Teilnehmer i , der von einem zählenden Peer j zum ersten Mal kontaktiert wird, setzt si = 0

Ausgleich:

– Kontaktiert Peer i den Peer j setzen beide:

• si = (si+sj)/2

• sj = (si+sj)/2




Der Average-Algorithmus

Eingabe: s1,...,sn

–lokal an den Peers vorhandenAusgabe:

–wird an allen Peers approximiert

Kommunikationsmodell–wird durch getPair() festgelegt–In der Regeln kommen alle Peers gleichwahrscheinlich vor

–In jeder Runde wird ein Peer ausgewählt

Algorithmus (eine Runde):–loop n do

• (i,j) = getPair()

• si = (si+sj)/2

• sj = (si+sj)/2

–od

Theorem:

Nach O(log n) Runden gilt für alle Peers i

mit hoher Wahrscheinlichkeit.

wenn getPair dem Push oder Pull-Kommunikationsmodell folgt




Beweisidee: Datenaggregation Zählen

Betrachte empirisches Mittel und empirische Varianz

Betrachte den Konvergenzfaktor

definiert als

Dann kann gezeigt werden

For t = Ω(log n) gilt dann

Daraus folgt

und




Simulation

Ein Knoten wurde mit 100.000 initialisiert

Alle anderen Knoten mit 0Kommunikationsnetzwerk mit 20

Nachbarn einmalig uniform gewählt

Zur Anzeige wird der QuickTime™ Dekompressor „TIFF (LZW)“

benötigt.




Netzwerkabschätzung von dynamischen Netzwerken

Zählprozess wird immer wieder neu gestartet

Schnelle Approximationwird durch Simulationsergebnisse

nahegelegt

Zur Anzeige wird der QuickTime™ Dekompressor „TIFF (LZW)“

benötigt.




Peer-Ausfälle

Im schlimmsten Fall, fallen die Peers zu Beginn aus.Angenommen pfn Knoten fallen gleichverteilt durch einen Zufallsprozess

aus

Sei f das Mittel von si

Theorem

Mit zunehmender Teilnehmerzahl, nimmt der Einfluss der ausfallenden Peers ab (bei gleicher Ausfallwahrscheinlichkeit).




Weitere Aggregations-Funktionen

Min

– f(x,y) = min (x,y)

– Berechnet MinimumMax

– f(x,y) = max(x,y)

– Berechnet größtes Element

Analyse analog zu Rumor Spreading

– Minimum ist das Gerücht– Kombination mit

Terminierungsmechanismum

Summe– Verwende Average mit Initialisierung

der Summanden, Ergebnis sei s– Verwende Average zum Zählen von n– Ausgabe: n s

Geometrisches Mittel– Verwende in Average:

Produkt:– Kombination aus Geometrisches

Mittel g und Anzahl der Peers• gn




Datenaggregation

Funktioniert auf jeder zusammenhängenden Netzwerktopologie

– und nicht nur im Random-Call-Modell– dort aber mit logarithmischer

KonvergenzzeitKonvergenz ist stark abhängig von der

Netzwerkstruktur– für statische Netzwerk Analyse mit

Markov-Prozessen möglich (für Average)

Polynomielle Laufzeit auf– Ring– Gitter

Logarithmische Konvergenz im–Baum–Hyperwürfel–De-Brujin-Netzwerke–Butterfly-Netzwerke–CAN mit mehreren Realitäten

Offene Fragen:–Welche Funktionen sind für Datenaggregation geeignet

–Läßt sich der Unterschied von Push- und Pull nachweisen?

37


Algorithmen und Komplexität

Vielen Dank

Ende der 11. VorlesungNächste Vorlesung: Fr. 09.07.2004 9-11 UhrNächste Übung: Mo. 05.07.2004 10/11/16 Uhr (A/B/C)

Documents

1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 02.07.2004 11. Vorlesung