Online-Algorithmen

Matthias Westermann

Version 1.0

Inhaltsverzeichnis

1 Einleitung 31.1 Grundbegriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2 Amortisierte Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3 Grundlagen der Wahrscheinlichkeitsrechnung . . . . . . . . . . . . . 7

2 List-Accessing 102.1 Der Algorithmus Move-To-Front . . . . . . . . . . . . . . . . . . . . 112.2 Deterministische untere Schranke . . . . . . . . . . . . . . . . . . . 12

3 Selbstanpassende Suchbaume 143.1 Operationen auf Splay-Baume . . . . . . . . . . . . . . . . . . . . . 153.2 Analyse der SPLAY-Operation . . . . . . . . . . . . . . . . . . . . . 163.3 Statische Optimalitat von Splay-Baumen . . . . . . . . . . . . . . . . 20

4 Paging 224.1 Ein optimaler Offline-Algorithmus . . . . . . . . . . . . . . . . . . . 224.2 Deterministische Algorithmen . . . . . . . . . . . . . . . . . . . . . 23

4.2.1 Nicht-kompetitive Algorithmen . . . . . . . . . . . . . . . . 244.2.2 Marking-Algorithmen . . . . . . . . . . . . . . . . . . . . . 244.2.3 Deterministische untere Schranke . . . . . . . . . . . . . . . 254.2.4 Unterschiedliche Speichergroßen . . . . . . . . . . . . . . . 26

4.3 Randomisierte Algorithmen . . . . . . . . . . . . . . . . . . . . . . . 274.3.1 Randomisierter Marking-Algorithmus . . . . . . . . . . . . . 274.3.2 Randomisierte untere Schranke . . . . . . . . . . . . . . . . 28

5 Datenmanagement in Netzwerken 305.1 Definition des File-Allocation-Problems (FAP) . . . . . . . . . . . . 315.2 FAP auf Baumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315.3 Deterministische untere Schranke fur FAP . . . . . . . . . . . . . . . 345.4 FAP auf allgemeinen Graphen . . . . . . . . . . . . . . . . . . . . . 35

5.4.1 Deterministische Approximation von Metriken . . . . . . . . 355.4.2 Probabilistische Approximation von Metriken . . . . . . . . . 375.4.3 Randomisierter Online-Algorithmus . . . . . . . . . . . . . . 39

1

6 Lastbalancierung 416.1 Identische Maschinen . . . . . . . . . . . . . . . . . . . . . . . . . . 416.2 Eingeschrankte Maschinen . . . . . . . . . . . . . . . . . . . . . . . 426.3 Verwandte Maschinen . . . . . . . . . . . . . . . . . . . . . . . . . . 44

2

Kapitel 1

Einleitung

Die klassische Entwicklung und Analyse von Algorithmen geht davon aus, dass diezur Losung eines Problems benotigten Daten zu Beginn der Berechnungen vollstandigvorliegen. In vielen Anwendungen ist diese Annahme jedoch unrealistisch. Algorith-mische Probleme, die in der Praxis auftreten, sind oftmals online, d.h. relevante Datentreffen erst nach und nach im Laufe der Zeit ein. Ein Online-Algorithmus muss Aus-gaben berechnen, ohne zukunftige Eingaben zu kennen. Das folgende Ski-Rental Pro-blem wirkt etwas kunstlich, jedoch zeigt es, dass wir haufig Entscheidungen treffenmussen, deren Qualitat durch das Auftreten oder Ausbleiben zukunftiger Ereignissebeeinflusst wird.

Angenommen Du willst zum ersten Mal in Deinem Leben Ski fahren gehen. Lohntes sich fur Dich, eine komplette Ski Ausrustung zu kaufen, oder solltest Du sie Dirzunachst einmal ausleihen? Eine komplette Ski Ausrustung kostet eine Menge Geld,aber wenn Du haufig fahrst, dann ist sie die gunstigste Losung. Wenn sich aber nunherausstellt, dass Dir Ski fahren keinen Spass macht, Du Dich verletzt oder Du ausanderen Grunden nicht mehr Ski fahren mochtest oder kannst? Dann ware es sicherlichbesser, die Ski nicht gekauft zu haben.

Leider weiß man beim Ski fahren nicht vorher, ob es einem gefallt oder nicht.Deshalb muss man die Entscheidung, Ski zu kaufen, unabhangig vom Wissen uber dieZukunft treffen. Wir wollen nun das Ski-Rental Problem formalisieren: Nehmen wireinmal an, dass eine Ski Ausrustung 800 Euro kostet und das Leihen der Ski kostet 50Euro/Tag. Außerdem nehmen wir zur Vereinfachung an, dass Ski ewig halten.

Wir wollen nun versuchen eine gute Strategie zu finden. Dazu mussen wir uns ersteinmal uberlegen, was eine gute Strategie auszeichnet. Eine Strategie ist dann gut,wenn sie sicherstellt, dass wir – auch ohne die Zukunft zu kennen – nie viel mehr aus-geben, als notig ist. Das bedeutet, dass wir sicher nicht sofort Ski kaufen, denn wennwir nur einmal Ski fahren gehen, hatten wir 800 Euro ausgegeben, aber im schlech-testen Fall hatten wir nur 50 Euro benotigt. Das heißt, in diesem Fall hatten wir das16-fache des benotigten ausgegeben. Andererseits macht es auch keinen Sinn immerwieder Ski auszuleihen, denn dann werden wir beliebig viel zahlen, wenn uns das Skifahren gefallt.

3

Daher werden wir folgende Strategie verfolgen: Wir werden Ski ausleihen bis wirinsgesamt 750 Euro Leihgebuhr bezahlt haben oder wir aus irgendeinem Grunde nichtmehr Ski fahren wollen. Danach werden wir uns eine Ausrustung zulegen. Wir wer-den nun zeigen, dass man mit dieser Strategie nie mehr als das (2− 1/r)-fache desBestmoglichen bezahlt, wobei r = 800/50 = 16 das Verhaltnis zwischen den Kostenfur den Kauf und das Leihen von Ski ist. Angenommen wir wurden die Zukunft kennenund wussten genau, dass wir k mal Ski fahren. Wenn k < r ist, dann ist die optimaleStrategie, Ski zu leihen. Ansonsten ist die optimale Strategie, Ski sofort zu kaufen.Fur k < r ist unsere Strategie optimal. Fur k ≥ r werden wir mit unserer Strategie(2r−1) ·x = 1550 Euro ausgeben, wobei x = 50 die Kosten fur das Leihen der Ski proTag bezeichnet. Im besten Fall hatten wir nur r ·x = 800 Euro ausgegeben. Also hattenwir das (2−1/r)-fache des Bestmoglichen bezahlt.

Auch in der Informatik gibt es Probleme, bei denen wir Dinge entscheiden mussen,bevor die eigentlich relevanten Ereignisse passieren. Zum Beispiel will man in einemCache moglichst gerade die Daten behalten, die in (naher) Zukunft angefragt werden.Aber man weiß naturlich nicht, welche Daten das sind. Ein anderes Beispiel ist die Fra-ge, wie (d.h. uber welche Wege) man in einem Netzwerk die Datenpakete verschickt,um eine gleichmaßige Auslastung des Netzwerkes zu gewahrleisten. Auch hier weißman nicht, wo in naher Zukunft Datenverkehr entsteht.

1.1 GrundbegriffeBei Online-Problemen handelt es sich um eine spezielle Art von Optimierungspro-blemen. Im Allgemeinen sagen wir, dass ein Optimierungsproblem (wir betrachtenhier o.b.d.A. nur Minimierungsprobleme) aus einer Menge von Eingaben I und einerKostenfunktion C besteht. Fur jede Eingabe i ∈ I gibt es eine Menge von zulassigenAusgaben (Losungen) F(i). Mit jeder zulassigen Losung o ∈ F(i) sind Kosten C(i,o)assoziiert, die die Kosten fur Ausgabe o bei Eingabe i darstellen.

Ein Algorithmus ALG berechnet nun bei Eingabe i ∈ I eine Losung o ∈ F(i). DieKosten von ALG sind dann ALG(i) =C(i,o). Ein optimaler Algorithmus OPT berech-net fur jede Eingabe i ∈ I eine Losung mit den geringsten Kosten

OPT(i) = mino∈F(i)

C(i,o) .

Bei Online-Algorithmen kommt nun noch ein weiterer Aspekt hinzu: Die Eingabe istnicht vorab bekannt, sondern sie trifft erst nach und nach als Sequenz ein. Dem Online-Algorithmus wird also immer nur das nachste Element der Eingabesequenz prasentiertohne dass er die zukunftigen Elemente kennt.

Wir werden nun definieren, wie man die Gute eines Online-Algorithmus bewertet.Wir sagen, dass ein Online-Algorithmus ALG c-kompetitiv ist, wenn fur jede Einga-

4

besequenz σ giltALG(σ)≤ c ·OPT(σ)+α ,

wobei α eine Konstante ist, die unabhangig von σ ist. Wenn α = 0 ist, dann ist ALGstreng c-kompetitiv. Die Kompetitiv-Ratio eines Online-Algorithmus ALG bezeichnetdas Infimum uber alle Werte c mit der Eigenschaft, dass ALG c-kompetitiv ist.

Eine beliebte Art, Online-Algorithmen zu analysieren, ist, das Problem als Spielzwischen dem Online-Algorithmus und einem Gegenspieler zu modellieren. Dabeikennt der Gegenspieler den Online-Algorithmus und darf die Eingabesequenz bestim-men. Sein Ziel ist es, das Verhaltnis zwischen den Kosten des Online-Algorithmus undseinen Kosten zu maximieren. Das heißt, er wird eine Sequenz wahlen, welche dieKompetitiv-Ratio erreicht.

1.2 Amortisierte AnalyseWir werden nun eine Analysetechnik anhand einiger Beispiele kennenlernen, dieim Bereich Online-Algorithmen eine große Rolle spielt. Die so genannte amorti-sierte Analyse wurde ursprunglich zur Analyse von dynamischen Datenstruktureneingefuhrt. Dabei geht man davon aus, dass jede Operation mit einer gewissen MengeGeld startet. Mit diesem Geld bezahlt man fur das Ausfuhren von Operation und esist moglich Geld, das man fur eine Operation nicht verbraucht hat, fur zukunftige,unter Umstanden teurere, Operationen zu sparen. Man konnte auch sagen, dass manmit amortisierter Analyse die durchschnittlichen Kosten einer Worst-Case-Eingabeanalysiert.

Im Bereich Datenstrukturen wird die amortisierte Analyse benutzt, um die durch-schnittlichen Kosten einer Sequenz σ1, . . . ,σn von Anfragen mit Kosten c1, . . . ,cn zuanalysieren. Dabei gilt:

Worst-Case-Kosten von σ = maxi

ci

Gesamtkosten von σ = ∑i

ci

Amortisierte Kosten von σ = ∑i

ci/n

Als amortisierte Kosten (von Operationen auf) der Datenstruktur bezeichnet man danndas Maximum der amortisierten Kosten von σ uber alle Folgen σ.

Amortisierte Analyse eines BinarzahlersWir werden nun amortisierte Analyse anhand des Beispiels eines k-Bit Binarzahlerskennenlernen. Zu Beginn ist ein solcher Zahler mit 0 initialisiert und es gibt nur eineOperation, namlich das Erhohen des Zahlers um 1. Dies geschieht, indem man die Bits

5

von rechts nach links durchlauft und flippt, bis man ein Bit von 0 auf 1 geflippt hat.Die Anzahl der Bitwechsel gibt dabei die Kosten des Erhohens an.

Offensichtlich gilt, dass die Kosten fur das Erhohen des Zahlers im Worst-Case ksind. Doch was sind die amortisierten Kosten fur das Erhohen des Zahlers?

Theorem 1.1 Die amortisierten Kosten fur das Erhohen eines Zahlers sind O(1).

Wir werden den obigen Satz nun aus drei verschiedenen Blickwinkeln beweisen.Aus der Sicht eines Ingenieurs, eines Bankers und eines Physikers.

Sichtweise des Ingenieurs

Die Idee hier ist, dass ganze Problem einfach durchzurechnen. Wir stellen fest, dassdas rechteste Bit b0 jedesmal geflippt wird. Das zweitrechteste Bit b1 wird jedes zweitemal geflippt. Das Bit bi wird jedes 2i-te mal geflippt. Fur m Operationen ergeben sichamortisierten Kosten

c =∑blogmci=0 bm

2i cm

< 2 .

Sichtweise des Bankers (Konto Methode)

Bei jeder Operation werden zunachst c Euro gezahlt. Von diesen c Euro mussenzunachst die Kosten der Operation bezahlt werden. Eventuell ubrig gebliebenes Geldkann auf ein Konto eingezahlt werden. Sind die Kosten fur eine Operation großer alsc, so mussen diese mit Geld vom Konto bezahlt werden. Dann gilt folgende Beobach-tung.

Beobachtung 1.2 Hat ein System immer einen nicht negativen Kontostand, dann ist ceine obere Schranke fur die amortisierten Kosten des Systems.

Um nun unser Beispiel des Binarzahlers zu analysieren, setzen wir c = 2. Wirwerden fur jedes Bit einen eigenen Kontostand einfuhren. Der Kontostand eines Bits ist1, wenn der Wert des Bits 1 ist und 0 sonst. Nach der ersten Operation zeigt das kleinsteBit den Wert 1 und wir haben einen Euro fur das flippen gezahlt und den ubrigen Euroauf das Konto des kleinsten Bits gezahlt. Also stimmt unsere Behauptung.

Nehmen wir an, unsere Behauptung stimmt fur die ersten m Operationen. In Ope-ration m+ 1 werden nun die kleinsten j Bits des Zahlers geflippt. Per Definition ge-schieht dies, wenn die kleinsten j− 1 Bits den Wert 1 gezeigt haben. Wir zahlen dasFlippen der j− 1 Bits von den Konten dieser Bits und das Flippen des j-ten Bit vonunseren 2 Euro fur die Operation. Den ubrigen Euro zahlen wir auf das Konto von Bitj ein. Da die letzten j−1 Bits auf 0 gestellt wurden, durften wir jeweils den Euro ab-heben. Einen Euro mussen wir einzahlen, weil das j-te Bit auf 1 gesetzt wird. Da wirdiesen Euro eingezahlt haben, stimmt unsere Behauptung auch nach Operation m+1und ist damit per Induktion immer korrekt.

6

Sichtweise des Physikers (Potentialfunktion Methode)

Hier wird uberschussige Energie als Potential des gesamten Systems gespeichert. Die-ses Potential wird benutzt, um fur Operationen zu bezahlen, die mehr Energie kostenals sie bringen. Das Potential zum Zeitpunkt i wird mit Φi bezeichnet. Sei

ci +Φi−Φi−1 ≤ c .

Damit gilt

m · c =m

∑i=1

c≥m

∑i=1

(ci +Φi−Φi−1) =m

∑i=1

ci +Φn−Φ0 .

Beobachtung 1.3 Wenn Φm ≥ Φ0 ist, dann ist c eine obere Schranke fur die amorti-sierten Kosten.

Wir wenden nun die Potential Methode auf unser Binarzahler Problem an. Sei Φidie Anzahl Bits, die zum Zeitpunkt i auf 1 gesetzt sind. Es gilt Φm ≥ 0 = Φ0. Wirbetrachten die m-te Operation. Sei j−1 die Position des Bits, das auf 1 geflippt wird(und alle Bits an Positionen kleiner j werden auf 0 geflippt). Dann gilt

Φm−Φm−1 = 1− ( j−1) = 2− j .

Also sind die amortisierten Kosten hochstens

cm +Φm−Φm−1 = j+(2− j) = 2 .

1.3 Grundlagen der Wahrscheinlichkeitsrechnung

WahrscheinlichkeitsraumEin diskreter Wahrscheinlichkeitsraum ist eine endliche Menge Ω = ω1, . . . ,ωn vonElementarereignissen ωi.

Eine Wahrscheinlichkeitsverteilung gibt die Wahrscheinlichkeit Pr [ωi] = pi an.Dabei muss gelten, dass die Summe der Wahrscheinlichkeiten uber alle Elementa-rereignisse 1 ist, d.h.

∑ωi∈Ω

Pr [ωi] = 1 ,

und die Wahrscheinlichkeiten durfen nicht negativ sein, also

Pr [ωi]≥ 0 .

Beispiel 1.4 Sei Ω = Wurfelergebnis zweier unterscheidbarer Wurfel. Dann ist

Ω = (1,1),(1,2),(1,3,),(1,4),(1,5),(1,6),(2,1),(2,2), . . . ,(2,6), . . . ,(6,6) .

Da jeder Wurf gleichwahrscheinlich ist, gilt fur jedes Elementarereignis a ∈Ω,

Pr [a] = 1/36 .

7

EreignisEine Menge W ⊆Ω heißt Ereignis. Die Wahrscheinlichkeit eines Ereignisses W ist

Pr [W ] = ∑ω∈W

Pr [ω] .

Beispiel 1.5 Im Beispiel zweier Wurfel kann man das Ereignis W = Pasch definieren,also W = (1,1), . . . ,(6,6). Fur diese Ereignis ergibt sich

Pr [W ] = 6 ·1/36 = 1/6 .

ZufallsvariableEine Zufallsvariable ist eine Funktion

X : Ω→ R .

Offensichtlich bezeichnet der Begriff Zufallsvariable nicht einfach eine Variable imklassischen Sinne. Viel mehr ist der Wert X vom Ausgang eines Zufallsexperimentesabhangig und in diesem Sinne eine Variable.

Beispiel 1.6 Im Beispiel Wurf zweier Wurfel bezeichnet

X((a,b)) = a+b

die Zufallsvariable fur die Summe der beiden Wurfel.

Man schreibt auch abkurzend

Pr [X < k]

furPr [ω ∈Ω|X(ω)< k] .

Analog benutzt man auch Pr [X = k] und Pr [X > k].

ErwartungwertDer Erwartungswert einer Zufallsvariable gibt den durchschnittlichen Wert an, deneine Zufallsvariable annimmt. Der Erwartungswert E [X ] einer Zufallsvariable X istdefiniert als

E [X ] = ∑k∈X(Ω)

k ·Pr [X = k] .

Beispiel 1.7 Wir betrachten noch einmal das Werfen von zwei Wurfeln und die Zu-fallsvariable X fur die Summe der beiden Wurfel. Wir bekommen:

E [X ] = 2 ·1/36+3 ·1/18+4 ·1/12+ · · ·+12 ·1/36 = 7 .

8

Linearitat des ErwartungswertesDie Linearitat des Erwartungswertes ist eine der wichtigsten Eigenschaften, die wirbei der Analyse randomisierter Algorithmen ausnutzen. Seien X1, . . . ,Xn Zufallsvaria-blen auf Ω. Dann gilt

E

[n

∑i=1

Xi

]=

n

∑i=1

E [Xi] ,

wobei (n

∑i=1

Xi

)(ω) =

n

∑i=1

Xi(ω)

bezeichnet. Linearitat des Erwartungswertes bedeutet also, dass der Erwartungswerteiner ”zusammengesetzten“ Zufallsvariable bestimmt werden kann, indem man sie alsSumme ”einfacherer“ Zufallsvariablen schreibt und fur diese einfachen Zufallsvaria-blen ihren Erwartungswert bestimmt. Die Summe des Erwartungswertes der einfachenZufallsvariablen ist dann der Erwartungswert der zusammengesetzten Zufallsvariable.

9

Kapitel 2

List-Accessing

Als erstes werden wir uns mit dem List-Accessing-Problem beschaftigen. Dabei neh-men wir an, dass ` Datensatze in einer verketteten Liste abgespeichert sind. Zu jedemDatensatz gibt es einen Schlussel. Datensatze konnten z.B. Kundendaten sein und derSchlussel ist der Kundenname.

Zugegriffen wird auf die Datensatze wie folgt: Die Liste wird von vorne nach hin-ten durchgesehen, bis man auf den Datensatz trifft bzw. weiß, dass der Datensatz nichtin der Liste vorhanden ist. Wir nehmen an, dass wir fur eine solche Operation x Schrit-te benotigen, wobei x die Position des Datensatzes in der Liste ist. Neue Datensatzekonnen in die Liste eingefugt werden und Datensatze konnen auch geloscht werden.Das Einfugen eines Datensatzes kostet `+ 1 Zeitschritte, wobei ` die Lange der Li-ste vor Einfugen des Datensatzes ist. Das Loschen des x-ten Datensatzes in der Listekostet x Zeitschritte.

Bisher haben wir eine Implementierung (durch verkettete Listen) des abstraktenDatentyps Worterbuch beschrieben. Die Implementierung durch verkettete Listen istsehr einfach und wird daher haufig fur Worterbucher moderater Große genutzt.

Aber wo ist nun ein Online-Problem versteckt?Nach einem Zugriff oder dem Einfugen bzw. Loschen eines Datensatzes in der

Liste ist es erlaubt, die Liste neu zu organisieren. Wir messen die Kosten zur Reorga-nisation der Liste in Transpositionen (Vertauschungen benachbarter Elemente). Es gibtjedoch eine Sonderregel: Einen Datensatz, auf den gerade zugegriffen wurde, durfenwir kostenlos naher zum Listenanfang verschieben. Die Idee ist hier, dass wir bei derSuche nach diesem Datensatz Zeiger zu den bisher besuchten Positionen aufrecht er-halten konnen. Alle anderen Transpositionen sind kostenpflichtig: Sie kosten einenZeitschritt.

Damit haben wir folgendes Online-Problem: Beim List-Accessing-Problem ist einOnline-Algorithmus gesucht, der die Liste nach jedem Zugriff geschickt reorganisiert,so dass die Gesamtzugriffszeit minimiert wird.

In unserer Beschreibung haben wir ein dynamisches Problem beschrieben – wirhaben das Einfugen und Loschen von Datensatzen erlaubt. Eine andere Variante des

10

Problems ist das statische List-Accessing-Problem. Dabei sind nur Zugriffsoperationenerlaubt.

2.1 Der Algorithmus Move-To-FrontDer deterministische Algorithmus Move-To-Front (MTF) ist sehr einfach: Nach jedemZugriff auf einen Datensatz oder dem Einfugen eines Datensatzes bewegen wir diesenan die erste Position der Liste, ohne die relative Ordnung der anderen Elemente zuverandern. Wir werden nun zeigen, dass MTF eine Kompetitiv-Ratio von 2 erreicht.

Theorem 2.1 MTF ist 2-kompetitiv.

Beweis. Wir mussen zeigen, dass fur jede beliebige Sequenz von Operationen σ =σ1 · · ·σn (Zugriff, Einfugen, Loschen) MTF hochstens doppelt so viele Zeitschrittebenotigt wie ein optimaler Offline-Algorithmus OPT. Wir stehen nun vor einem Pro-blem: Im Gegensatz zum Ski-Rental Problem kennen wir keine einfache Beschreibungeiner optimalen Offline-Strategie. Wie konnen wir dann jedoch eine Aussage uber dieKompetitiv-Ratio machen?

Wir werden eine Potentialfunktion Φi benutzen, die die Konfiguration von MTFund OPT beschreibt, nachdem Operation σi bearbeitet worden ist. Der Wert von Φiist die Anzahl der Inversionen in der Liste von MTF bezuglich der Liste von OPT,dabei ist eine Inversion ein geordnetes Paar von Datensatzen 〈x,y〉, wobei x vor y inder Liste von MTF steht, aber x nach y in der Liste von OPT steht. Wir bezeichnen mitcon

i die Kosten von MTF fur die i-te Operation und mit coffi die entsprechenden Kosten

von OPT. Wir wollen zeigen, dass fur die amortisierten Kosten von MTF fur die i-teOperation gilt:

ai = coni +Φi−Φi−1 ≤ 2 · coff

i .

Im Unterschied zu unseren bisherigen Beispielen konnen die amortisierten Kosten furdie einzelnen Operationen verschieden sein.

Wir wollen nun zeigen, dass die amortisierten Kosten fur die i-te Operationhochstens (2s−1)+P−F betragen. Dabei bezeichnet s die Suchkosten, P die Anzahlkostenpflichtiger Transpositionen und F die Anzahl kostenloser Transpositionen vonOPT bei der Bearbeitung der i-ten Anfrage.

Wir betrachten zunachst nur Zugriffsoperationen. Zuerst werden wir die Kostenanalysieren, die MTF verursacht, und danach werden wir die Kosten analysieren, dieOPT verursacht. Sei x der Datensatz, auf den zugegriffen werden soll. Sei j die Positionvon x in der Liste von OPT und k die Position in der Liste von MTF. Weiterhin sei vdie Anzahl der Datensatze, die in der Liste von MTF vor x stehen, aber in der Listevon OPT hinter x stehen. Dann gibt es k−1− v Datensatze, die in beiden Listen vor xliegen. Außerdem gilt k−1− v≤ j−1, da x an Position j in der Liste von OPT steht.Also gilt k− v≤ j.

11

Bewegt MTF nun x an die erste Position der Liste, so erzeugt er k− 1− v neueInversionen bezuglich der Liste von OPT. Desweiteren eliminiert diese Aktion auchv Inversionen bezuglich der Liste von OPT. Also ist der Beitrag zu den amortisiertenKosten

k+(k−1− v)− v = 2(k− v)−1≤ 2 j−1 = 2s−1 .

Die Suche von OPT beeinflusst die Potentialfunktion und damit die amortisiertenKosten nicht. Jede bezahlte Transposition von OPT erhoht das Potenzial hochstens um1, jede Transposition, die umsonst ist, verringert es um 1. Daraus folgt sofort, dass gilt

ai ≤ (2s−1)+P−F ≤ 2(s+P) = 2 · coffi .

Insgesamt ergibt sich fur die Kosten von MTF

MTF(σ) =n

∑i=1

coni =

n

∑i=1

ai +Φ0−Φn ≤ 2n

∑i=1

coffi = 2 ·OPT(σ) ,

da Φn ≥ 0 und Φ0 = 0 ist (die Listen von MTF und OPT sind zu Beginn identisch).Um dasselbe Ergebnis fur das Einfugen eines Datensatzes oder den Zugriff auf

nicht vorhandene Datensatze zu zeigen, konnen wir die gleichen Argumente verwen-den und mussen lediglich j = `+ 1 setzen, wobei ` die Lange der Listen bezeichnet.Der Fall, dass ein Datensatz geloscht wird ist noch einfacher, da hier keine neuen In-versionen erzeugt werden und somit der Beitrag von MTF zu den amortisierten Kostenk− v≤ j = s≤ 2s−1 ist.

2.2 Deterministische untere SchrankeWir werden nun eine untere Schranke fur deterministische Online-Algorithmen bzgl.des List-Accessing-Problems zeigen. Dabei beschranken wir uns auf das statische Mo-dell. Da das statische Modell ein Spezialfall des dynamischen Modells ist, gilt dieseSchranke naturlich auch fur den dynamischen Fall. Wir werden folgenden Satz bewei-sen.

Theorem 2.2 Ein jeder deterministische Online-Algorithmus fur das statische List-Accessing-Problem hat eine Kompetitiv-Ratio von mindestens 2− 2

`+1 , wobei ` dieAnzahl der Datensatze in der Liste bezeichnet.

Beweis. Sei eine Liste der Lange ` gegeben. Wir werden nun einen so genannten grau-samen Gegenspieler einsetzen. Dieser Gegenspieler fragt immer den Datensatz an,der am Ende der Liste steht. Er maximiert also die Kosten des Online-Algorithmus.Nehmen wir einmal an, dass die Lange der Anfragesequenz n ist. Dann sind die Ge-samtkosten des Online-Algorithmus ` ·n.

Wie konnen wir nun zeigen, dass es einen Offline-Algorithmus gibt, der diese An-fragesequenz besser bearbeiten kann. Dazu werden wir uns eine Menge von Offline-Algorithmen definieren und berechnen, wieviel Zeit diese im Durchschnitt brauchen,

12

um die Anfragesequenz zu bearbeiten. Danach benutzen wir, dass es mindestens einenOffline-Algorithmus geben muss, der genauso gut ist wie der Durchschnitt.

Wir betrachten `! verschiedene Offline-Algorithmen. Jeder dieser Algorithmenentspricht einer der `! Permutationen der Liste. Genauer gesagt, ordnet ein solcherOffline-Algorithmus zu Beginn die Liste entsprechend dieser Permutation an undverandert die Ordnung der Liste danach nicht mehr. Das heißt, die Kosten fur einensolchen Offline Algorithmus bestehen aus den Kosten fur diese Umordnung plus denKosten fur das beantworten der Anfragen. Die Kosten fur die Umordnung sind O(`2)(Bubblesort), also eine Konstante, da ` nicht von n abhangt.

Nun berechnen wir die durchschnittlichen Zugriffskosten eines dieser `! Offline-Algorithmen. Dazu mussen wir die Gesamtkosten aller Algorithmen berechnen unddurch `! teilen.

Um die Gesamtkosten zu berechnen, machen wir folgende Beobachtung. Wenn wireinen Zugriff auf einen Datensatz x haben, dann kann x an jeder beliebigen Positionder Liste stehen. Wenn wir nun festhalten, dass x an Position i steht, dann gibt es furdie ubrigen Position noch (`−1)! Moglichkeiten und die Kosten fur die Anfrage vonx sind i. Daher gilt, dass die Gesamtkosten fur eine Anfrage von x genau

`

∑i=1

i · (`−1)! = (`−1)! · ` · (`+1)2

sind. Damit sind die Gesamtkosten fur alle n Anfragen

n · ·(`+1)!2

+ `! ·O(`2) .

Es ergeben sich also Durchschnittkosten von

12

n(`+1)+O(`2) .

Daher gibt es auch einen Offline-Algorithmus, der hochstens diese Kosten hat. Fur n→∞ strebt das Verhaltnis zwischen Online-Kosten und Offline-Kosten gegen 2`/(`+1).

13

Kapitel 3

Selbstanpassende Suchbaume

Im vorherigen Kapitel haben wir die einfache Datenstruktur verkettete Liste furein Worterbuch kennengelernt. Solch eine verkettete Liste ist jedoch keine effizi-ente Implementierung eines Worterbuchs. Daher betrachten wir nun Suchbaume. FurSuchbaumen ist leider eine (nichttriviale) Kompetitive-Analyse noch nicht bekannt.Allerdings werden wir in einem etwas vereinfachten Modell ein erstaunliches Ergebniszeigen: Es gibt Suchbaume, die bei einer beliebigen Anfragesequenz σ asymptotischgenauso gut sind wie ein optimalen statischer Suchbaum fur σ.

Eine Klasse von Suchbaumen mit dieser Eigenschaft sind die so genannten Splay-Baume. Diese benutzen die SPLAY-Operation mit deren Hilfe ein Element des Such-baumes an die Wurzel rotiert wird. Dabei sorgen die Rotationen dafur, dass der Such-baum auf lange Sicht balanciert wird.

x

y

B

C

x

y

C

A

BA

Abbildung 3.1: Beispiel fur eine Rotation

Die Kosten einer Operation entspricht der Anzahl der Vergleiche, die notwendigsind, um das entsprechende Element im Suchbaum zu finden, oder um festzustellen,dass das entsprechende Element nicht im Suchbaum vorhanden ist. Die Kosten fur dieReorganisation des Suchbaumes werden in der Anzahl der dafur notwendigen Rota-tionen gemessen. Es gibt jedoch eine Sonderregel: Ein Element, auf das gerade zuge-griffen wurde, darf umsonst aufwarts rotiert werden. Die Idee dabei ist, dass bei derSuche nach dem entsprechenden Element Zeiger zu den bisher besuchten Positionenaufrecht erhalten werden konnen.

14

3.1 Operationen auf Splay-BaumeFolgende Operationen werden von Splay-Baumen zur Verfugung gestellt.

• SPLAY(x): Dies ist die wichtigste Operation. Mit ihrer Hilfe werden alle ande-ren Operationen implementiert. Eine SPLAY-Operation holt das Element x mitHilfe von Rotationen an die Wurzel des Suchbaumes. Ist das Element x nichtim Suchbaum vorhanden, so wird der Vorganger oder Nachfolger von x an dieWurzel rotiert.

• ACCESS(x): Auf das Element x wird zugegriffen. Diese Operation wird durchSPLAY(x) und Ausgabe der Wurzel realisiert.

• INSERT(x): Beim Einfugen eines Elements wird zunachst eine SPLAY(x)-Operation durchgefuhrt. Diese rotiert den Vorganger oder Nachfolger von x andie Wurzel.

Ist nun die Wurzel r der Nachfolger von x, so wird x Wurzel des neuen Such-baumes. Der linke Teilbaum von r wird zum linken Nachfolger von x und r wirdrechter Nachfolger von x. Ist die Wurzel r der Vorganger von x, so erfolgt dasEinfugen analog.

• DELETE(x): Um ein Element x aus dem Splay-Baum zu loschen wird die-ses zunachst mit der SPLAY(x)-Operation an die Wurzel geholt. Dann wird esgeloscht und die beiden dabei entstehenden Baume werden mit Hilfe von derJOIN-Operation wieder zusammengefugt.

• JOIN(T1,T2): Die JOIN Operation vereinigt zwei Baume T1 und T2 unter derVoraussetzung, dass die Elemente in T1 alle kleiner sind als die Elemente inT2. Bei einem JOIN wird zunachst ein SPLAY(∞) in Baum T1 durchgefuhrt.Damit wird das großte Element aus Baum T1 an die Wurzel rotiert und der rechteTeilbaum unter der Wurzel ist leer. Dort wird nun Baum T2 angehangt.

• SPLIT(x): Auch bei der SPLIT Operation wird zunachst ein SPLAY(x) durch-gefuhrt. Danach sind alle Elemente im linken Unterbaum der Wurzel kleiner alsx und alle Elemente im rechten Unterbaum großer. Je nachdem, ob die Wur-zel kleiner (oder gleich) oder großer als x ist, bleibt sie Wurzel des linken bzw.rechten Teilbaums.

Wir konnen also jede Operation mit Hilfe zweier SPLAY-Operationen und eines kon-stanten Zusatzaufwandes durchfuhren. Daher interessiert uns im folgenden in ersterLinie die SPLAY-Operation.

Bei einer SPLAY(x)-Operation wird zunachst das Element x im Baum gesucht.Ist das Element x nicht im Baum vorhanden, so wird der Vorganger oder Nachfolgervon x mit x identifiziert. Dann wird x mit Hilfe von Rotationen an die Wurzel desBaumes bewegt. Dabei unterscheiden wir je nach Baumstruktur zwischen drei Fallen,die jeweils auch gespiegelt auftreten konnen.

15

1. Ist x ein Kind der Wurzel des Suchbaumes, so wird es mit Hilfe einer Rotationhoher bewegt.

x

y

B

C

x

y

C

A

BA

Abbildung 3.2: Fall 1

2. Ist x auf dem linken Grat des Suchbaumes, so wird es mit Hilfe zweier Rotatio-nen (erst um z, dann um y) hoher bewegt.

A B

C

Dx

y

z x

y

zB

C D

A

Abbildung 3.3: Fall 2

3. Ansonsten kann noch folgender Fall auftreten. x wird mit Hilfe zweier Rotatio-nen (erst um y, dann um z) hoher bewegt.

A

B C

DA C DB

z

y

x

x

yz

Abbildung 3.4: Fall 3

3.2 Analyse der SPLAY-OperationWir wollen nun die amortisierten Kosten von SPLAY(x) analysieren. Dazu fuhren wireine Potentialfunktion Φ ein, die uns das Potential eines Splay-Baumes T angibt. Wirnehmen an, dass jeder Knoten x ein positives Gewicht w(x) besitzt (zunachst setzen wirw(x) = 1; spater werden wir jedoch auch andere Gewichte betrachten). Dann konnen

16

wir das Gewicht eines Teilbaumes definieren, wobei wir einen Teilbaum mit seinerWurzel identifizieren:

W (x) = ∑Knoten y im Teilbaum von x

w(y) .

Der Rang r(x) von x ist dann

r(x) = log2W (x) .

Letztendlich konne wir dann das Potential eines Splay-Baumes T definieren:

Φ(T ) = ∑Knoten x in T

r(x) .

Betrachten wir nun eine Sequenz σ = σ1 · · ·σm von Operationen. Die amortisiertenKosten ai von Operation σi sind die tatsachlichen Kosten ci von σi plus die Potenti-alveranderung, die durch σi verursacht worden ist. Im vorherigen Kapitel haben wirschon gesehen, dass dann die tatsachlichen Kosten der Sequenz σ hochstens die amor-tisierten Kosten von σ plus das Anfangspotential der Datenstruktur sind, d.h.:

m

∑i=1

ci ≤m

∑i=1

ai +Φ(T ) ,

wobei T der initiale Suchbaum ist. Als erstes wollen wir nun die amortisierten Kosteneiner SPLAY-Operation analysieren.

Lemma 3.1 Die amortisierten Kosten von SPLAY(x) betragen hochstens 1+3(r(t)−r(x)), wobei t die Wurzel des Baumes vor der Operation ist.

Beweis. Wir teilen die SPLAY-Operation in eine Sequenz von Schritten auf. Dabeiist jeder Schritt gerade einer der drei oben beschriebenen Falle, die bei einer SPLAY-Operation auftreten konnen. Wir betrachten nun per Fallunterscheidung die amortisier-ten Kosten eines Schrittes. Dabei bezeichnet r(y) den Rang von einem Knoten y vordem Schritt und r′(y) den Rang von y nach dem Schritt.

x

y

B

C

x

y

C

A

BA

Abbildung 3.5: Fall 1

Behauptung 3.2 Im Fall 1 betragen die amortisierten Kosten hochstens 1+3(r′(x)−r(x)).

17

Beweis. Weil eine Rotation benotigt wird, betragen die amortisierten Kosten

1+ r′(x)+ r′(y)− r(x)− r(y) = 1+ r′(y)− r(x) ,

da r′(x) = r(y) ist. Weil r′(y)≤ r′(x) ist, folgt

1+ r′(y)− r(x)≤ 1+ r′(x)− r(x) .

Da r′(x)≥ r(x) ist, folgt dann

1+ r′(x)− r(x)≤ 1+3(r′(x)− r(x)) .

A B

C

Dx

y

z x

y

zB

C D

A

Abbildung 3.6: Fall 2

Behauptung 3.3 Im Fall 2 betragen die amortisierten Kosten hochstens 3(r′(x)−r(x)).

Beweis. Weil zwei Rotationen benotigt werden, betragen die amortisierten Kosten

2+ r′(x)+ r′(y)+ r′(z)− r(x)− r(y)− r(z) = 2+ r′(y)+ r′(z)− r(x)− r(y) ,

da r′(x) = r(z) ist. Weil r′(x)≥ r′(y) und −r(x)≥−r(y) ist, folgt

2+ r′(y)+ r′(z)− r(x)− r(y)≤ 2+ r′(x)+ r′(z)−2r(x) .

Wir zeigen nun, dassr′(z)+ r(x)−2r′(x)≤−2

ist. Damit folgt dann, dass gilt

2+ r′(x)+ r′(z)−2r(x)≤ 3(r′(x)− r(x)) .

Wir setzen nun r′(z) = log2W ′(z) und r′(x) = log2W ′(x) ein und erhalten

r′(z)+ r(x)−2r′(x) = log2W ′(z)+ log2W (x)−2log2W ′(x)

= log2

(W ′(z)W ′(x)

)+ log2

(W (x)W ′(x)

).

Es gilt

log2

(W ′(z)W ′(x)

)+ log2

(W (x)W ′(x)

)≤−2 ,

da links ein Term der Form loga+ logb steht, mit 0 ≤ a,b ≤ 1 und a+ b ≤ 1, daW ′(z) +W (x) ≤W ′(x) ist, und dieser Term loga+ logb nimmt sein Maximum fura = b = 1/2 an.

18

A

B C

DA C DB

z

y

x

x

yz

Abbildung 3.7: Fall 3

Behauptung 3.4 Im Fall 3 betragen die amortisierten Kosten hochstens 3(r′(x)−r(x)).

Beweis. Weil zwei Rotationen benotigt werden, betragen die amortisierten Kosten

2+ r′(x)+ r′(y)+ r′(z)− r(x)− r(y)− r(z)≤ 2+ r′(y)+ r′(z)−2r(x) ,

da r′(x) = r(z) und −r(x)≥−r(y) ist.Wir zeigen nun, dass

r′(z)+ r′(y)−2r′(x)≤−2

ist. Damit folgt dann, dass gilt

2+ r′(y)+ r′(z)−2r(x)≤ 2(r′(x)− r(x))≤ 3(r′(x)− r(x)) ,

da r′(x) ≥ r(x) ist. Wir setzen nun r′(z) = log2W ′(z), r′(y) = log2W ′(y) und r′(x) =log2W ′(x) ein und erhalten

r′(z)+ r′(y)−2r′(x) = log2W ′(z)+ log2W ′(y)−2log2W ′(x)

= log2

(W ′(z)W ′(x)

)+ log2

(W ′(y)W ′(x)

).

Es gilt

log2

(W ′(z)W ′(x)

)+ log2

(W ′(y)W ′(x)

)≤−2 ,

da links ein Term der Form loga+ logb steht, mit 0 ≤ a,b ≤ 1 und a+ b ≤ 1, daW ′(z)+W ′(y) ≤W ′(x) ist, und dieser Term loga+ logb nimmt sein Maximum fura = b = 1/2 an.

Nun beobachten wir noch, dass Fall 1 bei einer SPLAY-Operation nur ein einzigesmal auftritt. Dann folgt mit Hilfe der Teleskopsummenregel, dass die amortisierteneiner SPLAY(x)-Operation hochstens 1+3(r(t)− r(x)) betragen, wobei t die Wurzeldes Baumes vor der Operation ist.

Wir konnen nun folgenden Satz zeigen.

19

Theorem 3.5 Eine Sequenz σ = σ1 · · ·σm von Operationen wird auf einem Splay-Baum, der dabei maximal Große n erreicht, in Zeit O((m+n) logn) abgearbeitet.

Beweis. Sei T der Suchbaum vor der ersten Operation. Wir wissen, dass T hochstensn Knoten hat. Wir setzen fur jeden Knoten x sein Gewicht w(x) = 1. Damit folgt,dass Φ(T ) = O(n logn) ist. Nach Lemma 3.1 gilt, dass die amortisierten Kosten einerSPLAY-Operation hochstens O(1+ r(t)) = O(logn) betragen, wobei t die Wurzel desBaumes vor der Operation ist. Da die amortisierten Kosten plus Anfangspotential eineobere Schranke fur die tatsachlichen Kosten sind, folgt der Satz.

3.3 Statische Optimalitat von Splay-BaumenWir werden nun zeigen, dass Splay-Baume asymptotisch so gut sind, wie ein beliebigerstatischer Suchbaum (der Suchbaum wird wahrend der Anfragen nicht verandert). Wirkonnen also auch den statischen Suchbaum nehmen, der optimal fur eine feste Folgevon Anfragen ist, und dieser optimale statische Suchbaum ware asymptotisch nichtbesser als ein Splay-Baum.

Theorem 3.6 Sei S eine Menge von n Elementen und σ eine Sequenz von Zugriffsope-rationen auf Elemente aus S. Des weiteren sei TS ein beliebiger statischer Suchbaumfur die Elemente aus S und ` die Anzahl Vergleiche, die benotigt werden, um σ auf TSabzuarbeiten. Dann wird σ auf einem Splay-Baum in Zeit O(`+n2) abgearbeitet.

Beweis. Sei T ein beliebiger Splay-Baum fur S und t die Wurzel von T . Sei d die Tiefevon TS und d(x) die Lange des Pfades von der Wurzel von TS zu x. Wir verwenden nunfur jeden Knoten x aus T die Gewichtsfunktion

w(x) = 3d−d(x) .

Wir zeigen zunachst folgende Behauptung.

Behauptung 3.7 W (t)≤ 3d+1.

Beweis. Man kann beobachten, dass das Gewicht der Wurzel t maximal fur einenvollstandigen Binarbaum B ist. Damit ergibt sich

W (t) = ∑x∈S

w(x) = ∑x∈S

3d−d(x) ≤d

∑i=0

2i ·3d−i = 3dd

∑i=0

(23

)i

≤ 3d 11−2/3

= 3d+1 .

20

Aus Lemma 3.1 folgt dann, dass fur die amortisierten Kosten von SPLAY(x) gilt

O(1+ r(t)− r(x)) = O(

1+ log2W (t)W (x)

)= O

(1+ log2

3d+1

3d−d(x)

)= O(1+d(x)) .

Fur das Potential Φ(T ) gilt

Φ(T ) = ∑x∈S

r(x) = ∑x∈S

log2W (x)≤ ∑x∈S

log2 3d+1 = ∑x∈S

O(d) = O(n ·d) = O(n2) .

Da die amortisierten Kosten plus Anfangspotential eine obere Schranke fur dietatsachlichen Kosten sind, folgt der Satz.

21

Kapitel 4

Paging

Beim Paging-Problem geht es darum, dass wir einen Rechner haben, der eine gewis-se Menge an schnellem Speicher (z.B. Cache) zur Verfugung hat. Außerdem gibt eseinen langsamen Sekundarspeicher (z.B. Hauptspeicher), der eine großere Speicher-kapazitat hat. Wir messen die Speicherkapazitat in Seiten, und wir nehmen an, dassunser schneller Speicher Platz fur k Seiten hat.

Wenn nun eine Seite angefragt wird, so muss das System diese Seite im schnellenSpeicher bereit stellen. Ist diese Seite nicht im schnellen Speicher vorhanden, dann trittein Seitenfehler auf, d.h. die Seite muss aus dem langsamen Speicher nachgeladen wer-den und gegebenenfalls muss eine andere Seite aus dem schnellen Speicher verdrangtwerden. Ein Online-Algorithmus muss entscheiden, welche Seite verdrangt wird, ohnedie zukunftigen Anfragen zu kennen. Das Ziel ist es, die Anzahl der Seitenfehler zuminimieren.

4.1 Ein optimaler Offline-AlgorithmusZunachst werden wir die Offline-Variante des Paging-Problems betrachten. Im Gegen-satz zum List-Accessing-Problem werden wir hier einen einfachen optimalen Offline-Algorithmus kennenlernen.

• Longest-Forward-Distance (LFD): LFD verdrangt diejenige Seite, deren nach-ster Zugriff am weitesten in der Zukunft liegt.

Theorem 4.1 LFD ist ein optimaler Offline-Algorithmus fur das Paging-Problem.

Beweis. Wir zeigen, dass jeder optimale Offline-Algorithmus OPT in LFD umgeformtwerden kann, ohne dass zusatzliche Kosten auftreten. Die Umformung wird iterativdurchgefuhrt.

Lemma 4.2 Sei ALG ein beliebiger Paging-Algorithmus und sei σ eine Anfragese-quenz. Dann gibt es einen Offline-Algorithmus ALGi mit den folgenden Eigenschaften:

22

• ALGi verhalt sich bei den ersten i−1 Anfragen genauso wie ALG.

• ALGi verhalt sich bei der i-ten Anfrage wie LFD.

• ALGi(σ)≤ ALG(σ).

Beweis. Fur einen gegebenen Algorithmus ALG werden wir nun einen AlgorithmusALGi konstruieren. Fur die ersten i Anfragen ist ALGi schon definiert. Wir nehmenan, dass ALG und ALGi nach der i-ten Anfrage die Seiten X ∪v bzw. X ∪u imschnellen Speicher haben, wobei X eine Menge von k−1 Seiten ist. Gilt nun u = v, sofolgt das Lemma sofort. Wir nehmen daher an, dass u 6= v ist.

Solange bei den restliche Anfragen nicht die Seite v verlangt wird, verhalt sichALGi wie ALG, bis auf den Fall, dass ALGi die Seite u verdrangt, wenn ALG dieSeite v verdrangt. Dies ist moglich, da die Anzahl der gemeinsamen Seiten immermindestens k−1 ist. Wenn die Anzahl der gemeinsamen Seiten sogar k ist, d.h. ALGverdrangt die Seite v, dann ist von diesem Zeitpunkt an ALGi mit ALG identisch, unddas Lemma folgt.

Wird v angefragt, bevor ALGi mit ALG identisch ist, so hat ALGi einen Seitenfeh-ler und ALG nicht. Da v aber entsprechend LFD verdrangt wurde, muss nach der i-tenAnfrage Seite u mindestens einmal angefragt worden sein. Die erste solche Anfrageverursacht einen Seitenfehler bei ALG aber keinen bei ALGi. Daher ist die Gesamtan-zahl der Seitenfehler von ALGi hochstens so groß wie die von ALG. Um die Anfragebzgl. v zu bedienen, verdrangt ALGi die Seite u, und damit ist von diesem Zeitpunktan ALGi mit ALG identisch, und das Lemma folgt.

Der Satz wird dann wie folgt bewiesen: Das obige Lemma wird auf einen optima-len Offline-Algorithmus OPT mit i = 1 angewandt, und man erhalt OPT1. Dann wirdas obige Lemma auf OPT1 mit i = 2 angewandt, und man erhalt OPT2. Dieses wirdwiederholt, bis man einen optimalen Offline-Algorithmus erhalt, der sich wie LFDverhalt.

4.2 Deterministische AlgorithmenIm folgenden werden deterministische Online-Algorithmen fur das Paging-Problemvorgestellt und einige davon werden analysiert. Alle Strategien verdrangen naturlichnur dann eine Seite im schnellen Speicher, wenn eine Seite angefragt wird, die nichtim schnellen Speicher vorhanden ist.

• Least-Recently-Used (LRU): LRU verdrangt diejenige Seite, deren letzter Zu-griff am langsten zuruckliegt.

• Least-Frequently-Used (LFU): LFU verdrangt diejenige Seite, die am seltenstenangefragt wurde, seit sie im schnellen Speicher ist.

• First-In-First-Out (FIFO): FIFO verdrangt diejenige Seite, die sich am langstenim schnellen Speicher befindet.

23

• Last-In-First-Out (LIFO): LIFO verdrangt diejenige Seite, die als letztes in denschnellen Speicher geladen wurde.

4.2.1 Nicht-kompetitive AlgorithmenEin Online-Algorithmus wird als kompetitiv bezeichnet, falls er eine Kompetitive-Ratio hat, die nicht von der Lange der Eingabesequenz abhangt. Wir werden nun zei-gen, dass LIFO und LFU nicht kompetitive sind.

Theorem 4.3 LIFO ist nicht kompetitive.

Beweis. Sei ` eine positive ganze Zahl. Wir betrachten die Sequenz

σ = p1, . . . , pk,(pk+1, pk)` .

LIFO macht bei jeder Anfrage nach den ersten k Anfragen einen Seitenfehler. OPThingegen behalt einfach die Seiten pk und pk+1 im schnellen Speicher und macht garkeinen Seitenfehler mehr. Da man ` beliebig groß machen kann, ist LIFO nicht kom-petitive.

Theorem 4.4 LFU ist nicht kompetitive.

Beweis. Sei ` eine positive ganze Zahl. Wir betrachten die Sequenz

σ = p`1, . . . , p`k−1,(pk, pk+1)`−1 .

LFU macht bei jeder Anfrage nach den ersten (k−1) · ` Anfragen einen Seitenfehler.OPT hingegen macht nur einen einzigen Seitenfehler. Da man ` beliebig groß machenkann, ist LFU nicht kompetitive.

4.2.2 Marking-AlgorithmenSei σ eine Anfragesequenz. Wir teilen σ wie folgt in k-Phasen auf: Phase 0 ist dieleere Sequenz zu Beginn von σ. Phase i > 0 ist die maximale Sequenz, die direkt aufPhase i− 1 folgt, und in der auf hochstens k verschiedenen Seiten zugegriffen wird.Wir erinnern uns, dass k die Große des schnellen Speichers bezeichnet.

Ein Marking-Algorithmus assoziieren mit jeder Seite im schnellen Speicher einBit, das angibt, ob die jeweilige Seite markiert oder unmarkiert ist. Zu Beginn einerk-Phase werden alle Markierungen geloscht. Wahrend einer k-Phase wird eine Seitemarkiert, wenn auf sie zugegriffen wird. Ein Marking-Algorithmus ist nun dadurch ge-kennzeichnet, dass er niemals markierte Seiten aus dem schnellen Speicher verdrangt.

Theorem 4.5 Jeder Marking-Algorithmus ALG ist k-kompetitiv.

24

Beweis. Wir zeigen zunachst, dass ALG hochstens k Seitenfehler pro Phase macht.Dieses folgt sofort, da jede Seite nach ihrem ersten Zugriff markiert ist und somitnicht mehr aus dem schnellen Speicher entfernt wird. Also kann ALG hochstens einenFehler pro unterschiedlicher Seite in einer Phase machen.

Nun zeigen wir, dass OPT pro Phase (bis auf die letzte Phase) mindestens einenSeitenfehler macht. Sei q die erste Anfrage in Phase i. Wir betrachten die Sequenz, diemit der zweiten Anfrage von Phase i beginnt und bis einschließlich zur ersten Anfrageder Phase i+1 reicht. Zu Anfang dieser Sequenz hat OPT die Seite q und k−1 andereSeiten im schnellen Speicher. In dieser Sequenz gibt es Zugriffe auf k verschiedenenSeiten, die alle ungleich q sind. Also hat OPT mindestens einen Seitenfehler pro Phase(bis auf die letzte Phase).

Also folgtALG(σ)≤ k · (OPT(σ)+1) = k ·OPT(σ)+ k .

Um nun zu zeigen, dass LRU k-kompetitive ist, beweisen wir, dass LRU einMarking-Algorithmus ist.

Theorem 4.6 LRU ist ein Marking-Algorithmus.

Beweis. Annahme: LRU ist kein Marking-Algorithmus. Dann verdrangt LRU wahrendeiner Phase eine markierte Seite x. Wir betrachten den ersten Zugriff auf x in dieserPhase. Hier wird x markiert und x ist zu diesem Zeitpunkt naturlich die Seite, auf die alsletztes zugegriffen wurde. Zum Zeitpunkt, wenn LRU x verdrangt, ist x die Seite, derenZugriff am langsten zuruck liegt. Damit wurden alle k Seiten im schnellen Speicherund die Seite, die den Seitenfehler verursacht, in einer Phase angefragt. Dieses sindaber k+ 1 verschiedene Seiten, was ein Widerspruch ist. Also ist LRU ein Marking-Algorithmus.

Korollar 4.7 LRU ist k-kompetitive.

4.2.3 Deterministische untere SchrankeDie folgende untere Schranke zeigt, dass Marking-Algorithmen optimal sind.

Theorem 4.8 Jeder deterministische Paging-Algorithmus ALG hat eine Kompetitive-Ratio von mindestens k.

Beweis. Wir nehmen an, dass es k+1 verschiedene Seiten gibt. Wir konstruieren eineSequenz von Anfragen σ der Lange n fur die gilt, ALG(σ)≥ k ·OPT(σ). Wir benutzennun wieder den grausamen Gegenspieler, wie bei der unteren Schranke fur das List-Accessing-Problem. Die ersten k Anfragen gehen auf verschiedene Seiten. Danachfordert der grausame Gegenspieler immer genau die Seite an, die nicht im schnellen

25

Speicher von ALG ist. Bei einer Sequenz σ der Lange n hat ALG somit genau n Sei-tenfehler.

Fur den optimalen Offline-Algorithmus LFD hingegen gilt LFD(σ)≤ n/k. Diesessieht man wie folgt: Wir nehmen an, dass LFD bei einer Anfrage die Seite p verdrangt.Entsprechend der Definition von LFD und weil es nur k+1 verschiedene Seiten gibt,mussen alle k Seiten im schnellen Speicher angefragt werden, bevor p wieder angefragtwird. Also macht LFD hochstens einen Seitenfehler alle k Anfragen.

Damit giltALG(σ) = n = k · n

k≥ k ·OPT(σ) .

4.2.4 Unterschiedliche SpeichergroßenUm den Nachteil des Online-Algorithmus auszugleichen, erlaube wir, dass der Online-Algorithmus mehr Ressourcen benutzen darf als der Offline-Algorithmus. Beim Pa-ging bedeutet das, dass der Online-Algorithmus einen schnellen Speicher der Großek besitzt, wahrend der Offline-Algorithmus mit einem schnellem Speicher der Großeh≤ k auskommen muss. Wir haben das Modell also erweitert, denn das bisherige Mo-dell ergibt sich aus dem Fall h = k.

Wir werden nun unsere Ergebnisse bezuglich Marking-Algorithmen auf diesesModell erweitern. Mit dem folgenden Theorem kann man folgern, dass ein Marking-Algorithmus mit doppelt so viel Speicher wie ein optimaler Offline-Algorithmus 2-kompetitive ist.

Theorem 4.9 Sei ALG ein Marking-Algorithmus mit Cachegroße k und OPT ein opti-maler Offline-Algorithmus mit Cachegroße h≤ k. Dann ist ALG k

k−h+1 -kompetitive.

Beweis. Der Beweis ist eine einfache Erweiterung des Beweises von Theorem 4.5.Sei σ eine Anfragesequenz. Wir betrachten wieder die Partitionierung von σ in k-Phasen. Aus dem Beweis von Theorem 4.5 wissen wir bereits, dass ALG hochstens kSeitenfehler pro Phase macht.

Nun zeigen wir, dass OPT pro Phase (bis auf die letzte Phase) mindestens k−h+1Seitenfehler macht. Sei q die erste Anfrage in Phase i. Wir betrachten die Sequenz, diemit der zweiten Anfrage von Phase i beginnt und bis einschließlich zur ersten Anfrageder Phase i+1 reicht. Zu Anfang dieser Sequenz hat OPT die Seite q und h−1 andereSeiten im schnellen Speicher. In dieser Sequenz gibt es Zugriffe auf k verschiedenenSeiten, die alle ungleich q sind. Also hat OPT mindestens k− (h− 1) = k− h + 1Seitenfehler pro Phase (bis auf die letzte Phase).

Also folgt

ALG(σ)≤ k ·(

OPT(σ)k−h+1

+1)=

kk−h+1

·OPT(σ)+ k .

26

4.3 Randomisierte AlgorithmenWie sieht die Kompetitiv-Ratio eines randomisierten Algorithmus aus? Wir werdenhier den so genannten blinden Gegenspieler kennenlernen. Sei ALG ein randomisier-ter Online-Algorithmus. Der blinde Gegenspieler wahlt in Kenntnis des Algorithmus(und seiner Wahrscheinlichkeitsverteilung) eine Eingabesequenz σ aus. Er sieht jedochnicht den Ausgang der Zufallsexperimente (daher blinder Gegenspieler). Wir sagen,dass ALG c-kompetitive ist, wenn fur jede Eingabesequenz σ gilt

E [ALG(σ)]≤ c ·OPT(σ)+α ,

wobei α eine Konstante ist, die nicht von σ abhangt. Genau wie im deterministischenFall bezeichnet die Kompetitiv-Ratio eines randomisierten Online-Algorithmus ALGdas Infimum uber alle Werte c mit der Eigenschaft, dass ALG c-kompetitiv ist.

4.3.1 Randomisierter Marking-AlgorithmusDer randomisierte Marking-Algorithmus Mark assoziieren mit jeder Seite im schnel-len Speicher ein Bit, das angibt, ob die jeweilige Seite markiert oder unmarkiert ist.Zu Beginn einer k-Phase werden alle Markierungen geloscht. Wahrend einer k-Phasewird eine Seite markiert, wenn auf sie zugegriffen wird. Bei einem Seitenfehler ver-drangt Mark eine uniform zufallig ausgewahlte unmarkierte Seite aus dem schnellenSpeicher. Mark ist nun dadurch gekennzeichnet, dass er niemals markierte Seiten ausdem schnellen Speicher verdrangt.

Wir wollen nun zeigen, dass Mark 2Hk-kompetitive ist, dabei bezeichnet Hk diek-te harmonische Zahl, d.h. es ist

Hk =k

∑i=1

1i.

Fur die k-te harmonische Zahl gilt

lnk ≤ Hk ≤ lnk+1 .

Theorem 4.10 Mark ist 2Hk-kompetitive.

Beweis. Sei σ eine Anfragesequenz. Wir betrachten die Partitionierung von σ in k-Phasen. Eine Seite, die direkt zu Beginn einer Phase im schnellen Speicher vorhandenist, wird als alt bezeichnet. Jede nicht alte Seite, die in einer Phase angefragt wird,wird als neu bezeichnet. Beachte, dass wiederholte Anfragen auf alte oder neue Seitendie Kosten von Mark nicht erhohen, da jede Seite, die wahrend einer Phase angefragtwird, bis zum Ende der Phase im schnellen Speicher gehalten wird.

Sei mi die Anzahl neuer Seiten, die in Phase i angefragt werden. Innerhalb ei-ner Phase ist es offensichtlich am schlechtesten fur Mark, wenn zunachst alle neuen

27

Seiten angefragt werden. Die ersten mi Anfragen nach neuen Seiten verursachen miSeitenfehler. Wir untersuchen nun die erwartete Anzahl von Seitenfehlern bezuglichder k−mi Anfragen nach alten Seiten.

Wir betrachten die erste Anfrage nach der j-ten alten Seite p in Phase i. Zu diesemZeitpunkt sind noch k−mi−( j−1) unmarkierte alte Seiten im schnellen Speicher undes gibt insgesamt noch k− ( j−1) unmarkierte alte Seiten (von denen einige im lang-samen Speicher sind). Bei einem Seitenfehler verdrangt Mark eine uniform zufalligausgewahlte unmarkierte Seite aus dem schnellen Speicher. Daher gilt, dass zum Zeit-punkt dieser Anfrage jede unmarkierte alte Seite mit derselben Wahrscheinlichkeit imschnellen Speicher vorhanden ist. Also gilt

Pr [p ist im schnellen Speicher] =k−mi− ( j−1)

k− ( j−1).

Dann folgt

Pr [p ist nicht im schnellen Speicher] = 1− k−mi− ( j−1)k− ( j−1)

=mi

k− j+1.

Damit gilt fur die erwartete Anzahl von Seitenfehlern in Phase i

mi +k−mi

∑j=1

mi

k− j+1= mi +mi · (Hk−Hmi)

= mi · (Hk−Hmi +1)≤ mi ·Hk .

Wir mussen nun noch eine untere Schranke fur die Kosten eines optimalen Offline-Algorithmus OPT finden. In den Phase i−1 und i zusammen werden mindestens k+mi verschiedene Seiten angefragt, d.h. OPT macht mindestens mi Seitenfehler. In derersten Phase macht OPT mindestens m1 Seitenfehler. Dann konnen wir ∑i gerade mi und∑i ungerade mi als untere Schranke fur die Kosten von OPT benutzen. Eine der beidenSummen ist mindestens 1

2 ∑i mi. Also sind die Kosten von OPT mindestens 12 ∑i mi. Da

die erwarteten Kosten von Mark hochstens Hk ∑i mi sind, folgt der Satz sofort.

4.3.2 Randomisierte untere SchrankeDie folgende untere Schranke zeigt, dass Mark asymptotisch optimal ist.

Theorem 4.11 Jeder randomisierte Paging-Algorithmus ALG hat eine Kompetitive-Ratio von mindestens Hk.

Beweis. Wir nehmen an, dass es k+1 verschiedene Seiten gibt. Wir konstruieren eineAnfragesequenz σ. Fur jede Anfrage kann der blinde Gegenspieler die Wahrschein-lichkeit p j ausrechnen, dass die Seite j gerade nicht im schnellen Speicher von ALGvorhanden ist.

28

Die Anfragesequenz σ besteht aus einer beliebig hohen Anzahl von k-Phasen.Der Gegenspieler benutzt zur Konstruktion einer solchen Phase einen Marking-Algorithmus. Im folgenden zeigen wir, wie eine Phase konstruiert wird, und wirzeigen, dass die erwarteten Kosten von ALG fur so eine Phase mindestens Hk betra-gen. Da ein optimaler Offline-Algorithmus so eine Phase mit Kosten eins abarbeitenkann, folgt damit dann das Theorem.

Eine Phase besteht aus k Subphasen. Zu Beginn der i-ten Subphase sind genauk− i+1 unmarkierte Seiten im schnellen Speicher. Am Ende der k-ten Subphase sinddann alle Seiten markiert und eine neue Phase beginnt. Wir konstruieren die Subphasenso, dass die erwarteten Kosten von ALG fur die i-te Subphase 1

k−i+1 betragen. Damitbetragen die erwarteten Kosten von ALG fur eine Phase

k

∑i=1

1k− i+1

= Hk .

Jede Subphase besteht aus null oder mehreren Anfragen nach markierten Seitengefolgt von einer Anfrage nach einer unmarkierten Seite. Wir zeigen nun, wie eineSubphase konstruiert wird. Sei M die Menge der markierten Seiten zu Beginn der i-ten Subphase. Offensichtlich gilt |M| = i und die Anzahl der unmarkierten Seiten istk+1− i. Sei γ = ∑ j∈M p j.

• Falls γ = 0, dann gibt es mindestens eine unmarkierte Seite a mit pa ≥ 1/(k+1− i). In diesem Fall fragt der Gegenspieler Seite a an und die Subphase endet.

• Falls γ > 0, dann gibt es eine Seite m∈M mit pm > 0. Sei ε = pm. Als erstes wirdnun in dieser Unterphase die Seite m angefragt. Solange die erwarteten Kostenvon ALG noch nicht 1/(k+1− i) betragen und solange γ > ε ist, frage die Seiteaus M an, die mit der großten Wahrscheinlichkeit nicht im schnellen Speichervon ALG ist.Wir stellen zunachst fest, dass die obige Schleife terminiert, da γ > ε ist, undsomit jede Iteration mit γ/M > ε/M zu den erwarteten Kosten von ALG beitragt.Wenn die Schleife terminiert, betragen entweder die erwartete Kosten von ALGmindestens 1/(k+1− j) oder es gilt γ≤ ε. Im letzteren Fall fragt der Gegenspie-ler die unmarkierte Seite b an, die mit der großten Wahrscheinlichkeit nicht imschnellen Speicher von ALG ist. Offensichtlich gilt pb ≥ (1− γ)/(k+1− i) undes folgt somit fur die erwarteten Kosten von ALG

ε+ pb ≥ ε+1− γ

k+1− i≥ ε+

1− ε

k+1− i≥ 1

k+1− i.

29

Kapitel 5

Datenmanagement in Netzwerken

Der Kommunikationsoverhead fur die Bereitstellung von Datenobjekten, die von meh-reren Knoten in einem Netzwerk bearbeitet werden konnen, dominiert haufig die Lauf-zeit von Netzwerkanwendungen. Bei solchen Datenobjekten kann es sich zum Beispielum Dateien in einem Local-Area-Network (LAN), globale Variablen auf einem Paral-lelrechner oder auch virtuelle Seiten in einem verteilten Speichersystem handeln.

In der Standardimplementierung solcher Systeme haben Datenobjekte haufig einso genanntes Home, also einen Rechner bzw. Prozessor, der der Ansprechpartner furdieses Objekt ist. In einer naiven Realisierung dieses Konzeptes wird jeder Zugriffauf ein Datum an sein Home geschickt, das dann bei einem Schreibzugriff das Objektentsprechend modifiziert und bei einem Lesezugriff das gesamte Objekt bzw. einenangefragten Ausschnitt der Daten zuruckliefert.

Unter dem Konzept des Cachings versteht man eine raffiniertere Variante, die eserlaubt Kopien des Objektes zu erzeugen, die im Netzwerk verteilt werden. Falls einProzessor haufiger auf dasselbe Datenobjekt zugreifen mochte, ist es vielleicht sinn-voll, wenn dieser Prozessor eine lokale Kopie erhalt, so dass Anfragen von diesemProzessor nicht mehr zum Home gesendet werden mussen. Falls jedoch jetzt ein ande-rer Prozessor dieses Objekt verandern mochte, muss diese Kopie entweder invalidiertoder aktualisiert werden. Es stellen sich die Fragen, wann wir Kopien erzeugen undwann wir sie wieder loschen sollen.

Grundsatzlich scheint es sogar moglich und sinnvoll zu sein, das Home eines Pro-zessors zu verschieben, oder sogar das Home-Konzept ganz aufzugeben und verschie-dene gleichrangige Kopien im Netzwerk wandern zu lassen. In einem derartig dyna-mischen System, stellt sich naturlich auch die Frage, wie die anfragenden Knoten, dieim Netzwerk verteilten Kopien, lokalisieren konnen, ohne dazu das gesamte Netzwerkabzusuchen. Diese und andere Fragestellungen werden wir im Folgenden schrittweisebeantworten.

30

5.1 Definition des File-Allocation-Problems (FAP)Das Netzwerk wird durch einen ungerichteten Graphen G = (V,E) mit nicht-negativenKantenlangen aus R beschrieben. Wir betrachten nur ein Datenobjekt x auf das vonallen Prozessoren im Netzwerk lesend und schreibend zugegriffen werden kann. Esdurfen beliebig viele Kopien von x erzeugt werden. Die Teilmenge der Knoten, die zueinem Zeitpunkt t ≥ 0 eine Kopie von x besitzen wird als Residenzmenge Rt ⊆V,Rt 6= /0

bezeichnet. Zum Zeitpunkt 0 gilt R0 = v fur einen beliebigen Knoten v ∈ V . Wirvernachlassigen zunachst das Problem, wie die Kopien im Netzwerk lokalisiert werdenkonnen und setzen globales Wissen uber die Residenzmenge voraus, d.h. zu jedemZeitpunkt t kennt jeder Knoten die Menge Rt .

Auf dem Netzwerk muss eine Sequenz von Lese- und Schreibanfragen σ =σ1 · · ·σT , mit σt ∈ r(v),w(v)|v ∈ V, abgearbeitet werden. Dabei steht σt = r(v)fur eine Leseanfrage von Prozessor v und σt = w(v) fur eine Schreibanfrage von v.Dabei mussen die folgenden Spielregeln eingehalten werden. Nachdem σt prasentiertist, fuhrt der Algorithmus die Anfrage durch. Wir kummern uns nicht um die De-tails der Durchfuhrung, sondern definieren stattdessen abstrakte Servicekosten fur dieeinzelnen Zugriffe.

• Falls σt = r(v) ist, dann entsprechen die Servicekosten der Distanz von v zumnachsten Knoten in Rt−1.

• Falls σt = w(v) ist, dann entsprechen die Servicekosten den Kosten des mini-malen Steinerbaumes, der v und Rt−1 aufspannt, also der minimalen Summe derKantenlangen, die benotigt wird, um v durch einen Baum mit allen Knoten inRt−1 zu verbinden.

Nachdem die Anfrage σt bedient wurde, kann die Residenzmenge angepasst werden,also Rt−1 in Rt uberfuhrt werden. Dazu durfen neue Kopien erzeugt oder auch vorhan-dene Kopien verschoben und geloscht werden. Es muss jedoch immer mindestens eineKopie im Netzwerk erhalten bleiben. Das Erzeugen neuer Kopien sowie das Loschenverursacht keine Kosten. Jedoch durfen neue Kopien nur auf solchen Knoten erzeugtwerden, die schon eine Kopie haben. Die neue Kopie kann dann entlang der Kantenverschoben werden. Das Verschieben einer Kopie entlang einer Kante der Lange `verursacht dabei Migrationskosten in Hohe von `.

5.2 FAP auf BaumenSei der betrachtete Graph ein Baum T = (V,E). Wir prasentieren einen einfachen 3-kompetitiven Online-Algorithmus. Dieser Algorithmus hat die folgende Invariante. Zujedem Zeitpunkt t ≥ 0 ist der durch die Residenzmenge induzierte Teilgraph zusam-menhangend. Fur v ∈V und t ≥ 0 bezeichne Pt(v) die Knoten auf dem kurzesten Weg,der vom Knoten v zur Residenzmenge Rt fuhrt, inklusive des Quell- und Zielknotens

31

dieses Weges. Nach der Durchfuhrung der Anfrage σt verandert der Algorithmus dieResidenzmenge wie folgt.

• Falls σt = r(v) ist, dann Rt := Rt−1∪Pt−1(v).

• Falls σt = w(v) ist, dann Rt := Pt−1(v).

Im Falle einer Leseanfrage durch v erzeugt der Online-Algorithmus also neue Kopienauf dem Weg Pt−1(v), und im Falle einer Schreibanfrage von v loscht er die Kopien inRt−1 und erzeugt neue Kopien auf Pt−1(v). Beachte, falls v ∈ Rt−1 ist, so gibt es nacheiner Schreibanfrage von v nur noch eine Kopie, namlich die Kopie auf dem Knoten v.

Theorem 5.1 Der Online-Algorithmus fur FAP auf Baumen ist 3-kompetitive.

Beweis. Betrachte eine beliebige Kante e = (a,b). O.B.d.A. hat die Kante die Lange1. Die Entfernung von e aus T wurde den Graphen in zwei Teilbaume Ta und Tb zer-legen, die jeweils die Knoten a bzw. b enthalten. Wir unterscheiden drei verschiedeneKonfigurationen.

[A] Nur Ta enthalt Kopien von x.

[B] Nur Tb enthalt Kopien von x.

[AB] Beide Teilbaume enthalten Kopien.

Beachte, dass in der Konfiguration [AB] garantiert ist, dass beide Knoten a und bjeweils eine Kopie haben mussen, weil ansonsten die Residenzmenge nicht zusam-menhangend ware. Sei ct ∈ [A], [B], [AB] die Konfiguration zum Zeitpunkt t. DerSchritt von ct−1 nach ct wird als Konfigurationsubergang bezeichnet. Die folgendeBehauptung kann beobachtet werden.

Behauptung 5.2 Der Online-Algorithmus geht niemals in einem Schritt von der Kon-figuration [A] direkt in die Konfiguration [B] uber und umgekehrt. Es gibt nur dieUbergange [A]→ [AB], [B]→ [AB], [AB]→ [A] und [AB]→ [B].

Damit konnen wir die Konfigurationssequenz in disjunkte Phasen der Form[A]+[AB]+ bzw. [B]+[AB]+ einteilen. Wir betrachten nun eine derartige Phase undvergleichen die Kosten des Online-Algorithmus mit den Kosten eines beliebigenOffline-Algorithmus.

• Zunachst zeigen wir, dass der Online-Algorithmus auf Kante e pro Phase Kostendrei hat. O.B.d.A. betrachte eine Phase der Form [A]+[AB]+. Die Beschreibungder in solch einer Phase entstehenden Online-Kosten in der Tabelle 5.1 bestatigtunsere Behauptung.

• Als nachstes zeigen wir, dass jeder Offline-Algorithmus mindestens Kosten einspro Phase hat. Zum Zwecke des Widerspruchs nehmen wir an, es gibt eine Strate-gie mit Kosten null. Dann erfordert die Schreibanfrage (*) aus Ta, dass zu diesem

32

vorherige Konf. Konf. Art des Zugriffs Online-Kosten[AB] [A] Schreibanfrage aus Ta (*) 1[A] [A] Lese-/Schreibanfrage aus Ta 0[A] [AB] Lese-/Schreibanfrage aus Tb (**) 2[AB] [AB] Leseanfrage aus Ta oder Tb 0

Abbildung 5.1: Online-Kosten auf einer Kante in einer Phase der Form [A]+[AB]+.

Zeitpunkt keine Kopie in Tb enthalten ist, sonst waren die Kosten mindestens eins.Außerdem kann keine Kopie migriert werden. Also ist auch zum Zeitpunkt derLese-/Schreibanfrage (**) aus Tb keine Kopie in Tb enthalten. Damit verursachtdieser Zugriff jedoch mindestens Kosten eins.

Also hat jeder Offline-Algorithmus mindestens Kosten eins pro Phase, wahrendder Online-Algorithmus nur Kosten drei hat. Somit ist der Online-Algorithmus 3-kompetitive.

Verteilte Ausfuhrung. Bisher sind wir von globalem Wissen ausgegangen. Wir ha-ben angenommen, dass alle Knoten die Konfiguration des Netzwerks kennen. Jetztbeziehen wir eine verteilte Ausfuhrung in unser Modell mit ein. Wir gehen davon aus,dass die einzelnen Knoten im Netzwerk nur diejenigen Zugriffe sehen, in die sie invol-viert sind. Genauer gesagt, ein Knoten sieht einen Lesezugriff nur dann, wenn er aufdem gewahlten Weg zur Zusammenhangskomponente liegt. Analog wird ein Schreib-zugriff nur von denjenigen Knoten wahrgenommen, die im fur die Aktualisierung oderInvalidierung der Kopien verwendeten Baum enthalten sind. Auch Migrationen wer-den nur von Knoten, die auf dem Migrationspfad liegen, beobachtet. Um Informatio-nen uber eine Veranderung der Residenzmenge auch an andere Knoten im Netzwerk zugeben, mussen Informationsnachrichten versendet werden. Im folgenden zeigen wir,dass Informationsnachrichten fur die verteilte Ausfuhrung nicht benotigt werden.

Theorem 5.3 Es gibt einen verteilten 3-kompetitiven Online-Algorithmus fur FAP aufBaumen.

Beweis. Wir verwenden eine verteilte Variante des Online-Algorithmuns fur FAP aufBaumen. Wir werden zeigen, wie das so genannte Data-Tracking, d.h. die Lokalisie-rung der Residenzmenge, auch ohne globales Wissen realisiert werden kann.

Wir erklaren einen beliebigen Knoten zur Wurzel des Baumes, z.B. den Knotender die initiale Kopie des Datenobjektes halt. Der Algorithmus halt die folgende In-variante aufrecht. Zu jedem diskreten Zeitpunkt gibt es eine Kette von Zeigern aufdem Weg von der Wurzel zur Residenzmenge, d.h. jeder Knoten auf dem Weg von derWurzel zur Residenzmenge kennt seinen Nachfolger auf diesem Weg. Somit kann jedeLese-/Schreibanfrage auf dem kurzesten Weg zur Residenzmenge gelangen, indem dieentsprechende Nachricht zunachst in Richtung Wurzel des Baumes lauft und dann den

33

Zeigern zur Residenzmenge folgt. Beachte, dass diese Zeiger im Falle einer Migrationohne weitere Kommunikation aktualisiert werden konnen, da die betroffenen Knotenauf dem Migrationspfad liegen und somit die Migration beobachten konnen.

Fur Schreibzugriffe muss nicht nur ein sondern alle Knoten der Residenzmenge lo-kalisiert werden. Dazu speichern die Knoten in der Residenzmenge jeweils ab, welcheNachbarn ebenfalls zur Residenzmenge gehoren.

5.3 Deterministische untere Schranke fur FAPDie folgende untere Schranke zeigt, dass der obige Online-Algorithmus fur FAP aufBaumen optimal ist, denn selbst auf einer einzelnen Kante kann man keinen besserenFaktor als drei erreichen.

Theorem 5.4 Betrachte FAP auf einer Kante (a,b) der Lange eins. Jeder determini-stische Online-Algorithmus ALG hat eine Kompetitive-Ratio von mindestens drei.

Beweis. Die jeweils zuletzt erzeugte Kopie von ALG bezeichnen wir als neueste Kopie.Wir betrachten die folgenden drei Offline-Strategien.

• Strategie A halt immer eine Kopie auf a.

• Strategie B halt immer eine Kopie auf b.

• Strategie C halt immer eine Kopie auf demjenigen Knoten, auf dem sich nicht dieneueste Kopie von ALG befindet.

Ein grausamer Gegenspieler konstruiert wie beim Paging die Anfragesequenz σ.

• Wenn ALG auf einem Knoten x ∈ a,b keine Kopie hat, dann folgt als nachsteseine Leseanfrage r(x).

• Wenn ALG auf beiden Knoten a und b Kopien hat, dann folgt als nachstes eineSchreibanfrage w(x), wobei x derjenige Knoten ist, auf dem sich nicht die neusteKopie von ALG befindet.

Die Offline-Strategien A und B haben keine Migrationskosten. Die Migrationsko-sten der Offline-Strategie C entsprechen genau den Migrationskosten von ALG. Alsohaben die drei Offline-Strategien zusammen dieselben Migrationskosten wie ALG. Beiden Servicekosten ist die Situation ahnlich. ALG hat in jedem Schritt Servicekosteneins. Dasselbe gilt fur die drei Offline-Strategien zusammen. Also gilt

ALG(σ) = A(σ)+B(σ)+C(σ)≥ 3 ·OPT(σ) .

34

5.4 FAP auf allgemeinen GraphenAuf allgemeinen Graphen ist ein dynamisches Datenmanagement wesentlich komple-xer als auf Baumnetzwerken, da die Wege zwischen Knoten nicht mehr eindeutig sind,und somit auch die Wahl der Routingwege in das Problem einbezogen werden muss.Dieser Aspekt erschwert das Datenmanagement in fast jeder Hinsicht, angefangen beider Platzierung der Kopien bis hin zum Data-Tracking. Wir losen dieses Problem in-dem wir die zuvor beschriebenen Baumalgorithmen auf anderen Netzwerken simulie-ren. Dazu werden wir eine Methode vorstellen, allgemeine Metriken durch so genannteBaummetriken zu approximieren. Diese Methode kann nicht nur auf FAP sondern auchauf zahlreiche andere Optimierungsprobleme angewendet werden. Die Voraussetzungist, dass sich die Gesamtkosten einer Losung als Linearkombination der Kosten ein-zelner Kanten beschreiben lasst.

5.4.1 Deterministische Approximation von MetrikenWie auch bei vielen anderen Problemen, basiert das Kostenmodell fur FAP auf denDistanzen zwischen Knoten in einem Graphen G = (V,E) mit nicht-negativen Kan-tenlangen. Die konkrete Graphtopologie ist dabei unwesentlich. Um die Kosten zuermitteln, wird eigentlich nur die durch G erzeugte Metrik M benotigt. Fur jedes Kno-tenpaar u,v∈V beschreibt M die Distanz dM(u,v) zwischen u und v. Allgemein erfullteine Metrik M uber einer Knotenmenge V die folgenden Bedingungen:

• Fur alle u,v ∈V gilt: dM(u,v)≥ 0 (Nicht-Negativitat)

• Fur alle u,v ∈V gilt: dM(u,v) = dM(v,u) (Symmetrie)

• Fur alle u,v,w ∈V gilt: dM(u,w)≤ dM(u,v)+dM(v,w) (Dreiecksungleichung)

Im Folgenden definieren wir, was es bedeutet, eine Metrik durch eine andere Me-trik zu approximieren. Eine Metrik N uber V dominiert eine Metrik M uber V , fallsfur jedes u,v ∈V gilt dN(u,v)≥ dM(u,v). Eine Metrik N uber V α-approximiert eineMetrik M uber V , falls sie M dominiert und fur alle u,v ∈V gilt dN(u,v)≤ αdM(u,v).

Eine Metrik N uber V ist eine Baummetrik, falls es einen Baum T = (V,E) gibt,der die Metrik N erzeugt. Wir mochten allgemeine Metriken durch Baummetrikenapproximieren. Die folgende untere Schranke zeigt, dass dies deterministisch nichtsinnvoll funktionieren kann.

Theorem 5.5 Fur jedes n ∈ N gibt es eine Metrik M uber n Knoten, so dass fur jedeBaummetrik N uber n Knoten gilt, falls M durch N α-approximiert wird, gilt α=Ω(n).

Beweis. Sei G = (V,E) der Kreis uber n Knoten. Insbesondere sei V = 0, . . . ,n−1und E = (i, j)|i = j + 1 mod n. Alle Kanten in G haben Lange 1. G erzeuge dieMetrik M. T = (V,ET ) bezeichne den Baum, der N erzeugt. Zur Vereinfachung der

35

Notation nehmen wir an, dass n gerade ist, und dass α < n4 eine ganze Zahl ist. Zum

Zwecke des Widerspruchs nehmen wir an, dass N eine α-Approximation von M ist.Zuerst zeigen wir, dass jede Kante in ET hochstens Lange α hat. Zum Zwecke des

Widerspruchs nehmen wir an, dass es eine Kante e = (a,b) ∈ ET mit Lange großer alsα gibt. Dann gibt es zwei Teilbaume Ta und Tb, so dass fur jedes Knotenpaar (u,v) mitu aus Ta und v aus Tb gilt dN(u,v) > α. Da N die Metrik M α-approximiert, konnenNachbarn im Kreis aber hochstens Abstand α im Baum haben. Also sind entweder alleKnoten aus V im Teilbaum Ta oder alle im Teilbaum Tb enthalten. Ein Widerspruch.

Jetzt definieren wir zwei Knotenmengen A = 0, . . .α− 1 und B = n2 , . . .

n2 +

α− 1. Nun farben wir die Knoten in V \ (A∪B) mit zwei Farben. Die Knoten inα, . . . n

2 − 1 werden blau gefarbt und die Knoten in n2 + α, . . .n− 1 werden rot

gefarbt. Beachte, zwischen je einem blauen und einem roten Knoten ist die Distanz imKreis großer als α. Somit folgt, dass es keine Kante (u,v)∈ ET zwischen einem blauenKnoten u und einem roten Knoten v geben kann, weil sonst dM(u,v) > α ≥ dN(u,v)gelten wurde, was im Widerspruch zur Dominanz von N uber M stunde. Wir fassenzusammen: Zwischen roten und blauen Knoten gibt es keine Kante in ET .

Sei a ∈ A und b ∈ B. Im Kreis haben a und b die Distanz n2 −α≥ n

4 . Aufgrund derDominanz von N uber M folgt, dass die Entfernung im Baum nicht geringer sein darf.Sei a 6= a′ ∈ A. b kann nicht auf dem Pfad liegen, der a und a′ in T verbindet, den sonstgabe es zwei Knoten in A, die im Kreis benachbart sind, aber im Baum mindestensDistanz n

4 hatten. Die α-Approximation erlaubt jedoch hochstens eine Distanz von α<n4 fur im Kreis benachbarte Knoten. Mit dieser Eigenschaft konnen wir nun die WalderTA und TB definieren: TA bzw. TB enthalt die vollstandigen Teilbaume, die jeweils eineWurzel aus A bzw. B haben, aber die keinen Knoten aus B bzw. A enthalten.

Wenn wir TA und TB aus T entfernen wurden, so bleibt ein zusammenhangenderRestbaum R uber. Per Definition besteht R nur aus gefarbten Knoten. Tatsachlich be-steht R entweder nur aus blauen oder nur aus roten Knoten, denn sonst wurde es in Rein benachbartes Paar Knoten mit unterschiedlichen Farben geben. O.B.d.A. konnenwir also annehmen das R nur aus roten Knoten besteht.

Die blauen Knoten sind entweder alle in TA oder in TB enthalten, denn sonst gabees zwei blaue im Kreis benachbarte Knoten, die im Baum mindestens Distanz n

4 hatten.Die α-Approximation erlaubt jedoch hochstens eine Distanz von α < n

4 fur im Kreisbenachbarte Knoten. O.B.d.A. konnen wir also annehmen alle blauen Knoten sind inTA enthalten.

Jetzt betrachte das Knotenpaar u = n2 −1 und v = n

2 . Im Baum finden wir u in TA,da er zu den blauen Knoten gehort, und v in TB, da er zur Menge B gehort. Es folgtdN(u,v) ≥ n

4 > α. Aus der Nachbarschaft auf dem Kreis folgt jedoch dM(u,v) = 1.Also erhalten wir einen Widerspruch zur α-Approximation von M durch N.

36

5.4.2 Probabilistische Approximation von MetrikenEine probabilistische α-Approximation einer Metrik M uber V durch Baummetrikenist definiert durch eine Menge von Baummetriken S uber V mit einer assoziiertenWahrscheinlichkeitsverteilung P : S → [0,1], die die folgenden Bedingungen erfullt:

• Jede Baummetrik N ∈ S , dominiert die Metrik M.

• Fur ein zufallig gemaß P gewahltes N ∈ S gilt: E [dN(u,v)]≤ α ·dM(u,v) fur alleu,v ∈V .

Bartal hat gezeigt, dass es fur jede Metrik M uber eine Knotenmenge V eine pro-babilistische O(log |V | log log |V |)-Approximation durch Baummetriken gibt. Das fol-gende leicht verbesserte Ergebnis geht zuruck auf Fakcharoenphol, Rao und Talwar.

Theorem 5.6 Fur jede Metrik M uber eine Knotenmenge V gibt es eine probabilisti-sche O(log |V |)-Approximation durch Baummetriken.

Dieses Ergebnis ist optimal, denn es gibt eine Metrik M fur die es nachweisbar kei-ne probabilistische o(log |V |)-Approximation durch Baummetriken gibt. Wir werdendiesen Satz nicht in seiner Allgemeinheit beweisen, sondern uns die grundlegende Be-weisidee anhand eines relativ einfachen Beispiels klarmachen. Als Beispiel betrachtenwir die Metrik M, die durch den zwei-dimensionalen (n× n)-Torus G = (V,E), mitV = 0, . . .n−12,

E = (x,y),((x+1) mod n,y),(x,y),(x,(y+1) mod n)|(x,y) ∈V

und uniformen Kantenlangen, erzeugt wird.

Theorem 5.7 Sei n = 2d . Fur die (n×n)-Torusmetrik M uber V = 0, . . .n−12 gibtes eine probabilistische 8d-Approximation durch Baummetriken.

Beweis. Durch eine hierarchische Partitionierung des Torus definieren wir zunachsteinen Dekompositionsbaum. Dazu teilen wir den Torus in vier disjunkte (n

2 ×n2)-

Teilgitter, die wiederum rekursiv in vier disjunkte, quadratische Teilgitter aufgeteiltwerden, bis wir einzelne Knoten erreichen. Mit dieser Partitionierung ist ein 4-arerDekompositionsbaum der Tiefe d verbunden, in dem die Wurzel den gesamten Torusund jeder Knoten auf Ebene i ∈ 1, . . .d dieses Baumes jeweils ein Teilgitter mitSeitenlange n/2i reprasentiert.

In jedem dieser Teilnetzwerke wahlen wir jetzt iterativ einen Leiter. Wir beginnenmit den Teilgittern auf Ebene d des Dekompositionsbaumes. Als Leiter solch einesTeilgitters, das nur aus einem Knoten besteht, wahlen wir diesen einen Knoten. Nach-dem wir die Leiter auf Ebene i∈ 1, . . .d bestimmt haben, widmen wir uns der Ebenei−1. Als Leiter eines Teilgitters S auf Ebene i−1 wahlen wir einen beliebigen Knotenaus der Menge der Leiter der Teilgitter auf Ebene i, in die S partitioniert wird. DieDistanz dieses Leiters zu einem beliebigen Knoten in S ist durch 2n/2i−1 beschrankt.

37

Wir beschriften nun die Knoten des Dekompositionsbaumes. Jeder Baumknotenerhalt das Label des Leiters im jeweiligen Teilgitter. Beachte, dass einzelne Labelim Baum mehrfach vorkommen konnen, wahrend sie im Torus eindeutig sind. Alsnachstes weisen wir den Baumkanten Distanzwerte zu. Eine Kante zwischen zweiBaumknoten mit Label u und v erhalt die Distanz der gleichnamigen Knoten im Torus-netzwerk. Kanten, deren inzidente Knoten dasselbe Label tragen, erhalten dabei denDistanzwert 0.

Wenn wir nun Baumknoten mit gleichem Label miteinander identifizieren, so er-halten wir eine Baummetrik N uber V = 0, . . .n−12, die die Torusmetrik M domi-niert, weil fur jede Kante im Baum ein Weg gleicher Lange im Torus existiert, so dassgilt dM(u,v)≤ dN(u,v) fur alle u,v ∈V . Beachte, dass diese Aussage gilt, weil wir dieLeiter so gewahlt haben, dass der Graph, der jeweils durch Baumknoten mit gleichemLabel induziert wird, zusammenhangend ist.

Die oben beschriebene Dekomposition ist nicht eindeutig, da wir die Koordinatender Partionierung auf der obersten Rekursionsebene nicht festgelegt haben. Tatsachlichgibt es n2 Moglichkeiten fur die Partitionierung auf der obersten Rekursionsebene. So-bald dieser erste Partionierungsschritt jedoch festgelegt ist, sind auch die nachrangigenPartionierungen eindeutig bestimmt. Tatsachlich erhalten wir also eine Familie von n2

Dekompositionsbaumen mit verschiedenen Beschriftungen von denen jeder eine un-terschiedliche Baummetrik uber V erzeugt, die die Torusmetrik M dominiert. Um eineprobabilistische Approximation von M zu erhalten, definieren wir jetzt, dass die MengeS eben aus diesen n2 verschiedenen Baummetriken besteht. Als Wahrscheinlichkeits-verteilung uber S wahlen wir die uniforme Verteilung.

Wir mussen nun die erwartete Distanz zwischen zwei beliebigen Knoten aus Vbezuglich einer zufallig aus S gewahlten Metrik N abschatzen und beweisen, dass dieerwartete Distanz in N hochsten 8d mal so groß ist wie die Distanz in der TorusmetrikM. Seien u = (u1,u2) und v = (v1,v2) beliebig gewahlte Knoten aus V . Bezeichne δ1die Distanz zwischen diesen beiden Knoten bezuglich der ersten Koordinate (Zeilen)im Torus und δ2 die Distanz bezuglich der zweiten Koordinate (Spalten). Um eine obe-re Schranke fur dN(u,v) zu erhalten, ist es jetzt sinnvoll sich den Dekompositionsbaumwieder als vollstandigen 4-aren Baum der Tiefe d vorzustellen. Wir identifizieren u undv mit den Blattern, die das entsprechende Label tragen.

Die Wahrscheinlichkeit, dass u und v durch die horizontale Partitionierung des To-rus auf der obersten Rekursionsebene getrennt werden, ist hochstens 2δ1/n, da auf die-ser Ebene zwei horizontale Schnitte vorgenommen werden, und jeder dieser Schnitteeine der δ1 Kantenschichten, die zwischen den Zeilen von u und v liegen, mit Wahr-scheinlichkeit δ1/n durchtrennt. Fur die vertikale Partitionierung ist die entsprechendeWahrscheinlichkeit hochstens 2δ2/n. Bezogen auf den Dekompositionsbaum schlie-ßen wir, dass der kurzeste Weg zwischen u und v die Wurzel mit Wahrscheinlich-keit hochstens 2(δ1 + δ2)/n enthalt. Allgemein gilt, die Wahrscheinlichkeit, dass derkurzeste Weg zwischen den beiden Knoten u und v einen Knoten von Ebene i desDekompositionsbaumes enthalt, ist hochstens 2i+1 · (δ1 + δ2)/n, da 2i+1 horizontale

38

und 2i+1 vertikale Schnitte vorgenommen werden, die zur Aufteilung von u und v inverschiedene Teilbaume unterhalb der Ebene i fuhren.

Daraus berechnen wir jetzt welche Baumkanten mit welcher Wahrscheinlich-keit uberschritten werden. Wir definieren, dass die Baumkanten auf Schicht i furi ∈ 0, . . .d− 1 zwischen den Knoten der Ebene i und den Knoten der Ebene i+ 1verlaufen.

• Mit Wahrscheinlichkeit hochstens 2i+1 · (δ1 + δ2)/n fuhrt der kurzeste Weg vonu nach v uber Kantenschicht i.

• Von jeder Kantenschicht werden maximal zwei Kanten benutzt.

• Die Kanten aus Schicht i haben Lange hochsten 2n/2i.

Daraus errechnet sich

E [dN(u,v)] =d−1

∑i=0

2i+1 · (δ1 +δ2)

n·2 · 2n

2i = 8d · (δ1 +δ2) = 8d ·dM(u,v) .

5.4.3 Randomisierter Online-AlgorithmusAus der obigen Approximation von allgemeinen Metriken durch Baummetriken kon-struieren wir einen randomisierten Algorithmus fur FAP auf allgemeinen Graphen. Derrandomisierte Online-Algorithmus fur FAP auf einem Graphen G= (V,E) arbeitet wiefolgt. Sei M die durch G erzeugte Metrik. In einem Preprocessing wird die fur eine α-Approximation von M benotigte Menge von Baummetriken S sowie die zugehorigeWahrscheinlichkeitsverteilung P berechnet. Eine zufallige Baummetrik N wird aus Sgemaß P gewahlt und ein Baum T = (V,ET ) wird konstruiert, der diese Metrik er-zeugt. Dann wird der in Satz 5.3 beschriebenen 3-kompetitiven Baumalgorithmus Afur T simuliert.

Lemma 5.8 Der obige Algorithmus ist 3α-kompetitive.

Beweis. Fixiere eine Anfragesequenz σ. Fur einen Algorithmus B und eine Metrik Qbezeichne CQ

B die Kosten von B auf σ unter Q. Wir werden beweisen, dass fur jedenAlgorithmus B gilt E

[CM

A]≤ 3α ·CM

B . Aus dieser Behauptung folgt unmittelbar, dassder Algorithmus 3α-kompetitive ist.

Sei B nun ein beliebiger Algorithmus. Die Gesamtkosten beim FAP lassen sichals eine Linearkombination von Kosten einzelner Kanten interpretieren. Insbesonderekonnen wir die Kosten von B auf die Knotenpaare umlegen, d.h. wir konnen jedemKnotenpaar u,v ∈ V einen absoluten Kostenwert CB(u,v) zuordnen, so dass fur jede

39

Metrik Q giltCQ

B = ∑u,v∈V

CB(u,v) ·dQ(u,v) .

Fur Algorithmus B auf der zufallig ausgewahlten Metrik N gilt somit

E[CN

B]

= E

[∑

u,v∈VCB(u,v) ·dN(u,v)

]= ∑

u,v∈VCB(u,v) ·E [dN(u,v)]

≤ ∑u,v∈V

CB(u,v) ·αdM(u,v)

= α ·CMB .

Aufgrund der Dominanz von N uber M, ist E[CM

A]≤E

[CN

A

]. Weil A 3-kompetitive

fur N ist, gilt E[CN

A

]≤ E

[3 ·CN

B]= 3 ·E

[CN

B]. Insgesamt erhalten wir somit

E[CM

A]≤ E

[CN

A]≤ 3 ·E

[CN

B]≤ 3α ·CM

B .

Das obige Lemma zusammen mit Satz 5.6 liefert das folgende Ergebnis.

Korollar 5.9 Fur jeden Graphen G = (V,E) gibt es einen verteilten, randomisiertenOnline-Algorithmus fur FAP der O(log |V |)-kompetitive ist.

40

Kapitel 6

Lastbalancierung

Wir beschaftigen uns in diesem Kapitel mit dem Problem der Lastbalancierung. Beidiesem Problem werden Aufgaben an Maschinen verteilt, so dass die maximale Aus-lastung der Maschinen minimiert wird. Wir haben eine Menge von moglicherweiseverschiedenen Maschinen gegeben und in der Online-Version des Problems erschei-nen die Aufgaben nacheinander und mussen sofort einer der Maschinen zugewiesenwerden. Dabei erzeugt jede Aufgabe auf den Maschinen eine Last (die moglicherweisevon der Maschine abhangt). Zu jedem Zeitpunkt hat also jede Maschine i eine Last li.Das Ziel ist es, die maximale Auslastung, d.h. maxli : 1≤ i≤ N, zu minimieren.

6.1 Identische MaschinenAls erstes werden wir uns die einfachste Variante des Lastbalancierungsproblems an-schauen. Dabei haben wir N identische Maschinen. Eine Eingabesequenz von Aufga-ben soll den einzelnen Maschinen zugewiesen werden. Jede Aufgabe erzeugt eine Lastauf der zugewiesenen Maschine. Da die Maschinen identisch sind, hangt auch die zu-gewiesene Last nicht von der Maschine ab. Man muss also die Aufgaben nur moglichstgleichmaßig auf die Maschinen verteilen.

Wir betrachten folgenden Algorithmus.

• Greedy: Jede eingehende Aufgabe wird der Maschine zugewiesen, die die nied-rigste Last hat. Haben zwei Maschinen identische Last, wird die Maschine mitder kleineren Nummer gewahlt.

Theorem 6.1 Fur N Maschinen erreicht Greedy eine Kompetitive-Ratio von 2− 1N .

Beweis. Wir zeigen zunachst, dass Greedy keine bessere Kompetitive-Ratio als 2− 1N

erreicht. Dazu betrachten wir eine Sequenz, die zunachst aus N · (N − 1) Aufgabenmit Last 1 besteht, gefolgt von einer einzigen Aufgabe mit Last N. Offensichtlich wirdGreedy einer Maschine eine Last von 2N−1 zuweisen, wahrend ein optimaler Offline-Algorithmus jeder Maschine genau eine Last von N zuweist. Also sind die Kosten

41

von Greedy auf dieser Sequenz (2− 1N )-mal so hoch wie die eines optimalen Offline-

Algorithmus.Wir zeigen nun, dass es keine schlechtere Eingabesequenz gibt. Sei dazu σ eine

beliebige Eingabesequenz. O.b.d.A. nehmen wir an, dass die hochste Last von Greedyauf Maschine 1 entsteht. Sei w das Gewicht der letzten Aufgabe, die an Maschine 1zugewiesen wurde und es sei s das Gewicht von Maschine 1 vor dieser Zuweisung.Also sind die Kosten von Greedy genau w+ s. Außerdem ist naturlich die Last aufjeder anderen Maschine ebenfalls mindestens s, denn sonst ware der letzte Job nichtMaschine 1 zugewiesen worden. Also ist die Gesamtlast mindestens w+N · s. Darausfolgt, dass OPT(σ)≥maxw+Ns

N ,w ist. Es gilt daher

Greedy(σ) = w+ s

≤ w+ s+OPT(σ)− w+NsN

= w+OPT(σ)− wN

= OPT(σ)+(1− 1N) ·w

≤ OPT(σ)+(1− 1N) ·OPT(σ)

= (2− 1N) ·OPT(σ) .

6.2 Eingeschrankte MaschinenIm Modell fur eingeschrankte Maschinen haben wir wieder N identische Maschinen.Allerdings kann nicht jede Aufgabe jeder Maschine zugewiesen werden. Daher gibtes zu jeder Aufgabe eine Menge von zugelassenen Maschinen, denen die Aufgabezugewiesen werden darf. Wir konnen nun den Algorithmus Greedy auf dieses neueModell erweitern, indem eine Aufgabe der zugelassenen Maschine zugewiesen wird,die die geringste Last hat.

Theorem 6.2 Fur N eingeschrankte Maschinen ist Greedy (dlogNe+1)-kompetitive.

Beweis. Sei σ = σ1 · · ·σn eine Eingabesequenz, wobei Aufgabe σk eine Last wk aufeiner zugelassenen Maschine erzeugt. Offensichtlich gilt OPT(σ)≥ ∑

ni=1 wiN .

Wir betrachten nun die Zuweisung dieser Aufgaben durch Greedy an die einzelnenMaschinen. Wir teilen diese Zuweisung in Schichten ein. Jede Schicht hat eine Dickevon OPT(σ). Diese Einteilung kann dazu fuhren, dass Aufgaben zwischen zwei an-einandergrenzenden Schichten aufgeteilt werden (aufgrund der Große der Schichten,kann eine Aufgabe nicht auf mehr als zwei aneinandergrenzende Schichten aufgeteilt

42

werden). Wir bezeichnen mit Wi die Gesamtlast, die Greedy in Schicht i den Maschi-nen zuweist (die Last von Aufgaben, die auf zwei Schichten aufgeteilt wurden, wirdgemaß dieser Aufteilung berucksichtigt). Es gilt also fur die Gesamtlast

W =n

∑i=1

wk =N

∑i=1

Wi .

Wir bezeichnen mit

Ri =W −i

∑j=1

Wj

die Restlast, die noch nicht in Schicht 1, . . . i vollstandig durch Greedy zugewiesenwurde. Wir zeigen nun, dass sich in jeder Schicht die Restlast halbiert. Zunachst be-weisen wir folgendes Lemma.

Lemma 6.3 Ri ≤Wi.

Beweis. Wir benotigen die folgende Notation.• Wi j: Die Last auf Maschine j in Schicht i.• zik: Die (partielle) Last von Aufgabe σk in Schicht i. Fur σk gibt es maximal zwei

aufeinanderfolgenden Schichten mit zik > 0.• Oi j: Die Menge der Aufgaben die OPT Maschine j zuweist und die noch nicht in

Schicht 1, . . . i vollstandig durch Greedy zugewiesen wurden.• Ri j: Die Summe der (partiellen) Lasten von Aufgaben in Oi j.

Wir zeigen, dass Ri j ≤Wi j ist. Damit ist dann

Ri =N

∑j=1

Ri j ≤N

∑j=1

Wi j =Wi ,

und das Lemma folgt somit.Wenn Oi j = /0 ist, folgt Ri j = 0 ≤ Wi j. Wenn Wi j = OPT(σ) ist, folgt Ri j ≤

OPT(σ) =Wi j.Daher verbleibt nur der Fall, dass Oi j 6= /0 und Wi j < OPT(σ) ist. Sei r die Ma-

schine, der Greedy die Aufgabe σk ∈Oi j zuweist. Aus Wi j < OPT(σ) folgt, dass r 6= jist. Es gilt Wir − zik ≤Wi j, ansonsten hatte Greedy die Aufgabe σk der Maschine jzugewiesen. Es ist Wir = OPT(σ), ansonsten ware σk 6∈ Oi j. Zusammenfassend gilt

OPT(σ)− zik ≤Wi j .

Mit der Beobachtung, dass ∑σk∈Oi j wk ≤ OPT(σ) ist, konnen wir dann folgern

Ri j = ∑σk∈Oi j

wk− zik ≤ OPT(σ)− ∑σk∈Oi j

zik ≤Wi j .

43

Aus dem Lemma folgt Ri ≤Wi = Ri−1−Ri, und somit gilt Ri ≤ Ri−12 . Deshalb ist

RdlogNe ≤R0

N=

WN≤ OPT(σ) .

Damit kann die Restlast RdlogNe in Schicht dlogNe+ 1 abgearbeitet werden und derSatz folgt.

6.3 Verwandte MaschinenIm Modell der verwandten Maschinen haben wir wieder N Maschinen. Allerdingshat jede Maschine i eine Geschwindigkeit αi, so dass eine Aufgabe der Große w aufMaschine i eine Last von w/αi erzeugt. Zunachst werden wir nun annehmen, dassOPT(σ)≤ Λ ist. Unter dieser Annahme betrachten wir den Algorithmus SlowfitΛ.

• SlowfitΛ: Jede eingehende Aufgabe wird der langsamsten Maschine zugewiesen,die nach der Zuweisung noch eine Last von hochstens 2Λ hat. Wir sagen, dassSlowfitΛ einen Fehler macht, wenn es keine solche Maschine gibt.

Theorem 6.4 Fur eine Eingabesequenz σ, mit OPT(σ) ≤ Λ, macht SlowfitΛ keinenFehler uns es gilt SlowfitΛ(σ)≤ 2Λ.

Beweis. Sei σ = σ1 · · ·σn eine Eingabesequenz, wobei Aufgabe σk die Große wk hat.Es reicht zu zeigen, dass SlowfitΛ keinen Fehler macht, denn dann gilt offensichtlichSlowfitΛ(σ) ≤ 2Λ. Dieses wollen wir per Wiederspruch zeigen. Wir nehmen an, dassOPT(σ)≤ Λ ist und dass SlowfitΛ bei der n-ten Aufgabe einen Fehler macht.

O.B.d.A. nehmen wir an, dass die Maschinen von der langsamsten zur schnellstenaufsteigend angeordnet sind, d.h. α1 ≤ ·· · ≤ αN . Mit lt(i) bezeichnen wir die Lastder Maschine i nachdem die Aufgabe σt zugewiesen ist. Wir nennen eine Maschine iausgelastet, wenn ln−1(i)> OPT(σ) ist. Wir nennen eine Maschine i uberladen, wenndie Maschinen i, . . .N ausgelastet sind. Sei Γ die Menge der uberladenen Maschinen.

Lemma 6.5 Sei Si (S∗i ) die Menge der Aufgaben, die Maschine i durch SlowfitΛ (OPT)zugewiesen werden. Dann ist

∑i∈Γ,s∈Si

ws > ∑i∈Γ,s∈S∗i

ws .

Beweis. Es muss Γ 6= /0 sein. Ansonsten wurde SlowfitΛ die n-te Aufgabe der schnell-sten Maschine zuweisen, denn die Last einer Aufgabe auf der schnellsten Maschi-ne ist hochstens OPT(σ), und damit ware die Last nach dieser Zuweisung hochsten2 ·OPT(σ)≤ 2Λ und SlowfitΛ wurde somit keinen Fehler machen.

44

Fur Γ 6= /0 folgt

∑i∈Γ,s∈Si

ws = ∑i∈Γ

αi ∑s∈Si

ws

αi

> ∑i∈Γ

αi ·OPT(σ)

≥ ∑i∈Γ

αi ∑s∈S∗i

ws

αi

= ∑i∈Γ,s∈S∗i

ws .

Es gibt mindestens eine Maschine, die nicht uberladen ist. Fur Γ = 1,2, . . . ,Nwurde gelten

∑i∈Γ,s∈Si

ws = ∑i∈Γ,s∈S∗i

ws ,

was im Wiederspruch zu Lemma 6.5 steht. Wir bezeichnen mit f die schnellste Ma-schine, die nicht uberladen ist.

Es gibt eine Aufgabe σs mit s < n, die von SlowfitΛ einer Maschine m ∈ Γ zuge-wiesen wird und die von OPT einer langsameren Maschine m′ 6∈ Γ zugewiesen wird.Aus der Annahme, dass eine solche Aufgabe nicht existiert, konnen wir folgern, dassjede Aufgabe, die von SlowfitΛ einer Maschine i ∈ Γ zugewiesen wird, auch von OPTeiner Maschine i′ ∈ Γ zugewiesen wird. Dann gilt

∑i∈Γ,s∈Si

ws ≤ ∑i∈Γ,s∈S∗i

ws ,

was im Wiederspruch zu Lemma 6.5 steht.Also konnen wir folgern

ws

α f≤ ws

αm′≤ OPT(σ)≤ Λ .

Außerdem giltls−1( f )≤ ln−1( f )≤ OPT(σ)≤ Λ .

Daraus folgt, dass ls−1( f )+ wsα f≤ 2Λ ist. Damit hatte SlowfitΛ die Aufgabe σs aber der

Maschine f (oder eine langsamere Maschine) anstelle der Maschine m ∈ Γ zuweisenmussen.

Bisher benotigten wir fur den Algorithmus SlowfitΛ eine Schranke Λ bezuglich dermaximalen Last eines optimalen Offline-Algorithmus. Wir werden nun aus SlowfitΛden Algorithmus Slowfit konstruieren, der keine solche obere Schranke mehr benotigt.

Der Algorithmus Slowfit lauft in Phasen ab. In der Phase 0 fuhren wir den Algo-rithmus SlowfitΛ0 aus, wobei Λ0 der Große der ersten Aufgabe entspricht. Wenn der

45

Algorithmus SlowfitΛ0 bei einer Aufgabe einen Fehler macht, dann beginnt mit dieserAufgabe die nachste Phase. In der Phase i fuhren wir den Algorithmus SlowfitΛi aus,wobei Λi = 2i ·Λ0 ist. Wenn der Algorithmus SlowfitΛi bei einer Aufgabe einen Fehlermacht, dann beginnt mit dieser Aufgabe die nachste Phase.

Theorem 6.6 Der Algorithmus Slowfit ist 8-kompetitive.

Beweis. Wir bezeichnen mit σi den Teil der Eingabesequenz, der in Phasen i abgear-beitet wird. Sei h die Phase, in der Slowfit terminiert. Dann gilt mit Satz 6.4

OPT(σ)≥ OPT(σ0 · · ·σh−1r)> 2h−1 ·Λ0 ,

wobei r die Aufgabe bezeichnet, die den Fehler am Ende von Phase h−1 erzeugt.Fur die maximale Last von Slowfit gilt

Slowfit(σ) =h

∑i=0

SlowfitΛi(σi)≤h

∑i=0

2i+1Λ0 ≤ 2h+2

Λ0 .

Damit ist das Theorem bewiesen.

46