29
1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung Christian Schindelhauer

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

Embed Size (px)

Citation preview

Page 1: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

1

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

Algorithmen für Peer-to-Peer-Netzwerke

Sommersemester 200421.05.2004

5. Vorlesung

Christian Schindelhauer

Page 2: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Kapitel III

CHORD

Page 3: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Brückentagvorlesungsplan

IF studenten kommen THEN

– Chernoffschranke

• mit Beweis

– Bälle in Körbe

• (ist dann ganz einfach)

– CHORD-Wiederholung

– Eigenschaften von CHORD

• mit Hilfe von Bällen und KörbenEND IF

Page 4: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Markov und Chebyshev

Stärkere Abschätzung: Chebyshev

wenn die Varianz bekannt ist:

Page 5: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Chernoff-Schranke

Bernoulli-Experiment

– Entweder 0 mit Wahrscheinlichkeit 1-p

– Oder 1 mit Wahrscheindlichkeit p

Page 6: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Beweis der 1. Chernoff-Schranke: Der Trick

Zu zeigen:

Für t>0:

Markov liefert:

Zu tun: geeignete Wahl für t und einsetzen...

Page 7: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Beweis der 1. Chernoff-SchrankeEin Erwartungswert

Zu zeigen:

wobei:

Jetzt zu zeigen:

Unabhängigkeit der Zufallsvariablen xi

Page 8: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Beweis der 1. Chernoff-SchrankeEtwas Algebra

Zu zeigen:

wobei:

Jetzt zu zeigen:

Page 9: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Beweis der 1. Chernoff-Schranke1.Fall c<c2

Zu zeigen für c>1:

Nun ist für c=1: 2 ln(2) > 4/3

Ableitung:

– linke Seite: ln(1+c)

– rechte Seite: 4/3Für c>1 ist Steigung der linken Seite größer als die rechten Seite, da

• ln(1+c)>ln (2) > 4/3Also gilt Ungleichung für c>0.

Page 10: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Beweis der 1. Chernoff-Schranke2. Fall c2<c

Zu zeigen für c< 1:

Nun ist für x>0:

Daraus folgt

Nun erhält man für (1+x) ln(1+x) durch Multiplikation:

Nun setzt man für ein (1+c) ln(1+c) und erhält for c(0,1):

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

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

2. Chernoff-Schranke

Bernoulli-Experiment

– Entweder 0 mit Wahrscheinlichkeit 1-p

– Oder 1 mit Wahrscheindlichkeit p

Page 12: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Beweis der 2. Chernoff-Schranke: Der Trick

Zu zeigen:

Für t<0:

Markov liefert:

Zu tun: geeignete Wahl für t und einsetzen...

Page 13: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Beweis der 2. Chernoff-SchrankeDer selbe Erwartungswert

Zu zeigen:

wobei:

Jetzt zu zeigen:

Unabhängigkeit der Zufallsvariablen xi

Page 14: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Beweis der 2. Chernoff-SchrankeEtwas Algebra

Zu zeigen:

wobei:

Jetzt zu zeigen:

Page 15: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Beweis der Chernoff-Schranke 2. TeilWas ist (1-c) ln (1-c) - Nachtrag

Warum ist ?

Für c=0 sind beide Seiten gleich.

Die Ableitung der linken Seite ist ln(1-c); die der rechten ist -c

Nun ist

Daraus folgt

und insbesondere die gewünschte Ungleichung.

Page 16: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Bälle und Körbe

LemmaWerden m= k n ln n Bälle zufällig in n Körbe geworfen (für jedes k>0), gilt Folgendes:

1. Für alle c>k ist die Wahrscheinlichkeit, dass mehr als c log n Bälle auf einen Korb fallen ist höchstens O(n-c‘) für ein c‘>0.

2. Für alle c<k ist die Wahrscheinlichkeit, dass in einem Korb weniger als c log n Bälle fallen, ist höchstens O(n-c‘) für ein c‘>0.

Beweis: Betrachte einen Korb mit Bernoulli-Experiment: B(k n ln n,1/n) mit Erwartungswert: µ =

m/n = k ln n1. Fall: c>2k

2. Fall: k<c<2k

3. Fall: c<k

Page 17: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Bälle und Körbe

Lemma

Werden m Bälle zufällig in n Körbe geworfen. Dann gilt:

1. Die Wahrscheinlichkeit, dass ein (bestimmter) Korb leer bleibt, ist kleiner als e-n/m.2. Die Wahrscheinlichkeit, dass mehr als k (ln n) + k m/n (ln n) Bälle auf einen

bestimmten Korb fallen, ist höchstens O(n-c) für konstante k und c.

Beweis:

1. Wahrscheinlichkeit: (1-1/n)m < e-n/m

2. Bernoulli-Ereignis: 1 Ball in einem Korb X: Summe aller m Ballwürfe in einem Korb• Wahrscheinlichkeit: p=1/n• Erwartungswert µ = 1• Fall m≥n, c>1:

• Fall m<n, c>1:

Page 18: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Hohe Wahrscheinlichkeit

Lemma

Falls Aussage A(i) für jedes von n Objekten i mit Wahrscheinlichkeit 1-n-c gilt, dann gilt (A(1) und A(2) und ... und A(n)) mit Wahrscheinlichkeit mindestens 1-n-(c-1)

Beweis:

Für alle i gilt: P[A(i)] ≤ n-c

Somit ist: P[ A(1) oder A(2) oder ... A(n) ] ≤ n n-c

P[( A(1) oder A(2) oder ... A(n)) ] ≤ 1- n n-c

Nach DeMorgan:

P[A(1) und A(2) und ... A(n) ] ≤ 1- n n-c

Page 19: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Chord als DHT

n: Knotenanzahl, Knotenmenge Vk: Anzahl Schlüssel, Schlüsselmenge

Km: Hashwertlänge: m >> log maxK,N

Zwei Hash-Funktionen bilden auf 0,..,2m-1 ab

– rV(b): bildet Peer b zufällig auf 0,..,2m-1 ab

– rK(i): bildet Index i zufällig auf 0,..,2m-1 ab

Abbildung von i auf einen Peer b = fv(i)

– fV(i) := arg minbV (rB(b)-rK(i)) mod 2m

Index

rK(i) = 3i-2 mod 80

123

4

5

6

7

rV(b) = b+1 mod 8

2

3

5

2 0

6

Page 20: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Eigenschaften der Datenstruktur

Lemma

1. Der Abstand zweier benachbarter Peers auf dem Ring ist

a) im Erwartungswert 2m/n,

b) < O((2m/n) log n) (mit hoher W‘keit) und

c) > 2m/nc (mit hoher W‘keit) für eine Konstante c>1

2. In einem Intervall des Rings der Länge w 2m/n sind (mit hoher W‘keit)– O(log n + w log n) Peers, falls w=O(log n) – O(w) Peers, falls w=Ω(log n)

Page 21: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Eigenschaften der Datenstruktur

Lemma1. Der Abstand zweier benachbarter Peers auf dem Ring ist

a) im Erwartungswert 2m/n,b) < O((2m/n) log n) (mit hoher W‘keit) undc) > 2m/nc (mit hoher W‘keit) für eine Konstante c>1

Beweis1a) Die Summe aller Abstände ist 2m

1b) Betrachte Intervall auf dem Ring der Länge c ((2m/n) log n)a) W‘keit, dass ein Peer dieses Intervall trifft: c (log n)/nb) W‘keit, dass n Peers dieses Intervall nicht treffen:

c) Damit bleibt so ein Intervall nicht leer und der Abstand zweier Peers ist mit hoher W‘keit ≤ 2c (2m/n) log n)

1c) Die W‘keit, dass ein Peer ein Intervall der Größe 2m/nc trifft, ist n-c

a) Also treffen Peers mit hoher W‘keit nicht in die Nähe eines anderen Peers

Page 22: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Eigenschaften der Datenstruktur (Beweis 2)

Lemma

2. In einem Intervall des Rings der Länge w 2m/n sind (mit hoher W‘keit)

a) O(log n + w log n) Peers, falls w=O(log n)

b) O(w) Peers, falls w=Ω(log n)

Beweis

Betrachte Intervall der Länge w 2m/n– Die W’keit, dass ein Peer hineinfällt ist p= w n– Erwartete Anzahl von Peers: p n = w

2a)

1.Fall: p n ≥ 1, c>1

2.Fall: p n < 1, c>1

2b) p n > k ln n, c > 1

Page 23: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Balance in Chord

– n: Anzahl der Knoten im P2P-Netzwerk

– k: Anzahl der Schlüssel 1

Theorem

Elemente werden auf die Peers wie folgt verteilt:

– Falls k=O(n log n):In jedem Knoten werden höchstens O(log n + k/n log2 n) Schlüssel gespeichert mit hoher W’keit

– Falls k=(n log n): In jedem Knoten werden höchstens O(k/n log n) Schlüssel gespeichert mit hoher W’keit

Beweis

– Übung

– Tipp:

Page 24: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Die Datenstruktur von Chord

Für jeden Knoten b:– successor: Nachfolger– predecessor: Vorgänger– Für i 0,..,m-1

• Finger[i] := Der Knoten derdem Wert rV(b+2i) folgt

Für kleine i werden die Finger-Einträge immer gleich

– Nur unterschiedliche Fingereinträge werden gespeichert

0

123

4

5

6

7

5

2 0

successorpredecessor

finger[0]

finger[1]

finger[2]

Page 25: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Fingeranzahl

Lemma

1. Der Ausgrad im CHORD-Netzwerk ist O(log n) mit hoher W‘keit

2. Der Eingrad im CHORD-Netzwerk ist O(log2 n) mit hoher W‘keit

Beweis

1. Der minimale Abstand zweier Peers ist 2m/nc (mit hoher W‘keit)– Damit ist der Ausgrad beschränkt durch c log n (mit hoher W‘keit)

2. Der maximale Abstand zweier Peers ist O(log n 2m/n)– Jeder Peer, der mit einem seiner Finger auf diese Linie zeigt, erhöht den

Eingrad des nachstehenden Peers.– Die Gesamtlänge der Streckenabschnitte, wo solche Peers liegen ist

O(log2n 2m/n)– Damit ist w=O(log2n)

b

b.finger[m]

a.finger[m-1]

x ya

Page 26: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Suchen in Chord

Theorem

Die Suche braucht mit hoher W’keit O(log n) SprüngeSuchalgorithmus für Element s:

– Abbruch(b,s):

• Knoten b,b’=b.succ gefunden, mit rK(s) [rV(b),rV(b‘)|

– Hauptroutine: Starte mit irgendeinem Knoten b

while not Abbruch(b,s) do

for i=m downto 0 do

if rK(s) [rV(b.finger[i]),rV(finger[i+1])] then

b ← b.finger[i]

fi

od

b

s

b.finger[m]

b.finger[m-1]c

x y

Page 27: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

b

s

b.finger[m]

b.finger[m-1]c

x y

Suchen in Chord

Theorem

Die Suche braucht mit hoher W’keit O(log n) Sprünge

Beweis:• Mit jedem Sprung wird die Entfernung zum Ziel mindestens halbiert• Zu Beginn ist der Abstand höchstens 2m

• Der Mindestabstand zweier benachbarter Peers ist 2m/nc mit hoher W’keit• Damit ist die Laufzeit beschränkt durch c log n

Page 28: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

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

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätChristian Schindelhauer

Einfügen von Peers

Theorem O(log2 n) Nachrichten genügen mit pol. W’keit, um Peers in CHORD aufzunehmen

Beweisideeo Zuerst wird Zielgebiet in O(log n) Schritten gesuchto Die ausgehenden Zeiger werden vom Vorgänger und

Nachfolger übernommen und angepasst– Die Zeiger müssen jeweils um bis zu O(log n) Schritte entlang des

Rings angepasst werdeno Der Eingrad des neuen ist mit hoher W’keit O(log2 n)

– Zu suchen kostet jeweils O(log n)– Diese sind jeweils in Gruppen von maximal O(log n) benachbart.

– Damit fallen nur O(log n) Suchen á Kosten O(log n) an

– Die Aktualisierung hat jeweils konstante Kosten

Page 29: 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 21.05.2004 5. Vorlesung

29

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

Heinz Nixdorf Institut& Institut für InformatikUniversität PaderbornFürstenallee 1133102 Paderborn

Tel.: 0 52 51/60 66 92Fax: 0 52 51/62 64 82E-Mail: [email protected]://www.upb.de/cs/schindel.html

Vielen Dank

Ende der 5. VorlesungNächste Vorlesung: Fr. 28.05.2004 9-11 UhrNächste Übung: 6. Übung Mo. 31.05.2004 10,12,16 Uhr (A,B,C)