Randomisierte Algorithmen für Verteilungsprobleme Christian Scheideler Institut für Informatik...

Randomisierte Algorithmen für Verteilungsprobleme

Christian Scheideler

Institut für Informatik

Technische Universität München

Verteilungsprobleme

Problem: Verteilung von Daten auf Speicher

Anwendungen:

• Organisation großer Festplattensysteme

• Peer-to-Peer Systeme

Festplattensysteme

Server

Festplatten

Peer-to-Peer Systeme

Verteilungsprobleme

Anforderungen:

• Skalierbarkeit: Faire Verteilung der Daten und ihrer Anfragen auf Speichereinheiten

• Effizienz: Effiziente Operationen zum Einfügen, Löschen und Suchen von Daten

Verteilungsprobleme

Grundlegender Ansatz: Hashing

Vorteile: O(1) Zeit für Einfügen, Suchen und Löschen von Daten möglich

1 2 3 4

Hashfunktion h

Verteilungsprobleme


Vorteile: skaliert sehr gut, wenn Hash-funktion zufällig gewählt wird

1 2 3 4

Hashfunktion h

Verteilungsprobleme


Nachteil: Standardhashing nicht adaptiv, nicht robust gegenüber gegn. Verhalten

1 2 3 4

Hashfunktion h

Übersicht

• Bälle-in-Urnen – Spiele

• Speicherverwaltung in Festplattensystemen

• Robuste Informations- systeme

Bälle in Urnen

n Urnen

m Bälle

Problem: Faire Verteilung von m Bällen auf n Urnen

Bälle in Urnen

Varianten:• Bälle bj: uniforme oder nichtuniforme

Gewichte wj (Gesamtgewicht 1) • Urnen vi: uniforme oder nichtuniforme

Kapazitäten ci (Gesamtkapazität 1)

Fairness: für jede Urne vi, i2{1,…,n} ist j: bj in vi

wj innerhalb von (1§ )ci für eine kleine

Konstante >0

Bälle in Urnen

Allgemein: Packungsproblem(werden wir hier nicht betrachten)

Hier:

• Beschränkung auf uniforme Ballgewichte

• Statischer Fall: Menge der Bälle und Urnen fest vorgegeben

Bälle in Urnen

Problem: verteile m Bälle gleichen Gewichts gleichmäßig über n Urnen gleicher Kapazität

verwende eine zufällige Hashfunktion

Bälle in Urnen

Hashfunktion zufällig: für jedes Datum x ist h(x) unabhängig von den anderen Daten uniform zufällig über die Menge der Urnen verteilt (d.h. wie echt zufällige Abbildung)

Tatsache: Für eine zufällige Hashfunktion enhält jede Urne im Erwartungswert m/n Bälle.

Ziel: hohe Konzentration um m/n mit hoher Wahrscheinlichkeit

„Mit hoher Wahrscheinlichkeit“ oder „m.h.W.“: >1-1/n für eine beliebige Konstante >1

Bälle in Urnen

Theorem: Mit hoher Wahrscheinlichkeit enthält jede Urne m/n § O( \/(m/n)log n + (log n)/(log log n)) viele Bälle.

Beweis: über Chernoff-Schranken

Chernoff-Schranke: Seien X1,…,Xn unabhängige binäre Zufallsvariablen. Sei X=i Xi und =E[X]. Dann gilt für alle >0

Pr[X >(1+)] < (e / (1+)1+)< e-2 / (2(1+/3))

Pr[X<(1-)] < (e- / (1-)1-) < e-2 /2

Bälle in Urnen

Chernoff-Hoeffding Schranke:Seien X1,…,Xn unabhängige binäre Zufallsvariablen. Sei X=i Xi und p=E[X]/n. Dann gilt für alle 0<<1-p

Pr[X-E[X] > n] <p

p+1-p

1-p-

p+ 1-p- n

Bälle in Urnen

Theorem: Mit hoher Wahrscheinlichkeit enthält jede Urne m/n § O( \/(m/n)log n + (log n)/(log log n)) viele Bälle.

Problem: Für m~n kann die Abweichung von m/n sehr hoch sein.

Lösung: erlaube mehr als einen zufälligen Ort pro Ball

Bälle in Urnen

Bälle in Urnen

Theorem: Für zwei zufällige Hashfunktionen existiert mit hoher Wahrscheinlichkeit eine Zuweisung von Bällen auf Urnen mit maximal dm/ne+1 Bällen pro Urne.

Beweis:• U: Teilmenge der Urnen• (U): Menge der Bälle, die alle Alternativen in U

haben

Lemma: Die minimax Last ist maxU=; |(U)|/|U|

Bälle in Urnen

Lemma: Die minimax Last ist L=maxU=; |(U)|/|U|

Beweis:

L

…..

U1 U2

beliebige Ballplatzierung

Bälle in Urnen

U1S1S2

S3

Alternative Hashpos.

Sk

. . .

U2

Bälle in Urnen

Lemma: maxU=; |(U)|/|U|<=dm/ne + 1 mit hoher Wahrscheinlichkeit.

Lemma: Für m>cn log n ist maxU=;|(U)|/|U| <=dm/ne mit hoher Wahrscheinlichkeit.

Beweis: ÜbungIdee:• Zeige, dass für jede Urnenmenge U gilt

Pr[ |(U)|/|U|>dm/ne ] < 1/n|U| • Fallunterscheidung zwischen |U|<=(2/3)n

(Chernoff) und |U|>(2/3)n (Chernoff-Hoeffding).

Bälle in Urnen

Theorem: Für zwei zufällige Hashfunktionen existiert mit hoher Wahrscheinlichkeit eine Zuweisung von Bällen auf Urnen mit maximal dm/ne+1 Bällen pro Urne.

Problem: wie schwierig ist es, solch eine Verteilung (annäherungsweise) zu erhalten?

Bälle in Urnen

Algorithmus 1: Minimumregel [KLM92]• Platziere die Bälle hintereinander in die

Urnen.• Für jeden Ball, wähle die Urne mit

minimaler Last aus.

Theorem: Die Minimumregel resultiert in einer Last von m/n + O(log log n) mit hoher Wahrscheinlichkeit.

Bälle in Urnen

Beweisidee für Minimumregel:

Last 4d d=log log n

…1 d2

1 2 d 1 2 d… … 2 innere Knoten,d-2 Blätter

d innere Knoten

Tiefe d

Lasten 4d-1..3d

1 2 d… 1 2 d…

… …

Bälle in Urnen

Zu zeigen: m.h.W. kommt so eine Struktur nicht in dem Graph G=(V,E) vor, in dem V die Urnen und E die Bälle mit ihren Alternativen darstellt.

Problem: Bälle können mehrmals vorkommen!

Übung: zeige zumindest, dass Wahrscheinlichkeit für Baumstruktur sehr gering ist, falls alle Bälle in ihr verschieden sind.

Bälle in Urnen

Algorithmus 2: L-Kollisionsregel [MD93, Sch93]• Alle Bälle sind anfangs aktiv.• Wiederhole, bis alle Bälle inaktiv

– Bestimme bezüglich der aktiven Bälle die Last für jede Urne für beide Hashfunktionen.

– Für alle Urnen mit einer Last von <= L werden alle aktiven Bälle mit Alternativen darin inaktiv.

Theorem: Die Kollisionsregel terminiert w.h.W. für L = O(m/n) in O(log log n) Runden.

Bälle in Urnen

Beweisidee für Kollisionsregel:

Last >L

…1 L2

1 2 L 1 2 L… … L innere Knotenmit Grad L

L innere Knotenmit Grad L

d Runden,d=log log n

Bälle in Urnen

Vorteile beider Strategien: L-Kuckucksregel:• Füge Bälle hintereinander in Urnen ein.• Platziere Ball x in Urne mit minimaler Last, sei v

diese Urne• Wiederhole, bis v eine Last <=L hat

- wähle einen zufälligen Ball x in v- platziere x in Alternativurne, sei diese Urne v

Behauptung: Kuckucksregel terminiert in Zeit O(m) m.h.W. mit L=min{O(m/n), m/n + O(log log n)}

Übersicht



• Robuste Informations- Systeme

Verteilte Speichersysteme

Daten

Speicher

Annahme: Daten haben uniforme GrößenProblem: Menge der Speicher jetzt dynamisch

Verteilte Speichersysteme

Anforderungen:• Fairness: j: bj in vi

wj innerhalb von (1§ )cifür eine beliebige Konstante >0.

• Effizienz: Ort jedes Datums kann zeit- und speichereffizient bestimmt werden

• Adaptivität: Für jeden Wechsel von (c1,…,cn) nach (c´1,…,c´n) ist die Menge der umzu-platzierenden Daten nahezu minimal (d.h. nahe (m/2)i|ci-c´i| )

• Redundanz: Jedes Datum hat k Kopien auf verschiedenen Speichereinheiten.

Uniforme Speichersysteme

Anforderungen:• Fairness: Anzahl Daten in Speicher i innerhalb

von (1§ )m/n für eine beliebige Konstante >0.• Effizienz: Ort jedes Datums kann zeit- und

speichereffizient bestimmt werden• Adaptivität: Für jeden Wechsel von n-1 nach n

oder n nach n-1 Speichern ist die Menge der umzuplatzierenden Daten nahezu minimal (d.h. nahe m/n )

• Redundanz: Jedes Datum hat k Kopien auf verschiedenen Speichereinheiten.


Konsistentes Hashing [KLL+97]:

1 2 3 4 5

0 1

Hash h

Hash g

R2


Theorem: Für jedes i2{1,…n} ist j: bj in vi wj

innerhalb von (1§ )|Ri|+O(log n / m) m.h.W. für eine beliebige Konstante >0.

Beweis:

Verwende Chernoff-Schranken.


Theorem: Für jedes i2{1,…n} ist E[|Ri|] = 1/n.Beweis:• Für alle i,j ist E[|Ri|] = E[|Rj|] (Symmetrie)• i |Ri|=1, also E[i |Ri|] = i E[|Ri|] = 1• Daher ist E[|Ri|] = 1/n für alle i

Konsistentes Hashing ist also im Erwartungswert fair (sowie effizient, adaptiv, und kann einfach auf Redundanz erweitert werden).

Problem: Abweichung vom Mittelwert kann groß sein! (Übung: in [(1/n2), ((log n)/n)] )


Problem: Abweichung vom Mittelwert kann groß sein (in [(1/n2), ((log n)/n)] )

Lösungen:• Verwende (log n) Hashfunktionen für die

Speicher. Damit hat jeder Speicher (log n) Regionen in [0,1) mit Gesamtgröße innerhalb (1§ )/n m.h.W.

• Verwende Cut & Paste Methode


Cut & Paste Methode [BBS00]:

0 1

Hash h

1 2 3 4 5

mittels Cut&Paste


10

1

10

1

2 10

1

2

1/21/3

3

1/2

10

2

1/3

3

1/4

4

usw.Speicher i raus: letzterSpeicher (d.h. n) über-nimmt dessen Platz


Tatsache: Cut&Paste weist jedem Speicher einen Teil von [0,1) der Größe exakt 1/n zu.

Theorem: Bei Anwendung von Cut&Paste von 1 nach n Speichern wird jedes Datum höchstens dlog ne–mal umplatziert.

Beweis: Übung.

Konsequenz: Damit Position jedes Datums effizient berechenbar (O(log n) Zeit).

Nichtuniforme Speichersysteme

SHARE Strategie [BSS02]:

0 1

Hash h

1 2 3 4 5

Hash g

R2

|Ri|=s ¢ ci

für Stretch s


Wende zur Entscheidung konsistentes Hashing auf überschneidende Menge der Speicher an.

0 1

1 2 3 4 5

Speicher 2 oder 4?


Lemma: Für einen genügend großen Stretch s=(log n) ist die Anzahl der Intervalle über jeden Punkt in [0,1) innerhalb von (1§ )s m.h.W.

Beweis: Übung.

Theorem: Unter der Annahme, dass für jedes Datum x mit k Speicherintervallen über h(x) es gleichwahrscheinlich ist, in welchem der k Speicher x gespeichert wird, ist SHARE fair.


Probleme:

• Da SHARE auf konsistentem Hashing aufbaut, Probleme mit Abweichungen bei Fairness

• SHARE kann im Allgemeinen nicht Redundanz sicherstellen. Beispiel:

1/2 1/4 1/4 Redundanz k=2


SIEVE Strategie [BSS02]:

1 2 3 4 5 6 7 8

2n Intervalle (Rahmen) der Größe 1/2n

0 1

• Jeder Rahmen ist höchstens einem Speicher zugeordnet.• Speicher i verwendet bis auf einen alle seine Rahmen vollständig, so dass insgesamt ein Bereich von ci/2 in [0,1) abgedeckt wird (wichtig für Adaptivität!)


SIEVE Strategie [BSS02]:

0 1

0 1

0 1

h1

h2

h3

log n) viele Hashfunktionen


Theorem: SIEVE ist fair, effizient und adaptiv m.h.W.

Beweis:

Fairness:

• Jede Urne i deckt ci/2 von [0,1) ab

• Chernoff-Schranken

Übersicht



• Robuste Informations- systeme

Skalierbare Informationssysteme

Klassische Netzwerktheorie: Graphfamilien

Beispiel: d-dim. de Bruijn Graph G=(V,E)• V = {0,1}d

• E = { {x,y} | x=(x1,…,xd), y=(b,x1,…,xd-1), b 2 {0,1} beliebig}

Wir brauchen: dynamische Form des de Bruijn Graphen (Peers gehen rein / raus)

00

01

10

11




• Betrachte (x1,…,xd) als 0.x1 x2…xd 2 [0,1), d.h. 0.101 = 1 ¢ (1/2) + 0 ¢ (1/4) + 1 ¢ (1/8)

• Setze d ! 1




Ergebnis für d ! 1:• V = [0,1)• E = { {x,y} 2 [0,1)2 | y=x/2, y=(1+x)/2 }


Kontinuierlicher de Bruijn Graph:

• V = [0,1)

• E = { {x,y} 2 [0,1)2 | y=x/2, y=(1+x)/2 }

Wie verwenden wir das für ein skalierbares Informationssystem?

Kontinuierlich-diskrete Methode! [NW03]

Kontinuierlich-Diskrete Methode

0 1

Peers

Jedem Peer wird zufälliger Punkt in [0,1) zugewiesen

Peers teilen [0,1) in Regionen auf

v

R(v)=[v,succ(v))

Kontinuierlich-Diskrete Methode

Kontinuierlicher de Bruijn Graph:• V = [0,1)• E = { {x,y} 2 [0,1)2 | y=x/2, y=(1+x)/2 }

0 1

Seien f0(x)=x/2 und f1(x)=(1+x)/2.Betrachte R0(v)=f0(R(v)) und R1(v)=f1(R(v)).

R1(v)R(v)R0(v)

Kontinuierlich-diskrete Methode

Verknüpfungsregel:• Kreiskanten: Peer v verbindet sich mit pred(v) und

succ(v) in [0,1)• De-Bruijn Kanten: Peer v verbindet sich mit allen Peers

w, für die R0(v) oder R1(v) mit R(w) überlappt.

Updates sehr einfach:• Join(v):

– Kreiskanten:

– De Bruijn Kanten:

pred(v) succ(v) pred(v) succ(v)v

0 1

pred(v) succ(v)v

R(v)

Kontinuierlich-diskrete Methode

Verknüpfungsregel:• Kreiskanten: Peer v verbindet sich mit pred(v) und

succ(v) in [0,1)• De-Bruijn Kanten: Peer v verbindet sich mit allen Peers

w, für die R0(v) oder R1(v) mit R(w) überlappt.

Updates sehr einfach:• Leave(v):

– Kreiskanten:

– De Bruijn Kanten:

pred(v) succ(v)pred(v) succ(v)v

0 1

pred(v) succ(v)v

R(v)

Datenzuweisung

0 1

Daten

Peers

Verwende konsistentes Hashing von [KLL+97]

(pseudo-)zufällige Hashfunktion

Robuste Informationssysteme

Skalierbarkeit ist nicht alles!

Robustheit gegenüber gegnerischemVerhalten immer drängender!!

InternetInternet InternetInternet

Ideale Welt

Vier Gebote:

1. Du sollst nicht schlafen

2. Du sollst nicht lügen

3. Du sollst nicht stehlen

4. Du sollst nicht töten

Maßnahmen bei Verletzungen:

Nicht so einfach wie es scheint…

!

Übersicht

• Methoden gegen Verletzungen von1. Du sollst nicht schlafen (fail-stop)2. Du sollst nicht lügen (Gegner)

• Methoden gegen Verletzungen von4. Du sollst nicht töten (DoS-Attacken)

Grundlegender Ansatz

Peers/Server formen einen Kreis

gegnerische Peersehrliche Peers

Zustände dem System nicht bekannt!

Robustheit

Gegenmaßnahmen zu:

1. Du sollst nicht schlafen

2. Du sollst nicht lügen Forme lokale Quoren

Halte gegn. Peers gut verteilt

Robustheit

Statische Menge von Peers:

Wähle zufällige Permutation für Anordnung

Robustheit

Dynamische Menge von Peers:

Zwei Operationen: Join und Leave

Join-Leave Robustheit

Problem: finde zustandslose Join und Leave Operationen, so dass für jede (selbst adaptive) Join-Leave Sequenz gegnerischer Peers die gegnerischen Peers im Kreis gut verteilt sind.


Modell:• n ehrliche Peers• n gegnerische Peers, <1• Zeit unterteilt in Runden• In jeder Runde kann Gegner Join oder Leave

Operation für einen gegnerischen Peer aufrufen

Ziel: finde Join und Leave Operationen, so dass für alle Folgen F von c log n Peers auf Kreis gilt:

Mehrheitsbedingung: die ehrlichen Peers in F sind in der Mehrheit.


Join-Operation:k-Rotation [Sch05]:- neuer Peer zunächst positionslos- vertausche (k-1)-mal hintereinander positionslosen mit zufälligem Peer im Kreis

- füge positionslosen Peer zufällig ein


Theorem: Solange < 1-2/k ist, gilt Mehr-heitsbedingung für poly viele Runden m.h.W., egal was der Gegner macht.

Analyse der k-Rotationsregel

Unterteile Regel in Stufen:• Stufe 0: neuer Peer ist obdachlos

• Stufe i 2 {1,…,k-1}: Position p wird uniform zufällig gewählt, obdachloser Peer wird in p plaziert, Peer vorher in p wird neuer obdachlose Peer

• Stufe k: obdachloser Peer wird in neuer zufälliger Position plaziert

Analyse der k-RotationsregelKonzentration auf einzelne Position p:• Zustandsraum: {(0,0),(0,1),(1,0),(1,1)}• Stufe 0: (0,0) ! (0,1), (1,0) ! (1,1)• Stufe i 2 {1,…,k-1}:

• Stufe k: {(0,0),(0,1)}!(0,0), {(1,0),(1,1)}!(1,0)

0,0 0,1 1,0 1,1

1-n/N

(n-1)/N

1/N

1/N

1-(n+1)/N

n/N

N: Anzahl Peers, n: ehrliche (blaue) Peers

n/N 1-n/N

n/N1-n/N

0: blau, 1: rot

(p,h)


Konzentration auf einzelne Position p:

• Anfangs hat p Verteilung (x,0,y,0), x+y=1

• Am Ende hat p Verteilung (x’,0,y’,0) mit

• Stationäre Verteilung: y’=y, N=(1+)n


Theorem: Für k>2 ist die worst-case Wahr-scheinlichkeitsverteilung der Zahl der roten Peers in einer Folge der Größe s=(log n) nach oben & unten beschränkt durch eine Binomialverteilung mit E.wert


Problem: viele Peer-to-Peer Systeme platzieren Peers in virtuellen Raum


Problem: viele Peer-to-Peer Systeme platzieren Peers in virtuellen Raum

Einfachster virtueller Raum: [0,1)-Intervall

0 1


• n ehrliche Peers, n gegn. Peers, <1

• Jeder Peer hat Punkt in [0,1)

0 1


Ziel: Für jedes Interval I ½ [0,1) der Größe (c log n)/n, c konstant, gilt:

• Balancierung: (log n) Peers in I

• Mehrheit: ehrliche Peers in Mehrheit in I

0 1I

Wie sind Bedingungen zu erfüllen?

Chord: verwendet kryptographische Hashfunktion, um Peers Punkte in [0,1) zuzuweisen

• zufällige Verteilung der ehrlichen Peers• keine zufällige Verteilung der gegnerischen Peers

01


CAN: weist den Peers zufällige Punkte in [0,1) zu


Group Spreading [AS04]:

• Weise Peers zufällige Punkte in [0,1) zu

• Begrenze die Lebenszeit der Peers

Zu teuer!


k-Kuckuck-Regel [AS06]:

leere k/n-Region

n ehrlich n gegnerisch

< 1-1/k

Analyse der k-Kuckucksregel

• k-Region: Region der Größe k/n• Alter einer k-Region: Anzahl Runden seit

letztem Treffer in Kuckucksregel.• R: feste Region aus (c log n) k-Regionen• Alter von R: Alter seiner k-Regionen• Neuer Peer: noch nicht replaziert• >0: kleine Konstante

Lemma 1: R enthält <=c log n neue Peers.


Lemma 2: R hat Gesamtalter von (1 § ) (c log n)n/k, m.h.W.

Beweis:

• Alter jeder seiner k-Regionen Ri: Pr[Alter(Ri)=t] = (k/n)(1-k/n)t-1

• Alter der k-Regionen quasi-unabhängig, damit Alter von R konzentriert um E[R] = i E[Ri] = i n/k = (c log n)n/k


• R: feste Region aus c log n vielen k-Regionen• T=(/)log2 n• >0: kleine Konstante

Lemma 3: In jedem Zeitintervall der Größe T werden m.h.W. (1§ )kT blaue Peers und <(1+)kT rote Peers umplaziert.

Lemma 4: R hat m.h.W. (1§ )(c log n)k alte blaue Peers und <(1+)(c log n)k alte rote Peers.

Beweis: Übung


# blaue Peers in R: >(1-)(c log n)k

# rote Peers in R:<(1+)(c log n)k + (c log n)

Theorem: Unter der k-Kuckucksregel sind für jedes k>1 und <1-1/k die Balan-cierungs- und Mehrheitsbedingungen m.h.W. erfüllt.

Grenzen der Kuckuck-Regel

• Funktioniert nur für Join-Leave Sequenzen von gegnerischen Peers.

k-flip&cuckoo Regel [AS07]

• Join: wie zuvor (k-Kuckuck-Regel)

• Leave: wähle zufällige k/n-Region unter benachbarten c log n k/n-Regionen, leere & vertausche sie mit zufälliger

k/n-Region

n ehrlich n gegnerisch

Tauschjoin

Übersicht

• Methoden gegen Verletzungen von1. Du sollst nicht schlafen (fail-stop)2. Du sollst nicht lügen (Gegner)

• Methoden gegen Verletzungen von4. Du sollst nicht töten (DoS-Attacken)

• Weitere Probleme und Ausblick

Fundamentales Dilemma

• Skalierbarkeit:Minimiere Ressourcen für Operationen

• Robustheit:Maximiere DoS-Aufwand für Angreifer

Gegner hat Insider-Wissen: keine Chance!!

DoS-resistente Informationssysteme

Past-Insider-Attacke: Gegner kennt alles über System bis (unbekannte) Zeit t0

Ziel: skalierbares Informationssystem, so dass alles, was nach t0 eingefügt oder aktualisiert worden ist, sicher (m.h.W.) gegen jede past-insider DoS Attacke ist, die einen beliebigen -Bruchteil der Server lahmlegen kann (für ein >0)

Sie sind gefeuert!

Past insider DoS-Attacke

Dilemma:• Explizite Datenstruktur: Konsistenzprobleme

unter einer DoS-Attacke• Feste Hashfunktion: Strukturlos, aber trotzdem

leicht zu attackieren• Zufällige Platzierung: schwer zu attackieren,

aber Suche teuer

Kombiniere Hashing mit zufälliger Platzierung!!

Past-insider-resistentes System

hashbasierte Position (davon O(log n) viele)

zufällig gestreute Kopien

[AS07]

Fragen?

Übungen

1. Zeige: maxU=; |(U)|/|U|<=dm/ne + 1 m.h.W. für m> cn log n für eine genügend große Konstante c.

2. Zeige, dass die Zeugenstruktur für die Minimum-Regel sehr unwahrscheinlich für den Fall ist, dass alle Bälle in ihr verschieden sind.

3. Zeige, dass es beim konsistenten Hashing erwartungsgemäß mindestens eine Region Ri gibt mit |Ri|<=1/n2 und mindestens eine Region Ri gibt mit |Ri|>=(log n)/n.

Übungen

4. Zeige: Bei Anwendung von Cut&Paste von 1 nach n Speichern wird jedes Datum höchstens dlog ne–mal umplatziert.

5. Zeige, dass für einen genügend großen Stretch s=(log n) die Anzahl der Invervalle über jeden Punkt in [0,1) innerhalb von (1§ )s m.h.W. ist.

6. Beweise Lemma 4 der Kuckucksregel, d.h. R hat m.h.W. (1§ )(c log n)k alte blaue Peers und <(1+)(c log n)k alte rote Peers. Benutze dazu die vorigen Lemmata.

Date post:	05-Apr-2015
Category:	Documents
Upload:	grete-ahner
View:	107 times
Download:	1 times

Randomisierte Algorithmen für Verteilungsprobleme Christian Scheideler Institut für Informatik...

Documents