Ich freue mich, auch mal wieder selber Vorlesungen halten zu dürfen.
Meine halbe Arbeitsgruppe ist gerade auf einer Konferenz in Barcelona.
Und ich habe am Montag eine erste Version eines Exzellenzcluster
-Antrags an unser Präsidium abgeliefert, sodass ich jetzt auch mal
wieder normale Sachen machen darf.
Da freue ich mich richtig.
Wir kommen jetzt in unserer Vorlesung, sind wir jetzt so richtig
mittendrin darin, eine Bindestrich-Algorithmik nach der anderen Ihnen
kurz vorzustellen.
Wir haben jetzt mal ganz verschiedene Sichtweisen auf Algorithmen.
Die letzten Kapitel haben das dann klassifiziert nach, ich sage mal,
Datentyp.
Dann geht es ja auch meistens in der Algorithmik um
Berechnungskomplexität, also wie teuer ist es, etwas auszurechnen.
Hier ist jetzt mal eine Ausnahme, hier geht es weniger um
Berechnungskomplexität als um eine Modellierung dessen, was wir wissen
bzw.
nicht wissen.
Wir haben bisher immer Algorithmen betrachtet, wo die gesamte Eingabe
bekannt war und dann wurde halt irgendwas ausgerechnet und das war
dann halt mehr oder weniger gut.
Zum Beispiel Optimierungsalgorithmen.
In vielen Anwendungen ist das aber nicht möglich.
Ein Computer muss eine Entscheidung treffen, ohne die Zukunft zu
kennen.
Das ist mal sinnbildlich dargestellt durch den Nebel auf der Golden
Gate Bridge.
Das ist eine ganz wichtige Eigenschaft von realen Anwendungen.
Wie gehen wir damit um?
Was ich Ihnen hier vorstelle, ist eine Sichtweise auf dieses
grundlegende Problem aus der theoretischen Informatik oder aus der
Algorithmentheorie, das den Vorteil hat, sehr klar definiert zu sein
und sehr klare Antworten zu geben zum Teil.
Und den Nachteil hat, da werde ich noch darauf eingehen, warum das
auch Nachteile hat.
Aber das ist eine Sichtweise auf Unwissen über die Zukunft, die man
eigentlich kennen sollte, selbst wenn man nicht Algorithmiker ist.
Und deshalb haben wir es als Teil von Algorithmen 2 aufgenommen.
Also wie funktioniert das?
Die Information wird dem Algorithmus Stück für Stück nur zur Verfügung
gestellt.
Und er muss eine Ausgabe produzieren, noch bevor er das nächste Stück
kennt.
Also immer so, Eingabe, Entscheidung treffen, nächstes Stück der
Eingabe und so weiter.
Und das Radikale hier ist, wir wissen gar nichts über die Zukunft.
Das ist auch die wichtigste Abgrenzung zu anderen Dingen.
Insbesondere der Hauptansatz, den man in der praktischen Informatik
oft verwendet, ist, dass man eine stochastische Modellierung der
Zukunft hat.
Also man tut so, als wüsste man irgendwas über Verteilungen von
zukünftigen Ereignissen.
Zum Beispiel, was weiß ich, dass es irgendeine Eingabegröße ist,
normal verteilt mit dem und dem Mittelwert und der und der Varianz.
Der Vorteil von diesem stochastischen Ansatz ist, dass man oft
erheblich bessere Algorithmen kriegt, die sich besser auch auf die
Zukunft anpassen.
Nachteil ist, dass das Händewedelei ist, weil meistens weiß man auch
über diese Verteilungen eigentlich nichts oder zu wenig, um die
wirklich benutzen zu können.
Also das ist dann eine sehr starke Vereinfachung der Realität.
Das hier ist jetzt, sagen wir mal, eine sehr pessimistische
Sichtweise.
Aber man kann das auch so sehen, wenn man Algorithmen entwirft, die
mit dieser pessimistischen Sichtweise gut umgehen können, dann hat man
wirklich das Problem gelöst.
Wir werden sehen, dass man damit leider auch zu sehr pessimistischen
Einschätzungen der Zukunft kommt und das ist dann so ein bisschen der
Nachteil.
Trotzdem ist das eine Sichtweise auf Unwissenheit über Zukunft, die
man sich anschauen sollte.
Die Idee ist jetzt folgende.
Wir haben uns bei Approximationsalgorithmen ja so Approximation Ratios
angeschaut.
Also im schlimmsten Fall, wie gut ist die Lösung des Algorithmus
verglichen zu einer optimalen Lösung.
Und diese Sichtweise übernehmen wir jetzt.
Nur, dass wir jetzt nicht die Qualität, wenn ich viel oder wenig
Rechenleistung reinstecke, vergleiche, sondern ich vergleiche die
Situation, wenn ich viel weiß oder nichts weiß.
Wir werden mehrere Beispiele hier betrachten.
Das erste wird das Mieten von Skiern sein.
Passt irgendwie ganz gut, weil wir haben jetzt das erste Mal seit
vielen Jahren wieder Schnee im Schwarzwald.
Da kann man sich fragen, kaufe ich mir Skier her.
Das kann man als Online-Algorithmen-Problem sich angucken.
Es ist ein sehr einfaches Problem und wir können das lückenlos
analysieren.
Wir können auch einen Algorithmus angeben, der auch in der Praxis Sinn
macht.
Dann gucken wir uns sehr intensiv an ein Problem, das für die
Informatik vielleicht eine Spur wichtiger ist.
Nämlich Paging in Virtual Memory Systems.
Weitere Beispiele, die wir nicht so detailliert angucken können, sind
zum Beispiel Routing in Kommunikationsnetzwerken.
Also wie leite ich Pakete weiter, wann schmeiße ich ein Paket weg usw.
Oder Scheduling von Maschinen in einer Fabrik, wo Aufträge über die
Zeit ankommen.
Dann steht hier drin Ad-Placement bei Google.
So genau weiß ich auch nicht, was das ist.
Ich muss dazu sagen, die Folien sind auch deshalb auf Englisch, weil
mein damaliger Post-Doc Rob van Stee, der ist jetzt glaube ich an der
Universität Leicester Professor, der hat die damals mitgebaut.
Ich nehme aber an, dass es bei Google darum geht, dass man ja
Advertisements placen muss und man weiß eben nicht, wer wohin klickt.
Und man weiß auch nicht, was an weiteren Advertisements reinkommt,
während man das noch darstellt.
Wobei ich mal vermuten würde, dass das keine Anwendung ist, wo man
wirklich mit Online-Algorithmen arbeiten will.
Aber es wurde zumindest von den Theoretikern so untersucht.
Warum ich das vermute, dass das so eine Anwendung ist?
Google weiß verdammt viel.
Zwar nicht über die Zukunft, aber über die Vergangenheit.
Und mit diesen gewaltigen Datenmengen sind die tatsächlich auch in der
Lage, statistische Verteilungen zu berechnen, die es ihnen erlauben
abzuschätzen, was in der Zukunft passieren könnte.
Und ich vermute, dass das im Moment passiert.
Dieses Bild erkläre ich später.
So, jetzt erstmal Definition.
Was ist Competitive Analysis?
Ich habe es schon gesagt, wir vergleichen den Online-Algorithmus, der
heißt jetzt ALG, mit einem Offline-Algorithmus, der ein optimales
Ergebnis berechnet.
Den nennen wir OPT.
Wir gucken uns den Worst Case an, das heißt, wir maximieren über alle
möglichen Eingaben.
Hier steht nicht Maximum, sondern Supremum, weil wir auch unendlich
lange Eingaben betrachten.
Und dann gibt es eine unendliche Zahl möglicher Eingaben und das
Maximum existiert vielleicht gar nicht, sondern nur ein Supremum.
Also ein Grenzwert einer Folge von Maxima.
Also was wir wollen für einen gegebenen Algorithmus, wollen wir diesen
Competitive Ratio, C-ALG, bestimmen.
Und natürlich suchen wir nach Algorithmen mit möglichst kleinem
Competitive Ratio.
Darum geht es bei Online-Algorithmen.
Fragen dazu?
Also diese Definition sollte man verstehen, die ist sicherlich auch
eine schöne Wissensfrage für eine Klausur.
So, jetzt gucken wir uns mal dieses Key-Rental-Problem an.
Das funktioniert mit beliebigen Zahlen, aber wir machen es jetzt mal
ganz konkret.
Nehmen wir mal an, Ski allein kostet 50 Euro, kaufen 300 Euro.
Jetzt das Problem ist natürlich, man weiß nicht, wie oft man Ski
fährt.
Also stellen Sie sich vor, Sie sind kompletter Neuling, haben eine
neue Freundin oder so, die ist total versessene Skifahrerin und die
überzeugt Sie, du willst das jetzt auch lernen.
Ich zeige dir, wie das geht.
Kann sein, dass Sie dann sofort Lunte riechen, das ganz toll finden
und ab jetzt jede Woche Skifahren geht und dann hält der Ski auch noch
10 Jahre und dann wäre es natürlich die optimale Lösung, sofort einen
Ski zu kaufen.
Kann aber auch sein, dass Sie sich beim ersten Mal ein Bein brechen
oder das so furchtbar finden, dass Sie das garantiert nie wieder
machen wollen, dann wäre es irgendwie keine gute Idee gewesen, sich
sofort Ski zu kaufen.
Aber Sie wissen es nicht.
Also was ist die rationale Entscheidung?
Was ist ein Algorithmus, der mir rät, wann ich Ski kaufen sollte?
Die optimale Lösung im Sinne eines Online-Algorithmus heißt 6.
Beim sechsten Mal sollte ich das kaufen.
Und ich erkläre Ihnen jetzt, warum.
Der Algorithmus ist eigentlich, Sie haben die Eingabe, wie viel kostet
es, die zu mieten, wie viel kostet es, die zu kaufen und Sie sollen
sagen, nach dem wievielten Mal kaufe ich.
Sonst ist das irgendwie ein komischer Algorithmus, der nur eine
mögliche Eingabe hat.
Wir werden es aber nur für diesen einen Fall 50 und 300 durchrechnen.
Die Frage ist jetzt, wie gut ist das Ding und geht es besser?
Ich habe behauptet, es ist optimal.
Na ja, analysieren wir das mal.
Also ich kaufe die beim sechsten Mal.
Wenn ich weniger als 5 Trips mache, zahle ich 50 mal die Anzahl Trips.
Das ist zwischen 50 und 550 Euro.
Und da ich danach nie wieder fahre, ist das auch optimal.
Weil wenn ich irgendwann zwischendurch Skier gekauft hätte, hätte ich
mindestens 600 Euro bezahlt und würde schlechter fahren.
Wohlgemerkt, typisch für die theoretische Informatik, man
vernachlässigt dabei Dinge, die in der Realität auch noch auftreten
könnten.
Zum Beispiel könnte ich die natürlich auch verkaufen.
Und der Wiederverkaufswert ist auch irgendwie variabel, je nachdem wie
oft ich das benutzt habe.
Wir machen hier Vereinfachungen.
Und wahrscheinlich gar keine so schlechte Vereinfachung.
Ich schätze, bei den meisten Leuten stehen die Skier dann tatsächlich
20 Jahre lang irgendwo rum.
Werden vielleicht noch dreimal mit umgezogen, verursachen sogar
zusätzliche Kosten.
Das ist auch ein Online-Problem.
Wie oft sollte ich etwas umziehen?
Oder ein Kollege hat dann eine Arbeit geschrieben, das Bahncard
-Problem.
Das ist fast das gleiche Problem, nur dass es da noch ein paar
Varianten gibt.
Also ein paar zusätzliche Aspekte.
Die ist halt nur eine bestimmte Zeit gültig.
Und es gibt verschiedene Arten von Bahncards.
Ich weiß gar nicht, was er da genau gemacht hat.
Also wenn ich weniger als sechs Trips habe, ist das optimal.
Das ist schon mal schön.
Gar nicht wahr.
300 kosten die.
Das ist nicht optimal.
Aber ich zahle höchstens 550.
Der optimale Algorithmus zahlt mindestens 300.
Und das bedeutet, ich bin da das Maximum, das ich da sehe, ist elf
Sechstel.
Und naja, die anderen Fälle,
wenn ich öfter fahre als sechs Mal,
ist hier, wenn ich mindestens sechs Trips mache, zahle ich 550.
Man kann jetzt alle Fälle durchrechnen und man sieht, es ist nie mehr
als elf Sechstel davon weg.
Also eben 550 durch 300 ist das.
Das Kürze kommt elf Sechstel raus.
Fragen dazu?
Also das ist jetzt der Competitive Ratio dieses Algorithmus, elf
Sechstel.
Wenn Sie da andere Zahlen einsetzen, bleibt es das immer kleiner zwei.
Jetzt ist natürlich die Frage, gibt es bessere Algorithmen?
Naja, das Schöne bei diesem Algorithmus ist, es gibt nicht so viele
mögliche Ausgaben.
Von daher kann ich die alle durchspielen.
Also nehmen wir mal an, wir kaufen früher.
Also zum Zeitpunkt x kleiner sechs.
Dann zahle ich 300 plus 50 mal x minus eins.
Während der optimale Algorithmus 50 mal x zahlt.
Dann ist der Competitive Ratio 250 plus 50x geteilt durch 50x gleich
fünf durch x plus eins.
Und da sind aber nur die Fälle x kleiner sechs interessant und das ist
größer gleich zwei.
Also jede Strategie, die es früher kauft, hat ein Competitive Ratio
von mindestens zwei.
Während elf Sechstel kleiner zwei ist.
Wenn ich später kaufe,
zahle ich...
Naja, also bei Trip y größer sechs zahle ich 300 plus 50 mal y minus
eins.
Während Opt 300 zahlt.
Das ist also 250 plus 50y durch 300.
Gleich fünf plus y durch sechs.
y ist aber größer sechs, also mindestens sieben.
Dann steht da halt
zwölf durch sechs gleich zwei.
Um das jetzt mal zu verallgemeinern für beliebige Miet- und
Kaufkosten.
Man sollte dann kaufen zu dem Zeitpunkt, wo ich genauso viel für die
Miete bezahlt hätte wie für die Shia.
Das ist hier 300 durch 50 gleich sechs.
Das ist der Algorithmus.
Und es ist auch eingängig.
Man balanciert sozusagen die Risiken.
Also das Risiko, wenn ich zu früh kaufe, ist, dass ich am Ende gar
nicht fahre.
Und das Risiko, wenn ich zu spät kaufe, ist, dass ich dann ganz viel
Miete bezahle.
Und so balanciert man diese beiden Kosten und kommt dann auf zwei.
Fragen dazu?
Und vielleicht noch mal Interpretation.
Also was wir wollen, sind kleine Competitive Ratios.
Zwei ist schon mal ganz okay.
Also das ruiniert sie nicht.
Wenn sie jetzt irgendwie sofort kaufen, immer, dann haben sie ein
Competitive Ratio von sechs.
Das wäre irgendwie nicht so gut.
Oder wenn sie jahrelang mieten, dann haben sie einen unbeschränkten.
Also wenn sie überhaupt nie kaufen, ist der Competitive Ratio sogar
unbeschränkt groß.
Das wäre sicherlich auch keine gute Idee.
So, jetzt gehen wir mal zu einem etwas komplexeren, aber auch
vielleicht spannenderen Problem.
Zumindest für Informatiker.
Paging.
Also Computer haben einen begrenzten, schnellen Speicher.
Nennen wir den mal Cache.
Indem man Speicherseiten speichern kann.
Also das Spiel funktioniert auf verschiedenen Ebenen der
Speicherhierarchie.
Also z.B.
harter Cache als schneller Speicher und Hauptspeicher als langsamer
Speicher.
Oder aber eine Hauptspeicher als schneller Speicher und eine
Festplatte oder Solid-State-Disk als langsamer Speicher.
Und all diese Speicherarten sind dabei in Speicherseiten unterteilt.
Cache-Line ist glaube ich 64 Byte im Moment.
Eine Virtual-Memory-Page, die auf die Platte ausgelagert werden kann.
Es war ganz lange bei 4 Kilobyte.
Heutzutage ist es ein bisschen komplexer.
Es gibt auch große Seiten.
16 Kilobyte sieht man glaube ich auch manchmal.
Aber das ist eben im Betriebssystem oft eine feste Größe.
Und die Frage ist, welche Seiten sollte ich im Hauptspeicher behalten?
Das Ganze modelliere ich jetzt durch eine Folge Sigma von Page
References.
Die Farben, die ich hier dargestellt habe, geben die Seite an.
Also z.B.
wird diese rote Seite ganz am Anfang geladen, dann wieder benutzt.
Ganz am Anfang benutzt, dann wieder hier und hier und hier.
Und die gelbe wird viermal benutzt und die blaue usw.
Also die spannende Frage ist, wenn ich jetzt eine Seite lade, dann
muss die auf jeden Fall in den schnellen Speicher.
Aber wenn ich bereits k Seiten in meinem schnellen Speicher habe, also
die Kapazität voll ist, dann muss ich eine andere rausschmeißen.
Und die Frage, die ich jeweils beantworten muss, ist, welche?
Also k ist die Anzahl, die Größe des Caches.
Wir nehmen jetzt an, dass der Cache so viel schneller ist als der
langsame Speicher, dass wir eigentlich nur zählen müssen, wie oft wir
auf diesen langsamen Speicher zugreifen müssen.
Wir nehmen das als Konstante an.
Das ist zumindest bei einer Festplatte nicht immer genau konstant.
Da gibt es Rotational Delays usw.
Aber das wird alles weg abstrahiert und da gibt es auch gute Gründe,
das weg zu abstrahieren.
Also ein Cache-Hit kostet 0 und ein Cache-Miss kostet 1.
Wir zählen nur die Cache-Misses, ohne uns jetzt dafür zu
interessieren, was passiert dann noch oder wie schwanken die Cache
-Misstimes usw.
Wir machen auch kein Prefetching, schon weil wir die Zukunft nicht
kennen usw.
Das Ziel ist jetzt, die Anzahl Pagefalls zu minimieren.
Hier nochmal das Bild erklärt.
Das hier ist diese Folge der Seitenzugriff-Operation, die wir aber
nicht kennen.
Wir kennen hier die Vergangenheit, können uns die aber auch nicht
merken, weil wir keinen Platz haben, die zu speichern.
Wir kennen den Inhalt des Caches, aber wir kennen nicht diesen Teil
hier.
Zumindest der Online-Algorithmus nicht.
Dann gibt es diese Car-Pages und hier der große Speicher.
Jetzt gucken wir uns mal eine Anzahl von Caching-Algorithmen an.
Also erstmal einfache Heuristiken.
Last-In, First-Out.
Also ich schmeiße immer die neueste Seite raus.
Die Intuition dahinter ist, das ist intuitiv gesehen ein schlechter
Algorithmus.
Und wir hoffen, dass die kompetitive Analyse uns das auch zeigt.
Dann FIFO.
First-In, First-Out.
Das scheint schon besser zu sein.
Dann Least-Frequently-Used.
Also schmeiße die Seite raus, die am wenigsten benutzt wurde bisher.
Das klingt vernünftig.
Wir werden aber sehen, dass das zumindest im Worst-Case beliebig
schlecht sein kann.
Least-Recently-Used.
Schmeiße die Seite raus, die am längsten nicht mehr benutzt wurde.
Und das ist tatsächlich eine Strategie, die in der Praxis verwendet
wird.
Beziehungsweise andere Strategien, die verwendet werden, haben oft so
einen Aspekt da drin.
Und es gibt auch gute Gründe, warum man die verwendet.
Wenn man Performance Benchmarking macht, schneidet die immer sehr gut
ab, diese Methode.
Und man hätte natürlich jetzt gerne, dass die Theorie das auch
widerspiegelt.
Dass hier LRU am besten abschneidet.
Dann gibt es noch einen Flaschwend-Full, der sieht auch irgendwie ein
bisschen dämlich aus.
So der Handtuchwerf-Algorithmus nenne ich das mal.
Also wenn ich eine Seite lade, die nicht reinpasst, dann schmeiße ich
nicht eine Seite raus, sondern gleich alle.
Das hat den Vorteil, dass ich nicht wirklich entscheiden muss, welche
ich rauswerfe.
Und danach habe ich viel Platz.
Also es ist nicht völlig blöd, aber vielleicht ein bisschen
hysterisch.
Und wir werden sehen, dass in der theoretischen Analyse LRU und
Flaschwend -Full sich kaum unterscheiden.
Was irgendwie ein gewisses Problem darstellt, dass offenbar
Competitive Analysis nicht immer die ganze Wahrheit sagt.
Das hängt damit zusammen, dass das Worst Case ist.
Also es gibt eben Fälle, wo LRU auch nicht besser ist als Flaschwend
-Full.
Und die sind natürlich in der Praxis selten, aber die bestimmen hier
diesen Competitive Ratio.
Und dann gibt es noch einen Offline-Algorithmus, mit dem wir uns
vergleichen.
Das ist ja auch noch eine Frage, also selbst wenn ich die Zukunft
weiß, was sollte ich denn machen?
Und tatsächlich kann man zeigen, und wir werden teilweise das auch
beweisen, dass der Algorithmus Longest Forward Distance da am besten
ist.
Er schmeißt also immer die Seite raus, deren nächste Verwendung am
weitesten in der Zukunft liegt.
Beziehungsweise wenn der gar nicht mehr verwendet wird, dann ist das
unendlich, dann kann ich den auf jeden Fall rauswerfen.
Wie zeigt man sowas, dass Longest Forward Distance ein optimaler
Offline -Algorithmus ist?
Das ist so ein schrittweiser Prozess, also ein relativ komplexer,
induktiver Beweis, den wir hier machen.
Also wir nehmen irgendeinen optimalen Offline-Algorithmus, den müssen
wir nicht kennen, das ist das Abstrakte hier an diesem Beweis.
Und bauen ihn schrittweise so an, bauen ihn schrittweise so um, dass
er sich verhält wie Longest Forward Distance.
Und zwar so, dass er dabei seine Optimalität nicht verliert.
Und damit haben wir dann am Ende gezeigt, wenn die Induktion durch die
ganze Folge durchgelaufen ist, dass der Longest Forward Distance nicht
schlechter ist als der optimale und damit auch ein optimaler
Algorithmus ist.
Also der Induktionsschritt sieht konkret so aus.
Wir geben ein Algorithmus, wir können einen Algorithmus i bauen mit
den folgenden Eigenschaften.
Alg und Alg i verhalten sich auf den ersten i-1 Schritten, also
Schritte sind immer diese Requests in der Folge Sigma, verhalten sich
identisch.
Falls der Request i ein Cache Fault hervorruft für beide Algorithmen,
dann schmeißt Alg i die Seite mit der Longest Forward Distance heraus.
Und die Kosten von Alg i von Sigma sind kleiner gleich den Kosten von
Alg von Sigma.
Also das kann man sich hier so vorstellen.
Hier sind die beiden Algorithmen.
Hier ist Sigma, die Zugriffsfolge, hier ist die Stelle, an der ich
bin.
Der blaue Bereich ist der, wo Alg i und Alg sich identisch verhalten.
Diese rote Stelle ist, da verhält Alg i sich so, dass sie Longest
Forward Distance machen.
Und hier weiß ich noch nicht, was da passiert.
Wenn man diesen zugegebenermaßen nicht ganz einfachen Claim bewiesen
hat, folgt daraus schon der Beweis.
Und diesen Teil des Beweises führe ich jetzt auch vor.
Also ich fange an mit einer gegebenen Request-Sequenz Sigma und dem
optimalen Offline-Algorithmus für Alg.
Deshalb steht hier jetzt Opt.
Jetzt benutze ich den Claim für i gleich 1 sowie die Algorithmen Alg,
also das ist in dem Fall Opt, und kriege einen Algorithmus Alg 1, der
die LFD, die Longest Forward Distance-Seite beim ersten Request
rausschmeißt.
So.
Jetzt wende ich den Claim an für i gleich 2, und zwar nicht auf Opt
und Alg 1, sondern auf Alg 1, um Alg 2 zu kriegen.
Dann wende ich den Claim für i gleich 3 an, auf Alg 2, um Alg 3 zu
kriegen und so weiter.
Das kann man sich hier vorstellen.
Also ich habe erst den optimalen Algorithmus, ich habe keine Ahnung,
wie der sich verhält, aber ich baue einen, der sich im ersten Schritt
so verhält wie Alg i und danach das gleiche macht, glaube ich.
Und dann nehme ich den und verändere den so, dass er im zweiten
Schritt wie LFD ist und so weiter.
Und wenn ich bei Alg Sigma betragt bin, habe ich den LFD-Algorithmus.
Also jetzt muss ich nur noch diesen Claim zeigen.
Das ist jetzt nicht wirklich super schwierig, aber das würde irgendwie
eine ganze Vorlesung brauchen.
Und unsere Kalkulation sagt, dass wir die Zeit jetzt nicht haben und
dass vielleicht auch die Geduld der Hörer dann ein bisschen
überstrapaziziert würde.
Also in einer Vorlesung Online-Algorithmen würden wir das sicherlich
detailliert machen, aber hier nicht.
Gut.
Übrigens, wer will den Beweis sehen in der Übung?
Okay.
Einer.
Zwei, drei, ja.
Schauen wir mal.
So, vergleichte Algorithmen.
Na ja, Opt ist eben offensichtlich kein Online-Algorithmus, weil der
diese Longest Forward Distance berechnen muss und dafür muss man die
Zukunft schauen.
Was ist denn jetzt der beste Online-Algorithmus?
Jetzt schließen wir mal ein paar aus.
Beliebig schlecht sind LIFO und LFO.
Beispiel.
Also es geht ja hier um Worst-Case.
Wir müssen immer nur eine Folge angeben, die beliebig schlecht werden
kann.
Wobei das auch nicht ganz trivial ist, weil eine endlich lange Folge
kann natürlich auch nur endlich schlecht sein.
Aber wenn wir eine Familie von Folgen angeben, die immer länger werden
und deren Competitive Ratio immer weiter steigt, können wir jetzt
sagen, es ist unbeschränkter Competitive Ratio.
Und das machen wir hier bei LIFO.
Wir nehmen die Folge.
Am Anfang werden die Seiten Page 1 bis Page K zugegriffen.
Was da passiert, jeder Algorithmus hat hier dann Cash-Falls.
Am Anfang ist der Cash leer.
Dann kommt die Seite PK plus 1.
LIFO schmeißt PK raus.
Als nächstes kommt wieder die Seite PK.
Was schmeißt LIFO raus?
PK plus 1.
Ja, weil PK wurde gerade rausgeschmissen.
Muss man also was reinholen, was anderes rausschmeißen.
Dann kommt wieder PK plus 1.
Den habe ich gerade rausgeschmissen.
Too bad.
LIFO schmeißt PK raus.
Also ich schmeiße einfach abwechselnd PK und PK plus 1 raus.
Und LIFO ist wirklich so dickschädlich, trotzdem jedes Mal ein Cash
-Fall zu produzieren.
Die Anzahl Cash-Falls ist irgendwie genauso wie das Sigma-Betrag.
Es passiert jedes Mal ein Cash-Fall.
Ein optimaler Algorithmus hat wie viele Cash-Falls?
Der würde halt einfach an dieser Stelle P1 rauswerfen, was danach nie
wieder gebraucht wird.
Und er hat dann genau K-Page-Falls.
Der Competitive Ratio ist also Sigma-Betrag durch K.
Wenn ich Sigma-Betrag beliebig groß wähle, wird dieser Ratio beliebig
groß.
Also offensichtlich kein guter Algorithmus.
Jetzt weniger offensichtlich.
Least Frequently Used.
Also die Idee, dass man selten benötigte Seiten rausschmeißt, ist ja
an sich nicht schlecht.
Aber im Worst Case, schauen wir mal.
Nehmen wir einen Parameter M, den wir beliebig groß wählen können.
Jetzt greifen wir M mal P1 zu.
Dann M mal P2.
M mal PK minus 1.
Das ist jetzt so gemacht, die sind so oft zugegriffen worden, dass in
der folgenden Folge die wie Bleiklötze im Cash liegen.
Die werde ich nicht mehr los, weil die so oft zugegriffen wurden.
Die füllen mir meinen gesamten Cash auf bis auf eine Seite.
Und jetzt greife ich wieder PK und PK plus 1 abwechselnd zu und das
Ganze M minus 1 mal.
Zu jedem Zeitpunkt hier wurden die seltener zugegriffen als die.
Ich habe also nur noch einen, der frei ist.
Dann schmeißen die sich ebenfalls immer abwechselnd raus.
Wenn das öfter passieren würde, würde der Algorithmus tatsächlich von
LIFO abweichen und besser sein.
Aber trotzdem, der Competitive Ratio ist hier, die Details rechne ich
jetzt nicht aus, aber im Prinzip habe ich hier größer M Cashfalls.
Während der optimale Algorithmus hier K Cashfalls produziert.
Und wenn ich M hinreichend groß wähle, wird der Competitive Ratio auch
wieder beliebig groß.
Also was lernen wir daraus?
Least Frequently Used ist deshalb kein guter Algorithmus,
weil er zwar die Häufigkeit eines Zugriffs berechnet, aber nicht die
Recency sozusagen.
Es ist offenbar nicht nur wichtig, wie oft etwas zugegriffen wurde,
sondern auch wann es oft zugegriffen wurde.
Und das muss ich berücksichtigen, sonst kann ich beliebig schlecht
werden.
Okay, da habe ich schon mal was gelernt.
Das ist ja was Nützliches.
Also Competitive Analysis sagt uns, warum bestimmte Algorithmen nicht
gut sind.
Bei LIFO hätte man das vielleicht auch so sehen können, bei LFU nicht
unbedingt.
Also da finde ich das schon nützlich.
So, weiter.
Und da kommen wir jetzt zu einem Problem von Online-Analyse.
Wie gut können Online-Algorithmen in diesem Modell überhaupt werden?
Und was wir hier sehen, ist fast beliebig schlecht.
Egal wie gut ein Online-Algorithmus ist, es gibt immer eine
Eingabefolge, die ihn total schlecht aussehen lässt.
Nämlich man kriegt dann ein Competitive Ratio von K.
Jetzt stellen Sie sich groß, wie groß sind typische Cache-Größen?
Kommt auf den Cache an, aber sehr oft Millionen.
Sie wollen eigentlich keinen Algorithmus haben mit einem Competitive
Ratio von ein paar Millionen.
Aber das ist was Online-Algorithmen Ihnen hier liefert.
Und wenn Sie das Ihrem Chef sagen, oh ich habe einen optimalen Caching
-Algorithmus in unser Betriebssystem reingebaut.
Und dann sagt er ja, wie schlecht kann denn der werden?
Ja, er kann auch mal eine Million mal schlechter sein als das Optimum.
Das kommt nicht gut.
Aber zeigen wir das mal.
Warum ist das so?
Warum kann das so schief gehen?
Wir konstruieren jetzt eine Folge.
Und das ist jetzt so ein typischer Prozess, den man machen muss, wenn
man irgendwie Beweise führen möchte über Online-Algorithmen.
Man versetzt sich sozusagen in die Situation eines Gegners, eines
Adversary und versucht möglichst gemein zu sein.
Nehmen wir mal an, wir haben K plus 1 Pages.
Das ist noch nicht so gemein.
Wenn ich nur K Pages hätte, dann kann jeder Algorithmus, ist dann gut,
ist klar.
Also ich habe eine mehr.
Aber jetzt kommt die Gemeinheit.
Ich nutze jetzt aus, dass der Adversary den Algorithmus kennt.
Naja, also der weiß jetzt zu jedem Zeitpunkt, welche Seiten der im
Cache hat, im allgemeinen K-Stück, außer so einer Einschwingphase.
Aha, es gibt aber K plus 1 Seiten.
Das heißt, zu jedem Zeitpunkt gibt es genau eine Seite, die nicht im
Cache ist.
Was meinen Sie, welche der Adversary auswählt?
Genau die.
Total gemein, aber kann er machen.
So geht das Spiel hier.
Das bedeutet, wir kriegen in jedem Schritt ein Cache-Fault.
Egal, wie gut der Algorithmus ist.
Und das ist schon irgendwie eine blöde Aussage.
Also was sagt uns das?
Du kannst dir noch so sehr den Kopf zerbrechen, wie du willst.
Sobald das Paging-Problem überhaupt nicht trivial ist, nämlich es gibt
mehr Seiten als Cache-Einträge, gibt es Eingaben, bei denen du nur
Mist baust.
Und wo jeder beliebig schlechte Caching-Algorithmus auch funktionieren
würde.
Insbesondere einer, der einfach gar nicht cached.
Nein, das stimmt nicht.
Streichen Sie den letzten Satz.
Wir haben ja gesehen, dass es noch schlimmer sein kann.
Aber trotzdem, es gibt Seiten, wo Caching überhaupt nicht wirkt.
Es gibt Eingaben, wo Caching nicht wirkt.
Und das ist natürlich blöd.
Und das unabhängig von dem Algorithmus.
Ja, also das ist ein spannendes Ergebnis und ein ziemlicher Dämpfer
aus meiner Sicht für Online-Algorithmen.
Aber wir werden noch ein paar Tricks sehen, wie man sich da aus der
Affäre ziehen kann.
Also die Geschichte ist noch nicht zu Ende.
Der erste Trick ist Resource Augmentation.
Der macht das Modell ein bisschen komplexer und sagt, okay, das ist ja
auch total unfair, was der Adversary da macht.
Wir versuchen, das ein bisschen auszugleichen.
Wir sagen dafür, dass der Adversary volle Informationen hat, geben wir
dem Online-Algorithmus mehr Ressourcen.
Das nennt man Resource Augmentation.
Also wir vergleichen jetzt nicht mehr einen Online-Algorithmus mit
einem optimalen Offline-Algorithmus mit den gleichen Parametersätzen,
sondern wir vergleichen den Online-Algorithmus mit einem optimalen
Offline -Algorithmus, dem man weniger Ressourcen zur Verfügung stellt.
Also das Ergebnis ist dann so eine bikriterielle Sache.
Also du bist so und so viel schlechter und brauchst außerdem so und so
viel mehr Ressourcen.
Aber das könnte trotzdem eine nützlichere Aussage zu sein, wie du bist
beliebig viel schlechter, brauchst aber dafür nur genauso viele
Ressourcen.
Das ist trotzdem eine nützlichere Aussage, nur ein bisschen komplexer.
Offline-Cache hat jetzt die Größe h kleiner k.
Und das Problem nennt man auch hk-Paging.
Hier ist jetzt auch so eine Meta-Erkenntnis.
Wir müssen ja hier relativ komplexe Beweise führen.
Und wir wollen außerdem Online-Algorithmen oder dieses Framework der
Competitive Analysis verwenden, um eine große Anzahl Algorithmen zu
vergleichen.
Das sieht auf den ersten Blick so aus, dass das zu einem riesen Wust
von Beweisen führt.
Aber ein Trick hier ist, dass wir nicht konkrete Algorithmen
analysieren, sondern ganze Familien von Algorithmen.
Und das hat einen doppelten Vorteil.
Also erstens kann ich einen Beweis führen, der für ganz viele
Algorithmen Aussagen trifft.
Und zweitens ist es oft so, dass diese Definition der
Algorithmenfamilie auch bereits die Aspekte in den Vordergrund rückt,
die für den Beweis wichtig sind.
Und deshalb auch zusätzliche Einsichten liefern.
Und hier ist jetzt so eine Familie von Algorithmen.
Konservative Algorithmen.
Das ist jetzt weder politisch noch so, dass der Begriff Konservativ
-Algorithmen außerhalb dieses konkreten Online-Paging-Problems
irgendwie eine definierte Rolle hat.
Aber wir müssen jetzt einen Namen dafür angeben, einen sprechenden
Namen.
Also ein Paging-Algorithmus ist konservativ,
wenn er für eine Teilfolge von Requests, die nur k-verschiedene Seiten
zugreift, höchstens k-Pagefalls produziert.
Also das ist irgendwie so eine Art Vernunft-Argument auch.
Offenbar ist es so, dass wenn ich eine Teilfolge habe, wo die Anzahl
Seiten, die da zugegriffen werden, irgendwie nicht größer ist als der
Cache, dass dann ein halbwegs vernünftiger Algorithmus für jede dieser
Seiten nur einen Page-Fold in dieser Teilfolge produzieren sollte.
Also das ist so eine Eigenschaft, die man eigentlich von einem Paging
-Algorithmus erwartet und die man auch relativ leicht nachweisen kann
für viele Algorithmen.
Also LREU hat die Eigenschaft, FIFO hat die Eigenschaft, oder
Flaschlandfull hat die auch, übrigens.
Ja, Frage?
Also in dieser Teilfolge, die hier beginnt, greifen Sie nur zwei
verschiedene Seiten zu, produzieren aber in jedem Zugriff ein Page
-Fold.
Aber trotzdem gute Frage, um das zu illustrieren.
Genau, also LREU und FIFO haben diese Eigenschaft, LFU und ich glaube
Flaschlandfull auch, und LFU und LIFO haben sie nicht.
Bei denen wissen wir aber auch schon, dass sie schlecht sind.
Und ja, das kann beliebig lang werden, das war jetzt nicht so wichtig.
Ja, die Behauptung ist jetzt...
Wir machen jetzt den Competitive Ratio mit Ressource Augmentation.
Der Satz, den wir jetzt beweisen, ist, jeder konservative Algorithmus
ist K durch K minus H plus 1 kompetitiv.
Das ist jetzt irgendwie keine so sprechende Formel.
Was wir später tun werden, ist, dass wir H sowas wie K halbe wählen.
Und was dann passiert ist, dass hier sowas steht wie 2 kompetitiv.
Also wenn wir dem Offline-Algorithmus nur halb so viele Ressourcen
geben, sind wir höchstens zweimal schlechter.
Und das ist irgendwie, finde ich, ein besserer Kompromiss, als zu
sagen, wir sind K-mal schlechter, haben aber dafür die gleichen
Ressourcen.
Aber die Aussage hier ist noch ein bisschen allgemeiner, man kann mit
diesem Parameter jetzt auch spielen.
So, der Beweis ist auch nicht so schwierig.
Man nimmt eine beliebige Requestfolge Sigma und unterteilt sie in
Phasen.
Und jetzt wird erklärt, was eine Phase ist.
Das ist jetzt nur so eine technische Definition.
Phase 0 ist die leere Folge.
Phase i plus 1 ist die maximale Folge von Zugriffen, die auf Phase i
minus 1 folgt, die höchstens K distinct Pages enthält.
Also diese Definition gibt im Prinzip einen Algorithmus an, wie ich
diese Partitionierung machen kann.
Also erstmal habe ich Phase 0, das ist eine leere Phase.
Dann gehe ich, wenn ich jetzt i Phasen habe, nehme ich mir den
nächsten Request und gucke, was ist das für eine Seite.
Merke mir das und gehe immer weiter, bis ich in diesem Teil das erste
Mal die K plus 1.
Seite finde.
Und die ist dann gerade nicht Teil dieser Phase.
Das ist jetzt diese Partitionierung der Folge, die ich verwende.
Das ist jetzt auch typisch für theoretische Informatik.
Wir haben hier einen Algorithmus angegeben, den wir gar nicht
implementieren müssen.
Es geht gar nicht darum, diese Phasen wirklich zu bestimmen.
Es geht eher darum, zu definieren, was sind diese Phasen und wir
machen dann hinterher mathematische Beweise über diese Phasen.
Wichtige Beobachtung, diese Partitionierung hat nichts mit dem
Algorithmus zu tun.
Die hängt nur von Sigma ab, gilt also für alle Algorithmen.
Aber was wir auch jetzt sehen können...
Einfach nach Definition eines konservativen Algorithmus hat ein
konservativer Algorithmus höchstens k Falls in jeder Phase.
Also wir können jetzt, wenn wir diese Phaseneinteilung haben,
abschätzen, eine obere Schranke angeben für die Anzahl Page Falls
eines beliebigen konservativen Algorithmus.
Und jetzt kommt der Trick.
Jetzt gucken wir uns an, wie viele Cache Falls muss der optimale
Algorithmus produzieren in jeder Phase.
Und das ist auch ganz einfach, weil ich habe hier eine Phase, da
werden k verschiedene Seiten zugegriffen.
Ich habe aber nur Platz für h.
Deshalb müssen k-h, beziehungsweise wenn man genauer rechnet, sind es
k -h plus 1 Falls auftreten in dieser Phase.
Um weniger zu haben, müsste der einfach mehr Platz haben.
Das ist alles, was ich brauche.
Jetzt muss ich nur noch rechnen.
In jeder Phase hat ein konservativer Algorithmus k Falls.
Demgegenüber hat der optimale Algorithmus k-h plus 1 Falls.
Das heißt, also das hier ist höchstens so viele und der hat mindestens
so viele.
Daraus folgt, dass der Competitive Ratio kleiner gleich k durch k-h
plus 1 ist mal Opt.
Und dann plus r, das ist die Anzahl k Falls von Alg in der letzten
Phase, weil die kann ich nicht aufrechnen, gegen die das optimal ist.
Da muss man jetzt gucken, warum tritt das r hier nicht auf?
Da muss man in die Definition von Competitive Ratio gucken.
Da ist mir jetzt nicht ganz klar, was hier passiert.
Da muss ich vielleicht nochmal in die Definition gucken.
Weil, also das Verhältnis ist dann ja...
Also da kommt dieses plus r irgendwie vor.
Das ist aber höchstens k.
Wenn ich jetzt die Folgen beliebig lang mache, wird der Ratio
irgendwann kleiner.
Aber ich frage mich, ob der für kurze Folgen nicht ein bisschen größer
sein kann.
Da kann ich im Moment keine Antwort drauf geben.
Aber es gibt tatsächlich auch diesen Begriff, das Asymptotic
Competitive Ratio, der das halt bewusst sagt, dass ich den Grenzwert
bilde für beliebig lange Sigma.
Aber das ist nicht, was hier steht.
Deshalb bin ich ein bisschen verwirrt.
Aber das ist jetzt auch nicht so wichtig.
Zumindest wenn ich hier die Definition so machen würde, dass ich den
Grenzwert da definiere, dann würde das stimmen.
Oder es gibt irgendwie ein Argument, warum dieses plus r da nicht
wichtig ist.
Aber insgesamt für das Gesamtverständnis dieser Idee, warum Resource
Augmentation gut ist, ist das jetzt auch nicht wichtig.
Okay.
Gut.
Damit haben wir unsere Theorien bewiesen.
Und ein sinnvoller Wert für r ist halt k halber.
Und jetzt muss man sich nochmal klar machen.
Also wir haben jetzt ein Competitive Ratio zum Beispiel von 2 für r
gleich k halber gezeigt.
Und wir haben vorher gezeigt, dass der immer k werden kann.
Aber das sind da zwei verschiedene Schuhe.
Diese alte untere Schranke galt ja nur für h gleich k.
So.
Jetzt kommt was, was nichts mit Theorie zu tun hat.
In der Praxis ist der Competitive Ratio von LRU, aber das ist
natürlich Quatsch.
Das ist dann nicht der Competitive Ratio.
Sondern in der Praxis ist das Verhältnis zwischen der Leistung von LRU
und dem Offline-Algorithmus in der Nähe von 1.
Oder hier steht es Small Constant.
Kann sein, dass es nicht in der Nähe von 1 ist.
Aber ich denke, oft viel kleiner als 2 nochmal.
Und ja, Resource Augmentation hilft uns, das irgendwie zu verstehen.
Ich weiß nicht, wie Simon und Christian das gehalten haben.
In den Folien gibt es ja immer diese Seiten, die mit einer Chili
-Schote markiert sind.
Haben die die vorgeführt?
Das ist der spannende Teil.
Aber das heißt, dass wir da jetzt keine allzu gemeinen Fragen in der
Prüfung drüber stellen.
Das ist so ein bisschen der Blick über den Tellerrand.
Sie haben vielleicht schon gemerkt, ich bin kein absoluter Freund von
Online -Algorithmen.
Man kann daraus viel lernen, aber manchmal sind die Ergebnisse ein
bisschen komisch.
Also insbesondere alles, was wir bisher gesagt haben, kann nicht
unterscheiden zwischen der Qualität von FIFO, Flash when full und LRU.
Obwohl offensichtlich LRU der beste von diesen Algorithmen ist.
Und da gibt es aber eben tatsächlich auch neuere theoretische
Arbeiten, die das feiner herausarbeiten können.
Also da gibt es zwei Papiere, die mir da einfallen.
Das ist von Panagiotou und Sousa in Stock 2006.
Da habe ich irgendwas Falsches reinkopiert.
Entschuldigung, das ist Quatsch.
Das lösche ich wieder raus.
Das kommt mir hier unten.
Also die geben dem Adversary ein bisschen weniger Macht sozusagen.
Und sie gucken sich Locality of Reference an.
Und sie gucken sich typische Speicher-Zugriffsmuster an.
Also was die mit typisch meinen, ist ganz witzig.
Wenn ich aufeinanderfolgende Requests habe, dann gibt es zwei wichtige
Familien.
Nämlich welche, deren Abstand in Sigma sehr kurz ist, verglichen mit
der Cache-Größe.
Oder sie ist sehr groß.
Das kann man offenbar aus Traces von realen Berechnungen auch
nachweisen.
Und wenn ich diese Vereinfachung mache, dann kann man offenbar noch
genauere Competitive Ratios erleiden.
Oder realistischere.
Und hier ist dann halt dieses Papier von Angelopoulos.
Hier sieht man jetzt, wer das noch geschrieben hat.
Firas Angelopoulos, Alejandro Lopez-Ortiz und Reza Dorigif.
Die können dann eben tatsächlich diese verschiedenen Paging-Strategien
separieren, mithilfe solcher verfeinerten Modelle.
Aber das ist jetzt vielleicht deutlich jenseits dessen, was man
sozusagen als Bread-and-Butter-Informatiker wissen muss.
Und wahrscheinlich auch jenseits von dessen, was ein Algorithmiker
wissen muss.
Das ist halt schon ein bisschen was für die Spezialisten.
Aber wenn sie sich zum Beispiel mit Betriebssystemen beschäftigen, ist
es vielleicht auch interessant zu wissen, dass man theoretisch
argumentieren kann, warum bestimmte Algorithmen gut sind.
Und zwar auch für Eingaben von Anwendungen, die erst in der Zukunft
kommen, die sie noch gar nicht kennen durch ihre Messungen zum
Beispiel.
So, jetzt haben wir einen Trick gesehen, wie man dieses K-Competitive
-Problem besiegen kann.
Ich mache das jetzt alles sehr ausführlich am Beispiel von Paging,
aber das gilt für viele Algorithmische Probleme, die man in dem
Kontext von Online-Algorithmen anschaut.
Dass Resource Augmentation helfen kann.
Das ist nur ein Beispiel.
Was auch helfen kann, ist Randomisierung.
Und das ist auch was ganz Fundamentales.
Warum hilft Randomisierung?
Weil dieser Adversary, der konnte ja nur deshalb so gemein sein, weil
er genau wusste, was der Algorithmus macht.
Aber wenn Sie den Algorithmus jetzt randomisieren, dann weiß der
Adversary das halt nicht mehr und kann deshalb auch nicht ganz so
gemeine Entscheidungen treffen.
Bzw.
kann nicht so erfolgreich Ihnen in die Suppe spucken, sagen wir mal
so.
Unser Algorithmus muss halt irgendwie Zufall im Entscheidungsprozess
verwenden und man muss da noch etwas genauer hingucken, was der
Adversary jetzt weiß.
Wir beschäftigen uns nur mit dem einfachsten und schwächsten
Adversary.
Der weiß nur, was für eine Zufallsverteilung wir da verwenden, wenn
wir Bits würfeln.
Aber im Allgemeinen ist das halt irgendwie gleich verteilt,
unabhängig.
Deshalb nützt das auch nichts.
Also der weiß eigentlich gar nichts.
Und man kann sich das so vorstellen, der muss die Eingabe, die für uns
schlecht sein soll, festlegen, bevor der Algorithmus läuft und seine
Zufallsbits festlegt.
Und das ist aus meiner Sicht auch in vielen Fällen die sinnvollste und
realistischste Definition.
Dann gibt es noch zwei andere, Adaptive Online und Adaptive Offline.
Bei Adaptive Online kennt der Algorithmus die Zufallsentscheidungen,
die in der Vergangenheit getroffen wurden.
Und bei Adaptive Offline weiß er sogar, was ich in der Zukunft mache.
Ich habe immer noch nicht verstanden, wieso man das hier überhaupt
betrachtet.
Weil wenn der alles weiß über die Zukunft,
dann kann er das auch maximal ausnutzen.
Also zumindest bei Paging macht das keinen Sinn.
Bei Adaptive Offline hilft das irgendwie nicht, der Zufall.
Es kann sein, dass das bei anderen Problemen einen Unterschied macht.
Aber wenn Sie ein Paper sehen, das sagt, wir machen jetzt etwas, was
neue Erkenntnisse über Adaptive Offline gibt, dann wissen Sie, Sie
sind ganz tief in der Theorie.
Adaptive Online ist so ein bisschen dazwischen.
Ich glaube, das ist dann sinnvoll, wenn Sie über Angreiferszenarien
rechnen.
Oblivious ist der Fall, Sie wollen halt wissen, was passiert, wenn
normale Anwendungen und Eingaben, die sich nicht böswillig verhalten,
das ganze Spektrum von möglichen Eingaben durchgehen.
Aber Adaptive Online ist, glaube ich, dann wichtig, wenn es einen
Angreifer gibt, der Ihren Algorithmus kennt und tatsächlich, also in
der Praxis jetzt, das ist jetzt kein abstrakter Adversary, sondern ein
realer Adversary, der zum Beispiel eine Denial-of-Service-Attacke
fahren will.
Dann kennt er vielleicht Ihren Algorithmus und hat vielleicht sogar
eine Chance, aus den Entscheidungen, die Sie treffen, Rückschlüsse zu
schließen auf die Zufalls-Bits, die Sie verwendet haben in der
Vergangenheit.
Und der kann sich darauf anpassen.
Es gibt so ähnliche Anwendungen zum Beispiel bei Hashtabellen.
Wir haben in Algorithmen 1 Hashtabellen kennengelernt, die irgendwie
beweisbare Leistungsgarantien geben, in einem probabilistischen Sinne.
Aber jetzt stellen Sie sich vor, Sie haben eine Hashtabelle, die wird
von irgendeinem Web-Server verwendet.
Und jemand möchte einen Denial-of-Service-Angriff auf diesen Web
-Server führen und zwar will der das so machen, dass die Hashtabellen
-Zugriffe Ihres Services möglichst langsam werden.
Dann kann der Angreifer versuchen, herauszufinden, welche Hash
-Funktion Sie verwenden.
Indem er ganz bestimmte Eingaben macht und dann beobachtet, wie lange
die Antwortzeiten sind.
Und dann schließen, aha, hier war eine Kollision, das geht nur mit der
Hash -Funktion.
Ich weiß ja, der nimmt die aus der und der Familie von universellen
Hash -Funktionen.
Blablabla.
Und wenn er das einmal weiß, kann er vorhersagen, welche Elemente
kollidieren.
Und dann gibt er Ihnen nur noch Elemente, die Kollisionen hervorrufen.
Das heißt, Sie haben dann keine Hashtabelle mehr, sondern eine lineare
Liste, durch die Sie jedes Mal durchsuchen müssen.
Und das ist ein möglicher Ansatz für eine Denial-of-Service-Attacke.
Und so ähnlich ist das hier bei diesem Adaptive Online.
Also das ist dann sinnvoll, wenn Sie mit tatsächlichen, echten,
böswilligen Attacken rechnen.
Während das Oblivious irgendwie sinnvoll ist, wenn Sie einfach gucken
wollen, wie verhält sich so ein Algorithmus unter normalen Umständen.
Okay.
Also für uns nur das naheliegende.
Der Adversary weiß nichts über unsere Zufalls-Bits.
So.
Jetzt kommt die nächste Familie von Algorithmen.
Von Paging-Algorithmen.
Marking-Algorithmen.
Wenn eine Seite zugegriffen wird, wird sie markiert.
Und die Idee ist, wir schmeißen niemals markierte Seiten raus.
Das ist natürlich blöd, weil irgendwann sind natürlich alle Seiten im
Cache markiert.
In dem Fall muss ich etwas anderes machen, dann wird alles
endmarkiert.
Außer der Seite, die jetzt gerade zugegriffen wurde.
Damit beginnt sozusagen eine neue Phase.
Also hier habe ich wieder, diesmal auch im Algorithmus selber, Phasen.
Aber auch Phasen, die für die Analyse eine Rolle spielen.
Jetzt kann ich mir verschiedene Algorithmen vorstellen, die in diese
Familie fallen.
LRU hat... wie ist das?
Ist LRU von alleine?
Der ist, glaube ich, von alleine ein...
der verhält sich, obwohl er nicht explizit markiert, verhält er sich,
glaube ich, wie ein Marking-Algorithmus.
Aber man könnte auch eine Variante von LRU betrachten, die halt die
least recently non-marked page verdrängt.
Aber ich glaube, das passiert von alleine.
Flash when full hat auch diese Eigenschaft, ist auch ein Marking
-Algorithmus.
Die sind aber beide nicht so toll.
Also hier sind jetzt nicht alle Marking-Algorithmen gleich, sondern
wir gucken uns jetzt einen dritten an, den nennen wir R-Mark.
Wir schmeißen raus eine zufällige Seite, die nicht markiert ist.
Also das ist jetzt so ein bisschen ein Kompromiss zwischen
Randomisierung und,
ich sage mal, einem sinnvollen Algorithmus.
Der einfachste randomisierte Paging-Algorithmus würde ja einfach
sagen, naja, schmeiß eine zufällige Seite raus.
Aber das ist irgendwie nicht kompetitiv.
Weil dann würde man ja auch manchmal Seiten rauswerfen, die
offensichtlich ganz oft benötigt werden.
Und das vermeidet man durch diese Marking-Strategie.
Ich glaube, das Schöne ist auch, dass das außerdem ist jeder Marking
-Algorithmus auch ein konservativer Algorithmus.
Aber das ist so intuitiv schon, kann man sagen, das ist ein einfacher
Kompromiss zwischen Zufall und Zielgerichtetheit, sage ich mal.
Und der Zufall ist halt dafür da, den Adversary zu verwirren.
Die Aussage, die man beweisen kann, wir sind wieder bei Chilis,
deshalb werde ich Ihnen garantiert auch nicht einen detaillierten
Beweis vorführen.
Der Marking-Algorithmus ist 2HK-kompetitiv, wobei HK die Summe von 1
bis K, 1 plus 1 durch I ist.
Das ist sowas wie die harmonische Zahl.
Und das ist kleiner gleich LNK plus 1.
Also der ist sowas wie zweimal LNK-kompetitiv.
Und das ist schon toll, vorher waren wir K-kompetitiv, jetzt sind wir
LNK -kompetitiv.
Also das bringt eine deutliche Verbesserung und zwar ohne Ressourcen
-Augmentierung.
Hier ist jetzt die Analyse, möchte ich nicht so im Detail vorführen,
aber vielleicht mal so die logischen Schritte, ohne in die Rechnungen
zu gehen.
Also wir gucken das jetzt wieder Phase für Phase an.
Sei jetzt M die Anzahl neuer Seiten in einer Phase.
Also mit neu sind Seiten gemeint, die zu Beginn der Phase nicht im
Cache sind.
Dann kann man sich überlegen, dass die Miss-Probability für die J-alte
Seite, wenn die markiert wird, ist irgendwie ja das hier.
Das kann man abschätzen zu M durch K-J.
Und wenn ich das irgendwie durchrechne, kommt man auf M mal HK.
Also die erwartete Anzahl Cache-Falls für M neue Seiten ist M mal HK.
Das detaillierte Argument möchte ich Sie jetzt nicht mit belasten.
Aber was vielleicht interessant ist, also man guckt sich wieder Phase
für Phase an.
Man benutzt die Definition des Algorithmus, um irgendwie auszurechnen,
wie groß ist die Wahrscheinlichkeit für bestimmte Miss-Probabilities.
Und daraus kann man mithilfe von Linearität, von Erwartungswert und
solchen Sachen die erwartete Anzahl Cache-Falls ja nicht ausrechnen,
sondern abschätzen.
Obwohl, ja hier wird sie glaube ich mehr oder weniger aus...
Ne, weiß ich gar nicht.
Das ist abgeschätzt.
So, für so ein Competitive Ratio brauche ich immer zwei Seiten.
Wie ergeht das Opt?
Bei wie viel Cache-Falls produziert Opt für eine Phase?
Das ist sowas wie ein Halb-Mi.
Also wenn Mi war die Anzahl neuer Seiten in der Phase und dann kriege
ich ein Halbsumme-Mi.
Also ich habe hier ein Halbsumme-Mi, hier hatte ich M mal HK.
Und wenn ich das summiere, steht da Summe-Mi HK.
Und wenn ich dann ein Ratio bilde, komme ich eben auf 2 HK.
Also der Randomized Marking-Algorithmus ist 2 HK kompetitiv.
Man kann auch mehr zeigen, dass kein randomisierter Algorithmus besser
als HK kompetitiv werden kann.
Also wir sind bis auf den Faktor 2 an den besten randomisierten
Algorithmus dran.
Also nicht nur Marking-Algorithmus.
Und in dem Sinne würde jetzt ein Theoretiker sagen, der ist optimal
bis auf den Faktor 2.
Und es gibt tatsächlich randomisierte Paging-Algorithmen.
Also nicht randomisierte Marking-Algorithmen, sondern die sind halt
komplizierter, die tatsächlich dieses HK-Kompetitiveness erreichen.
Also das Beste, was man in diesem Framework überhaupt erreichen kann.
Was aus meiner Sicht noch eine offene Frage sein könnte, ist, was
passiert eigentlich, wenn ich Randomisierung und Resource Augmentation
zusammenbringe.
Also wenn ich jetzt sage, ich habe einen Algorithmus, der hat doppelt
so viele Ressourcen wie der Offline-Algorithmus und der darf außerdem
noch randomisiert sein.
Was ist der erwartete Kompetitive Ratio?
Ich weiß nicht mal genau, was da rausgekommen ist.
Ich habe da mit Experten gesprochen.
Ich vermute, das Ergebnis war, das bringt nichts Neues.
Aber ich bin nicht ganz sicher, ob das wirklich schon letztgültig
untersucht wurde.
So, jetzt nähern wir uns auch schon dem Ende des Kapitels.
Warum mache ich also kompetitive Analyse?
Also es gibt viele verschiedene Modelle für Entscheidungstreffen in
Abwesenheit vollständiger Informationen.
Ich habe schon gesagt, stochastische Modelle, ein bisschen spezieller,
aber in letzter Zeit in aller Munde, Machine Learning.
Angenommen, ich habe ganz viele Daten darüber, was in der
Vergangenheit passiert ist, dann kann ich versuchen, mit maschinellen
Lerntechniken einen Algorithmus zu finden, der zum Beispiel auch sagt,
welche Seite sollte ich rausschmeißen beim Paging.
Ich weiß nicht, ob das schon mal jemand gemacht hat.
Ich könnte mir vorstellen, dass das ganz gut ist.
Wobei meine Vermutung ist, dass es in der Praxis dann trotzdem nicht
besser ist als LRU.
Aber wahrscheinlich könnte man zeigen, dass man das auch lernen kann.
So ein Verhalten ähnlich zu LRU.
Dann wird hier als Argument geliefert, das ist jetzt Originalton Rob
van Steek.
Bin ich ganz sicher, ob das ein Vorteil oder ein Nachteil ist.
Wahrscheinlich beides.
Wir haben gesehen, Randomized Marking, das hilft einem irgendwie neue
Algorithmen zu finden, die erstaunlich gut sind.
Zum Beispiel auch Flush when full.
Das ist irgendwie eine gewisse Einsicht, dass das überraschend ein
guter Algorithmus ist.
Und man könnte es auch umdrehen.
Die Theoretiker schlagen uns hier Algorithmen vor, die in der Praxis
totaler Quatsch sind.
Und ich denke, beides ist wahr.
Ich habe irgendwie eine Möglichkeit, in einem theoretisch
wohldefinierten Framework mir zu überlegen, was könnten gute
Algorithmen sein.
Und das ist ein Vorteil.
Aber ich habe auch das Problem, ich bewege mich in einem theoretischen
Framework, das nicht immer ganz viel mit der Praxis zu tun hat.
Und muss damit rechnen, Algorithmen zu bekommen, die in der Praxis
nicht sinnvoll sind.
Also dessen muss man sich bewusst sein.
Wir haben ein bisschen Zeit, deshalb möchte ich auch noch eine
Geschichte erzählen, wo das noch ein bisschen klarer wird.
Und auch ein ganz klassisches Online-Problem.
Stellen Sie sich vor, ein ganz einfaches Scheduling-Problem.
Also Sie haben Maschinen, Sie kriegen Jobs mit bekannter Größe.
Und wenn ein Job ankommt, müssen Sie den einer Maschine zuteilen.
Jetzt kommen die ganzen Jobs an und am Ende gucken Sie sich den
Makespan an.
Also welche Maschine hat die größte Gesamtlast?
Also Summe der Fertigstellungszeiten der einzelnen Jobs.
Das ist Ihre Zielfunktion.
Da gibt es einen ganz einfachen zweikompetitiven Algorithmus.
Der sagt nämlich ganz einfach, schmeiße den Job immer auf die am
wenigsten belastete Maschine.
Und ich denke, das ist auch was ein menschlicher Operator zum Beispiel
auch tun würde.
Und was, glaube ich, auch im Maschinensetting viele Scheduling
-Algorithmen machen werden.
Und gut, zweikompetitiv ist im Lichte dessen, was wir hier für Paging
gesehen haben, ja auch schon ein schönes Ergebnis.
Aber im Framework von Online-Algorithmen gibt es bessere Algorithmen.
Die sind dann irgendwie 1,68 kompetitiv oder sowas.
Oder ich glaube, das ist dann sogar, sagen wir mal, die sind irgendwie
1,92 kompetitiv.
Das ist erstaunlich nah an der 2.
Oder es hat ganz lange gedauert, überhaupt weit weg davon zu kommen.
Also gute Nachricht, Sie haben jetzt einen Algorithmus, der ist noch
besser als der naheliegende.
Oder nicht?
Also ich weiß jetzt nicht im Detail, wie die Algorithmen
funktionieren, aber die Idee ist eigentlich ganz einfach.
Sie führen bewusst ein Ungleichgewicht in der Last der Maschinen
herbei.
Das heißt, Sie sorgen dafür, dass es immer wenig belastete und viel
belastete Maschinen gibt.
Und das gibt Ihnen die Flexibilität, wenn jetzt der Adversary Ihnen
dann plötzlich gegen Ende irgendwie einen fetten Job zuteilt oder
sowas, dass Sie den dann auf eine niedrig belastete Maschine schieben
können und die Gesamtlast einigermaßen ausgeglichen ist, sage ich mal.
Das ist schön für den Worst Case, aber Sie haben die ganze Zeit
bewusst eine schlecht ausgeglichene Last auf den Maschinen.
Und wenn zum Beispiel die Eingaben in der Anwendung ohnehin so sind,
dass die Jobs alle klein sind, dann würde der naive Algorithmus eine
fast perfekte Balancierung erreichen, während Sie bewusst sich vom
Best Case abwenden.
Das heißt, in der Realität ist das vielleicht ein total schlechter
Algorithmus, den Sie nur deshalb betrachten, weil der im Worst Case
ein bisschen besser ist als der naheliegende Algorithmus.
Und das ist vielleicht nicht das, was ein Praktiker haben will.
Also Vorsicht bei Competitive Algorithmen, aber man kann viel über den
Design Space von Algorithmen für ein Problem lernen, wenn man dieses
Competitive Analysis Framework wählt.
Ein anderes Argument, warum man vielleicht diesen Ansatz mit
Wahrscheinlichkeitsverteilungen nicht nehmen sollte, hat der Rob
geschrieben, die sind oft nicht bekannt.
Was noch viel schlimmer ist, meistens machen die irgendwie Annahmen,
dass die Ereignisse, die da passieren, unabhängig sind, die überhaupt
nicht stimmen.
Und das kann dann zu großen Abweichungen von der Realität widerführen.
Also probabilistische Modelle haben ihre eigenen Probleme.
Da muss man also auch vorsichtig sein.
Ja, und jetzt kommen hier weitere Nachteile von diesen
probabilistischen Modellen.
Und die Competitive Analysis gibt eine Garantie für die Performance.
Und das ist in einigen Anwendungen, ist die Garantie wichtiger als die
reale Performance.
Zum Beispiel nennt er jetzt Financial Planning oder ich sage jetzt mal
etwas allgemeiner, wenn da irgendwelche juristischen Dinge eine Rolle
spielen.
Wenn Sie garantieren müssen, dass Ihr Service mindestens so und so gut
ist und das wichtig ist, damit Sie nicht verklagt werden, dann ist
vielleicht diese Garantie wichtiger als die tatsächliche Performance.
Beziehungsweise vielleicht ist die Average Performance sowieso so gut,
dass das jedem egal ist, ob die dann noch ein bisschen schlechter
wird.
Aber Sie wollen auf keinen Fall, dass Sie irgendwelche Deadlines
verpassen oder sowas.
Oder jetzt gehe ich mal weg von dem Juristischen, Sie haben irgendwie
eine Echtzeitanwendung.
Sie wollen auf keinen Fall, dass irgendwie der Regler für das
Atomkraftwerk ab und zu mal ganz lange braucht und das Ganze dann
irgendwie aus dem Ruder läuft.
Das wäre nicht so gut.
So, Nachteile.
Das habe ich jetzt schon gesagt, das kann zu pessimistisch sein.
Aber man kann das ein bisschen abmildern durch Ressource Augmentation,
Randomisierung oder Einschränkung der Eingabe.
Diese Einschränkung der Eingabe war jetzt nur in diesem Future-Work
-Ding.
Also in diesem Chili-Ding.
Und Nachteil ist, dass man manchmal nicht unterscheiden kann zwischen
Algorithmen, die in der Praxis durchaus unterschiedlich sind, zum
Beispiel LRU und FIFO.
Aber das kann man durch verfeinerte Modelle wiederum abmildern.
Das war das Kapitel über Online-Algorithmus.