Schönen guten Tag.
Ich begrüße Sie zur Vorlesung Effiziente Algorithmen in diesem
Semester.
Wir haben uns letztes Mal wieder mit algorithmischer Geometrie
beschäftigt.
Kurze Frage noch mal.
Heute ist der letzte Tag der Anmeldung für die Klausur.
Wenn Sie sich anmelden wollen für Ende des Semesters, müssen Sie das
bis heute Abend gemacht haben.
Ansonsten können Sie erst am Ende des Wintersemesters die Prüfung
machen.
Also das noch mal als Vorbemerkung.
Einmal kurz, ich werde das einfach hier noch mal zu Beginn noch mal
raufschreiben.
Das kann ich ja kurz hier machen.
Dass das hier noch mal zu sehen ist.
Na, was ist hier los?
Stiftprüfungsanmeldung soll das heißen.
Bis 7.7.14.
Das noch mal als Erinnerung.
Und dann gehe ich hier aus dem Modus noch mal raus.
Beibehalten.
Und dann gucken wir noch mal kurz, was wir letztes Mal gemacht haben.
Wir hatten uns beschäftigt mit algorithmischer Geometrie.
Das hatte schon Herr Schugler angefangen vor zwei Wochen.
Und dann habe ich das weiter gemacht.
Da ging es um diese verschiedenen geometrischen Objekte.
Wir haben dort verschiedenste Fragestellungen angeschaut.
Das waren hier eine Reihe von unterschiedlichen Fragestellungen.
Die erste war gewesen, wie man Punkte, also Punktanfragen macht.
Wie viele Punkte innerhalb eines Rechtecks liegen.
Das hat also durchaus eine Reihe praktischer Bedeutung.
So ein Problem.
Dann haben wir uns gefragt, wie man feststellen kann, ob ein Punkt
innerhalb oder außerhalb eines Polygons liegt.
Da haben wir einfache Polygone betrachtet, bei denen man das durch
einen Strahl feststellen konnte und die Anzahl der Schnittpunkte
gezählt hat.
Das andere war beim konvexen Polygon, dass man dann dort das deutlich
einfacher machen kann mit einem Aufwand von Log N.
Wir hatten danach uns angeguckt, die Probleme, wie man Schnittpunkte
feststellen kann, also das Schneiden von irgendwelchen Kanten
überprüfen kann.
Wo schneiden sich irgendwelche Linien oder Geradensegmente in einem
Bild, in dem man irgendetwas machen muss.
Hier war es also die Frage, ob ein Polygon einfach ist oder nicht.
Man kann es aber deutlich allgemeiner darstellen, dass man
Liniensegmente hat und alle Schnittpunkte haben möchte.
Der Bentley-Ottmann-Algorithmus ist ein klassischer Algorithmus dafür,
weil der diese Methode des Plane Sweep eingeführt hat, die eine
allgemeine Methode ist, bei der man eben auf der vertikalen Linie im
Prinzip ein eindimensionales Problem löst und dadurch durch die Folge
der eindimensionalen Probleme das gesamte Problem lösen kann und
dadurch auf den Aufwand von Anzahl Haltepunkte mal Log N kommt.
Also in dem Fall N Log N.
Wir hatten dann das Problem der konvexen Hülle betrachtet letztes Mal.
Wir hatten zunächst einen einfachen Ansatz mit diesen Dreiecken.
Ganz interessant, aber natürlich sehr aufwendig.
Dann den Graham-Scan, der die einzelnen Punkte angeschaut hat.
Dann als nächstes den Jarvis-March, der nur die Extrempunkte bestimmt,
die dann auch garantierte Extrempunkte sind, während beim Graham-Scan
man nur eine Liste von potenziellen Eckpunkten oder Extrempunkten hat,
die sich aber dann später wieder als doch nicht Extrempunkte
herausstellen können.
Beim Jarvis-March hat man auf jeden Fall einen Punkt dann richtig
identifiziert als Extrempunkt, allerdings pro Punkt auf Aufwand linear
und deswegen ein Aufwand, der entsprechende Anzahl der Extrempunkte
dann zwischen linear und quadratisch liegen kann.
Dann hatten wir, das war das letzte gewesen, dann kommen wir heute zu
dem Entwurfsprinzip Divide and Conquer.
Auch dieses Entwurfsprinzip kennen Sie aus vielen verschiedenen
Gelegenheiten, vielen verschiedenen Problemstellungen.
Ein Problem ist uns zu groß.
Das übliche Problem der Informatiker, wir lieben keine großen
Probleme, sondern teilen sie auf und lösen lieber kleine Probleme und
überlegen uns, wie man die Lösungen der Teilprobleme geeignet
zusammensetzen kann.
In diesem Fall wäre das also folgendes Prinzip.
Wir haben hier unsere Punktmenge und wir teilen einfach unsere
Punktmenge auf.
Das heißt, hier sind irgendwelche Punkte drin in diesem Bild und wir
haben die entsprechend aufgeteilt auf zwei Teilmengen.
Wie man das macht, ist völlig beliebig.
Wie man die aufteilt in zwei Teilmengen, man sollte natürlich
normalerweise dafür sorgen, dass es in etwa gleich große Mengen sind.
Aber wie man das macht, ist völlig egal.
Hauptsache man hat zwei etwa gleich große Mengen, für die man dann
rekursiv wieder die konvexe Hülle bestimmt.
Und wenn die Punktmenge klein ist und ich zwei Punkte habe, sind
beides Extrempunkte, bei drei Punkten, da kann ich aufhören, dann habe
ich auf jeden Fall drei Extrempunkte.
Es sei denn, die liegen genau auf einer Linie, dann habe ich nur zwei
Extrempunkte.
Aber damit kann man eigentlich, das ist die Induktionsbasis dabei.
Und wenn ich dann also rekursiv meine konvexen Hüllen der beiden
Teilmengen M1 und M2 bestimmt habe, muss ich mir überlegen, wie bilde
ich daraus jetzt die konvexe Hülle des Gesamtproblems.
Wenn ich die konvexe Hülle habe, habe ich im Prinzip das Polygon.
Also den Rand, davon gehen wir mal aus, ich habe den Rand dieser
konvexen Hülle, also die Folge dieser Punkte.
Und die Frage ist, wie kann ich die jetzt geeignet zusammenbauen zu
einer konvexen Hülle insgesamt.
Also es ist halt die Frage, wie groß dieser Aufwand ist.
Ich sage, diese Schritte, das Aufteilen ist natürlich linear, das
Verschmelzen ist auch linear, sage ich.
Wieso ist das linear?
Also schauen wir uns das so einfach an.
Wir haben hier eine Folge von Punkten und jeweils konvexe Hülle
gegeben, natürlich der Rand der konvexen Hülle gegeben als Polygonzug.
Was wir machen können, ist folgender Trick.
Wir betrachten einfach einmal die obere Hälfte und dann die untere
Hälfte.
So, wenn ich die obere Hälfte betrachte, dann habe ich zwei
Teilmengen, zwei Mengen von Punkten, die jeweils sortiert sind in
Bezug auf ihre X-Koordinaten.
Und ich brauche die eigentlich nur zu verschmelzen.
Dann habe ich eine sortierte Reihenfolge.
Das Verschmelzen ist linearer Aufwand, das ist kein Problem.
Also in Bezug auf die X-Koordinaten.
Und dann habe ich also die Reihenfolge 1, 2, 3, 4, 5, 6 Punkte in dem
Fall.
Eine sortierte Reihenfolge der Punkte.
Und was mache ich auf so einer sortierten Reihenfolge von Punkten?
Ich möchte die konvexe Hülle bestimmen.
Ich gehe einfach entweder von links nach rechts hier rum.
Also so, so.
Dann stelle ich fest, hier habe ich natürlich einen konvexen Winkel.
In dem Fall, wenn ich hier rübergehe und dann darüber, habe ich hier
einen konkaven Winkel.
Das heißt, das ist kein Extrempunkt, den kann ich vergessen.
Das heißt, was ich hier mache, ist einfach ein Gram-Scan auf dieser
sortierten Reihenfolge.
Ich gucke einfach nach, wie sieht das aus mit den Winkeln zwischen
aufeinanderfolgenden Punkten.
Sobald ich hier einen konvexen, oder solange ich einen konvexen Winkel
habe, also einen konvexen Innenwinkel, bin ich zufrieden.
Wenn ich einen konkaven Winkel habe, muss ich den Punkt vergessen und
muss entsprechend dann in dem Fall diese Kante nehmen.
Und dann geht es entsprechend weiter und ich bin sehr schnell fertig.
Also das ist im Prinzip der Gram-Scan.
Wir wissen, der Aufwand für diesen Scan einmal durch ist linear in der
Anzahl der Punkte.
Das heißt, wir haben linearen Aufwand, um diese obere Hälfte zu
bestimmen.
Das gleiche können wir machen für die untere Hälfte und haben dann in
linearer Zeit insgesamt diese konvexe Hülle gefunden und können die
anderen Punkte, die hier drin liegen, dann entsprechend als Nicht
-Extrempunkte identifizieren.
Beziehungsweise die also rauswerfen.
Also der Aufwand oder dieses Verfahren ist relativ naheliegend.
Auf die Art und Weise kann ich also mit dem Divide-and-Conquer-Ansatz
auf N log N kommen.
Man kann das verbessern auf N log Anzahl der Extrempunkte.
H hatte ich schon vorher verwendet, also Anzahl der Extrempunkte in
der konvexen Hülle.
Darauf gehe ich aber nicht weiter ein.
Also Divide-and-Conquer ist auch ein typischer Ansatz.
Damit können wir auch die konvexe Hülle bestimmen.
Und dann kann man das natürlich auch parallel machen.
Rekursive Strukturen kann man auch parallel ausführen, entsprechend
dann den Aufwand reduzieren.
Das wäre dann so etwas ähnliches wie eben Merge, nicht Merge Sort,
sondern hier in dem Fall wäre das ein Verschmelzen der jeweiligen
Listen.
Das kann man sehr schön parallelisieren.
Gehe ich aber hier auch im Einzelnen nicht drauf ein.
Wäre etwas, was man nochmal dazufügen könnte.
Also parallele Variante könnte auch durchaus interessant sein.
Habe ich hier aber nicht mit drin.
Also hier steht nochmal, wie man das macht, die beiden konvexen Hüllen
zusammenfügen.
Habe ich gerade eben aber erläutert.
Die oberen Ränder bestimmen und dann entsprechend die beiden
verschmelzen zu einer Folge.
Und dann eben entsprechend die richtigen Winkel herausfinden und dann
nur die Winkel überprüfen von links nach rechts und dann ist man sehr
schnell fertig.
Also das ist einfach lineare Aufwand und dann ist man damit durch.
Auch hier gibt es eine, ich weiß gar nicht, ob ich das auch,
dieses auch tatsächlich...
Ich bin gar nicht verbunden mit dem Netz.
Lassen Sie mich ganz kurz ins Netz gehen.
Ich bin mir aber nicht sicher, ob ich überhaupt diese URL freigegeben
habe.
Das werden wir gleich feststellen.
Eigentlich hatte ich die alle freigegeben.
Da tut sich irgendwas.
Mal gucken.
Was macht er jetzt?
Ausführen.
Aha.
Und...
Den habe ich mir gar nicht vorangeguckt.
Die Weiden konker.
Genau.
Was macht er hier?
Ups.
Das wollte ich jetzt nicht.
Was habe ich denn jetzt gemacht?
Also hier muss ich gestehen, dass ich mir das vor...
Eigentlich...
Da ist es nochmal.
Das ist aber inkrementell.
Das will ich ja nicht.
Ich möchte die Weiden konker zeigen.
Genau.
Da haben wir es.
Und jetzt müsste er das eigentlich machen.
Das macht er jetzt in 3D.
Machen wir das mal einfacher in 2D.
Dann haben wir diese Menge.
Irgendwo muss das Ding doch starten können.
Wieso kann ich das Ding nicht starten?
Das ist ja seltsam.
Start.
Da ist es.
Irgendwas macht der hier nicht richtig.
Also ich will jetzt dafür keine Zeit verschwenden.
Das hätte ich mir vorher anschauen sollen.
Bitte?
Vielleicht liegt es daran, ich will jetzt die Zeit nicht verschwenden
dafür.
Letztes Mal ging das so gut mit den Animationen.
Deswegen habe ich mich darum gar nicht gekümmert in diesem Fall.
Ich dachte, das funktioniert einfach so.
Funktioniert aber nicht so.
Schauen Sie sich das selber an.
Der Link ist hier drauf.
Was dort passiert, habe ich Ihnen ja, glaube ich, gerade eben deutlich
genug dargestellt, wie der Algorithmus funktioniert.
So schwierig ist das ja eigentlich nicht.
Da war der Grahamscan und JarvisMath vielleicht ein bisschen
interessanter, das noch anzugucken.
Lassen Sie mich jetzt noch auf ein letztes Verfahren kommen.
Letzten Algorithmus Nummer 5, den ich Ihnen vorstellen möchte für
Konvexe Hülle.
Das ist ein wieder etwas anderes Prinzip.
Ich nenne das den Wegwerf-Algorithmus, Wegwerf-Prinzip.
Ich muss gestehen, dass ich gar nicht Ihnen sagen kann, wo ich den
gefunden habe.
Es ist schon lange her, dass ich mich damit beschäftigt habe.
Aber auch der Name Wegwerf-Prinzip muss ich eigentlich irgendwo
gefunden haben.
Ich kann nicht sagen, wo das tatsächlich herkam.
Aber das Prinzip ist ganz einfach.
Deswegen Wegwerf-Prinzip, weil man versucht, möglichst viele Punkte zu
eliminieren, die man nicht braucht.
Also sehr schnell zu sagen, ich kann ganz viele Punkte einfach
rausschmeißen.
Und wie funktioniert dieser Algorithmus?
Ich wähle einfach ein paar Extrempunkte aus, und zwar acht Stück.
Ich könnte auch vier nehmen, das würde nicht so viel bringen.
Acht Stück bringt ein bisschen mehr.
Ich könnte auch noch mehr nehmen.
Ich könnte noch jeweils einen Punkt dazunehmen.
Dann hätte ich 16 Punkte, könnte ich auch machen.
Oder 15 Punkte, wenn ich hier noch jeweils einen weiteren Extrempunkt,
also im Nord-Nord-Ost zum Beispiel, oder im Ost-Nord-Ost oder
irgendwas, Extrempunkte dazunehmen, würde es noch mehr bringen, aber
dann hätte ich mehr Aufwand zu treiben.
Hier ist Kompromiss, acht Punkte.
Und bei dieser schönen Menge, die ich Ihnen hier dargestellt habe,
sehen Sie, da sind ja fast alle Punkte bereits durch diese acht Punkte
eingeschlossen.
Das heißt, ich nehme mir die acht Extrempunkte her und eliminiere alle
Punkte, die im Inneren dieses konvexen Polygons E1 bis E8 sind.
Das heißt, das hier wäre E1, E2, E3, E4, dieses hier ist E8.
E1, E2, E3 und so weiter.
Jetzt eliminiere ich alle Punkte im Inneren.
Das ist ja relativ einfach.
Ich stelle fest, welche liegen links von...
also alle, die im Inneren von allen diesen Kanten liegen, die kann ich
rauswerfen.
Punkte, die auf der anderen Seite liegen, wie zum Beispiel hier diese
Punkte, die liegen zwar auf der rechten Seite von mehreren anderen
Kanten, aber eben links von außen bezüglich dieser Kante, die bleiben
drin.
Wir wissen, wie wir überprüfen, ob ein Punkt links oder rechts liegt
oder im Inneren oder Äußeren eines Polygons.
Das ist ein einfaches Polygon.
Ein einfaches, konvexes Polygon für jeden Punkt festzustellen, ob er
im Inneren oder Äußeren liegt, wissen wir ganz einfach.
Also der Aufwand ist sehr schnell zu machen.
Das ist linearer Aufwand.
Und ich muss für jeden Punkt feststellen, auf welcher Seite er liegt
für acht Kanten.
Und entsprechend muss ich anschließend die restlichen Punkte angucken.
Ich behalte also einige Punkte übrig.
Da sind diese Punkte dort, da ist noch ein Punkt, da sind ein paar
Punkte.
Natürlich, wenn ich Pech habe, hätte ich eine Situation, wo alle
Punkte außerhalb liegen.
Wenn ich einen Kreis habe, dann würden praktisch alle Punkte bis auf
die acht außerhalb liegen.
Dann hätte ich nichts gewonnen.
Wenn ich aber eine einigermaßen Gleichverteilung hier habe, wenn ich
das annehme, dass die Punkte einigermaßen gleichmäßig verteilt sind in
der Ebene, dann habe ich hier jeweils linearen Aufwand und
anschließend muss ich die restlichen Punkte betrachten.
Und der Aufwand dafür, na gut, da kann ich irgendein Verfahren nehmen,
um die konvexe Hülle zu bestimmen, um die restlichen Punkte zu
bestimmen.
Das ist dann Aufwand R log R.
Und wenn ich Glück habe, ist der Aufwand R log R ein konstanter
Aufwand.
Wenn ich eine Gleichverteilung der Punkte habe, dann ist der
Erwartungswert insgesamt linear, weil dieser Teil dann hier
verschwindet.
Und deswegen ist das ein sehr schnelles, effizientes Verfahren.
Ich mache so über den Daumen erstmal, wähle ich einfach ein paar
Punkte holistisch aus, von denen ich annehme, dass die dazu führen,
dass ich viele Punkte eliminieren kann, dieses Wegwerfen.
Und das, was dann noch übrig bleibt, das behandle ich mit dem
Standardverfahren.
Und das ist das Wegwerfprinzip.
Dann habe ich also ein einfaches, mittellineares Verfahren.
Im schlechtesten Fall natürlich immer noch N log N.
Aber bei linearem Aufwand.
Also ein sehr einfacher Ansatz.
Und mir liegt ja immer daran, dass ich versuche, Ihnen hier Prinzipien
zu vermitteln.
Und das wäre ein weiteres Prinzip, dass man eben versucht, mit wenig
Aufwand Informationen auszunutzen, vielversprechende Punkte
herauszunehmen, zu sagen, das sind garantierte Extrempunkte, diese
acht Punkte, das weiß ich ja, diese Extrempunkte in diesen Richtungen,
die kann ich mit jeweils linearem Aufwand bestimmen.
Und von dieser Teilmenge, dieser Menge der endgültigen Extrempunkte,
da kann ich dann eine ganze Reihe Entscheidungen treffen bezüglich der
übrigen Punkte und kann viele andere rauswerfen.
Zumindest unter der Annahme, dass ich eine einigermaßen gleich
verteilte Punktfolge habe.
Also das ist ein relativ einfaches Verfahren.
Was jetzt noch fehlt, ist etwas zu der unteren Schranke.
Wir waren jetzt von N hoch 4, war das schlechteste Verfahren,
runtergekommen bis auf im Mittellinear, bei dem Wegwerfprinzip.
Und jetzt geht es darum, wie weit können wir das runterdrücken.
Und da ist die Überlegung, wir gucken uns ein besonderes Polygon an.
Eine untere Schranke für den schlechtesten Fall wollen wir gerne
bestimmen.
Das heißt, wir müssen uns irgendeine Punktmenge angucken, für die wir
eine untere Schranke bestimmen können,
die in bestimmter Größenordnung ist.
Wir wissen, die obere Schranke ist N log N.
Die Weidenkonker hat das erreicht und genauso der GramScan.
Und jetzt nehmen wir eine Punktmenge.
Das sind Punkte, die liegen auf einer Parabel, hier angedeutet.
Das sind hier meine Punkte.
Die Punktmenge ist irgendwie gegeben, keineswegs sortiert.
Irgendwie eine Reihenfolge von Punkten, Menge von Punkten, paarweise
verschieden.
Und jetzt will ich die konvexe Hülle bestimmen.
Und bei dieser Punktmenge ist es natürlich so, dass alle Punkte, die
ich dort konstruiert habe, Extrempunkte sind.
Und die Aufgabe, um jetzt die konvexe Hülle zu bestimmen, besteht
eigentlich nur darin, diese Punktmenge zu sortieren.
Ich muss aus der gegebenen Menge von Punkten genau die richtige
Reihenfolge finden, bezüglich dieser X-Koordinaten.
Und dann habe ich sofort die konvexe Hülle bekommen.
Also allein die Menge der Extrempunkte reicht ja nicht aus.
Ich muss wissen, in welcher Reihenfolge die angeordnet sind.
Das heißt, ich habe diesen Sortieraufwand.
Und das heißt, dass ich über die untere Schranke für Sortieren im
schlechtesten Fall auch eine untere Schranke für die Konstruktion der
konvexen Hülle habe.
Und die untere Schranke für Sortieren kennen wir, das ist NlogN.
Damit haben wir auch für die konvexe Hülle als untere Schranke NlogN.
Aber diese Aussage gilt nicht für das mittlere Verhalten.
Beim mittleren Verhalten für beliebige konvexe Hüllen haben wir
festgestellt, wir haben O von N gefunden als eine Möglichkeit bei dem
Wegwerfprinzip.
Da hatten wir lineares Verhalten im Mittel.
Und selbstverständlich ist das auch die untere Schranke, dass wir
mindestens linearen Aufwand brauchen, um die konvexe Hülle zu finden.
Und das heißt Omega von N oder Theta von N ist die Schranke für das
mittlere Verhalten.
Und damit sind wir am Ende dieses Teils über algorithmische Geometrie,
was ich Ihnen darüber erzählen wollte.
Ich habe hier nur sequenzielle Verfahren Ihnen vorgestellt.
Ich habe ein paar Mal ein bisschen was erzählt über Parallelisierung.
Könnte ich vielleicht noch ein bisschen ausbauen.
Mal gucken.
Ich habe Ihnen hier vor allen Dingen diese anderen Lösungsansätze
vorstellen wollen.
Also dieses Planesweep-Verfahren.
Dann die Bedeutung der Vorbereitung, das war bei den Punktanfragen.
Da haben wir durchaus einen größeren Aufwand getrieben, um etwas
vorzubereiten und haben dadurch gewonnen eine sehr kurze Zeit für das
Durchführen der einzelnen Punktanfragen.
Und das letzte jetzt hier, dieses Wegwerfprinzip und dann eben noch
die untere Schranke, das waren so die wesentlichen Botschaften dieses
Kapitels.
Und es sind eine Vielfalt weiterer Fragestellungen da im Bereich
algorithmische Geometrie.
Sehr interessante Fragestellungen.
Ich hatte Ihnen so ein paar Dinge mal angesprochen.
Das gibt also zum Beispiel diese Galerieprobleme, die habe ich
überhaupt nicht erwähnt.
Wenn Sie irgendeine toll konstruierte Galerie haben, die eine sehr
seltsame Struktur hat oder irgendein Gebilde, ist so eine typische
Frage, wie bestimme ich die minimale Anzahl von Wachleuten in solch
einer Galerie.
Es gibt eine ganze Reihe weiterer Probleme, die man da anschauen kann.
Und das heißt, das ist ein Teilgebiet der algorithmischen Geometrie,
Galerieprobleme.
Es gibt ein ganzes Buch, ein dickes Buch über Galerieproblems.
Es gibt viele schöne Bücher über algorithmische Geometrie.
Wer sich damit genauer beschäftigen möchte, ist dazu herzlich
willkommen.
Interessantes Gebiet.
Hat viele Anwendungen im Bereich Computergrafik.
Wie kann ich effizient Gegenstände auf dem Bildschirm darstellen?
Und das hier, das Problem mit den Galerieproblemen, ist natürlich
jetzt weniger ein Computergrafikproblem, sondern ein wirkliches
Überwachungsproblem in dem Fall.
Videoüberwachung von irgendwelchen komplexen Strukturen ist durchaus
ein Problem, was man sich genauer angucken kann.
Also, das zu diesem Kapitel, damit sind wir damit schon durch.
Und wir kommen zu dem nächsten Kapitel, nämlich den verteilten
Algorithmen.
Ich hatte gesagt, ich habe bei der algorithmischen Geometrie jetzt
gerade die Parallelisierung ein bisschen stiefmütterlich behandelt.
Hier mache ich auch keine Parallelisierung in dem Sinne, sondern in
diesem Fall erzähle ich Ihnen etwas über verteilte Algorithmen.
Ich habe das ein paar Mal erwähnt.
Eine andere Rechnerinfrastruktur, die man sich eigentlich angucken
muss, ist das Prinzip der verteilten Berechnungen.
Und im Gegensatz zu parallelen Berechnungen müssen wir bei verteilten
Berechnungen insbesondere die Kommunikation genauer anschauen.
Beim Parallelrechner gehe ich normalerweise davon aus, dass ich eben
eine Struktur habe mit einem festen Verbindungsnetz.
Also irgendein Verbindungsnetz, das die Kommunikation erlaubt.
Das kann sein, dass ich hier so ein Mesh of Tree habe oder eben hier
so ein Butterfly-Netzwerk oder irgendeine wie hier zweidimensionale
Gitterstruktur.
Wir hatten gesehen, wie man dort Kommunikation im Prinzip machen kann.
Da brauche ich die Kommunikation nicht wirklich als extra Aufwand zu
berücksichtigen.
Da ist der wesentliche Aufwand die Anzahl der Schritte, die ich mache.
Die parallel ausgeführten Berechnungen.
Kommunikation ist dort im Prinzip in einer Einheit mit drin.
Uniformes Modell, uniformes Kostenmodell, die Zeiteinheit ist die
Einheit für Ausführung einer Berechnung in einer Zelle und die
Kommunikation ist damit eingeschlossen.
In dem Augenblick, wo ich verteilte Berechnungen mache, sieht das
alles anders aus.
Da habe ich irgendwelche Rechner, die miteinander reden wollen und ich
habe irgendein Kommunikationsnetz und die können Nachrichten schicken
in das Kommunikationsnetz und irgendwann kommen die Nachrichten an.
Und sie wissen, dass der Aufwand für das Verschicken von Nachrichten
groß ist.
Wenn Sie sich anschauen, die Taktfrequenzen Ihres Rechners, die sind
im Gigahertz-Bereich.
Das heißt, Sie haben wenige Nanosekunden für das Ausführen von
einzelnen Operationen.
Wenn Sie einen Ping machen zum anderen Rechner, sind Sie im
Millisekunden -Bereich.
Das heißt, Sie haben da 10 hoch 6 Unterschied in dem Aufwand.
Das heißt, im Prinzip muss man hier ganz anders an die Algorithmen
rangehen.
Ich darf nicht so tun, als wenn Kommunikation mir geschenkt wird.
Also, ich möchte gerne eine Menge sequentieller Prozesse ausführen,
die unabhängig voneinander arbeiten.
Zum Beispiel sage ich, ich habe ein großes Rechnernetz auf der Welt.
Ich schicke einfach meine Aufträge an diese vielen verschiedenen
Rechner und die sollen die Arbeit ausführen.
Und die können also unabhängig voneinander arbeiten, die bekommen nur
irgendwelche Daten geschickt, irgendwelche schönen Rechenpakete, die
sie der Reihe nach ausführen sollen.
Und die koordinieren ihre Aktivitäten durch Kommunikation auf
irgendeine Art und Weise, schicken sich Nachrichten in einem
verteilten System.
Das heißt, ich habe ein räumlich weit verteiltes Netz.
Die einzige Anforderung ist, ich kann Nachrichten schicken.
Und ich habe eben diese unabhängigen, leistungsfähigen Prozessoren,
Workstation -Netze, PC-Netze.
Ich kann auch sagen, ich rechne irgendwo in der Cloud.
Wobei in der Cloud rechnen ist noch ein bisschen was anderes.
Wenn ich in der Cloud rechne, also wenn ich hier in so eine Wolke
reinschaue, da kann es natürlich sein, dass hier ein dicker, fetter
Prozessor sitzt, der die ganzen Berechnungen durchführt.
Das wäre keine verteilte Berechnung.
Das wäre eigentlich Cloud-Computing, heißt, ich schicke die Sachen
irgendwo hin und dann werden die Sachen da ausgeführt.
Ich habe aber nicht unbedingt viele Rechner, die gleichzeitig
arbeiten.
Man kann auch in einer Cloud auch virtuell viele Rechner arbeiten
lassen.
Wenn man zum Beispiel diese Elastic Cloud von Amazon verwendet.
Hat jemand von Ihnen schon mal Elastic Cloud benutzt von Amazon?
Noch nicht?
Können Sie ganz einfach sich Rechenzeiter kaufen, kostet ein paar
Cent.
Und Sie können sich ganz viele kleine Rechner definieren, virtuelle
Rechner, die irgendwo dann tatsächlich laufen.
Manchmal laufen die aber auch alle nur auf Teilen eines großen
Rechners.
Das kann auch passieren.
Also da weiß man nicht so genau, wo die tatsächlich laufen.
Sie können aber natürlich insbesondere auch alle Rechner ansprechen
hier auf dem Unicampus.
Alle Rechner im Institut AEFB, in der WIWI-Fakultät, im Rechenzentrum.
Wir machen das zum Beispiel mit unserem System Josh Car.
Das ist das Job Scheduling Karlsruhe.
Das ist an meinem Institut entwickelt worden, wo wir Aufträge
weitergeben an Rechner, die bereit sind, die auszuführen.
Da werden im Prinzip alle Rechner im Zip-Pool dafür genutzt, die im
Hintergrund dann Aufträge ausführen für irgendwelche
Simulationsrechnungen, die wir machen im Rahmen unserer
Forschungsarbeiten.
Und das wird von vielen Instituten am KIT mittlerweile genutzt, dass
man im Prinzip im Hintergrund Aufträge bearbeiten lässt.
Das ist also dann wirklich verteiltes Rechnen.
Und dann muss man durchaus auch die Kommunikation anschauen.
Und das werden wir jetzt gleich noch genauer betrachten, was das
eigentlich heißt.
Ich kann auch alle Rechner im Clicknetz.
Clicknetz ist eins, das war mal ein Netz, muss ich eigentlich mal
rausnehmen.
Ich weiß gar nicht, ob es das noch gibt, ein Netz hier in Baden
-Württemberg.
Dann können Sie alle Rechner in Banken, bei IBM, bei SAP, alle Rechner
im Internet sich anschauen, also weltweit viele Rechner, die
miteinander kommunizieren können.
Und was müssen nun verteilte Algorithmen machen?
Ich setze die natürlich ein, weil ich meine Rechenlast, die ich habe,
verteilen möchte auf viele andere Rechner.
Das soll schneller ausgeführt werden, als wenn ich es lokal mache.
Also muss ich wirklich große Aufgaben haben, die dort ausgeführt
werden sollen.
Aber dann müssen diese Berechnungen auch sinnvoll ausgeführt werden.
Und jetzt geht es darum, das ist das, was wir bei verteilten
Algorithmen anschauen, was sind die speziellen Probleme, die
auftreten, die ich noch bearbeiten muss, wenn ich Berechnungen
verteile auf beliebig viele Rechner.
Und es gibt eben eine Reihe Probleme, die ich hier betrachten muss,
die ich nur in verteilten Rechnern habe.
Zuverlässige Kommunikation und Kooperation.
Wenn ich eine Nachricht schicke über meine dicke Wolke hier, über
meine Kommunikationswolke von A nach B, dann soll eine Nachricht, die
hier rausgeschickt wird, auch irgendwann tatsächlich ankommen.
Zuverlässige Kommunikation.
Dann muss ich wissen, wer kann hier eigentlich mit wem reden, was für
eine Netztopologie habe ich, wie sind die verbunden, welche Rechner
sollten eigentlich miteinander reden, weil sie nahe einander liegen
und nicht so große Latenzzeiten haben, wenn ich dort Nachrichten
verschicke.
Also was für eine Topologie habe ich eigentlich?
Habe ich da irgendwie eine Gitterstruktur oder habe ich einen Ring
oder habe ich eine Baumstruktur?
Was ist die Topologie der Rechner, die ich tatsächlich verwenden kann?
Oder habe ich nur irgendwie die Möglichkeit, Nachrichten
rauszuschicken?
Ist jeder mit jedem verbunden?
Wie werden meine Nachrichten weitergeschickt?
Werden die direkt geschickt?
Müssen die irgendwie warten?
Also das Message Routing durch eine Netztopologie ist auch ein
wichtiger Punkt, weil das die Zeit beeinflusst, die ich brauche, um
Nachrichten rauszuschicken.
Dann ist die Frage, ich habe jetzt an verschiedenen Rechnern in meinem
Netz Aufgaben bearbeitet.
Alle bearbeiten irgendwelche Tasks da drin.
Und ich muss natürlich wissen, wann machen die das eigentlich?
Ich brauche eine gewisse Information über die Zeit, zu der eine
gewisse Berechnung gemacht wurde.
Ich möchte ja später wissen, was ist dort tatsächlich alles bearbeitet
worden, wie viel Rechenzeit muss ich abrechnen und ähnliche Dinge.
Aber wenn ich an verschiedenen Orten etwas tue, wie sieht das mit der
Zeit aus?
Hier habe ich eine Zeit T1, da habe ich eine Zeit T2, da habe ich eine
Zeit T3.
Wie kann ich eigentlich die Zeitrechnung auf verschiedenen Rechnern
koordinieren?
Die müssen ja nicht unbedingt alle die gleiche Zeit haben.
Es kann natürlich sein, dass die über ein globales Zeitsignal
koordiniert sind.
Es kann sein, dass die alle irgendwie über GPS koordiniert sind.
Aber normalerweise oder zunächst mal sind das Rechner, die irgendwie
laufen, die irgendeine lokale Zeit haben und die können abweichen
voneinander.
Dann muss ich sehen, wie kann ich das einigermaßen synchronisieren.
Es ist also wichtig, wenn die alle etwas gemeinsam tun sollen und an
einer gewissen Zeit, meinetwegen in Berechnungsrunden laufen, was ist
eine Berechnungsrunde, wann geht die nächste Berechnungsrunde los?
Dann müssen die sich synchronisieren.
Datenverwaltung ist natürlich auch klar.
Wer hat welche Daten?
Zugriffe sind wichtig.
Wer darf auf Daten zugreifen?
Wer darf Daten schreiben?
Replikation ist auch ein wichtiger Punkt.
Ich möchte Daten nicht immer hin und her schicken, sondern ich möchte
die Daten eigentlich an verschiedenen Stellen aufbewahren.
Es gibt diese ganze Verteilung von Daten in Peer-to-Peer-Netzen mit
Redundanz, sodass die, auch wenn ein Rechner mal ausfällt, trotzdem
alle Daten noch verfügbar sind.
Wir kennen das bei diesen ganzen Peer-to-Peer-Netzen für irgendwelche
Videodateien oder ähnliches.
Große Datenmengen, die weltweit irgendwo im Netz verteilt sind.
Und durch Replikation erreicht man, dass man zuverlässig darauf
zugreifen kann.
Wenn ich Replikation mache, brauche ich Konsistenz.
Wenn ich etwas verändert habe in einer Kopie, müssen die anderen
Kopien auch entsprechend verändert werden.
Dann die Synchronisation von Startzeiten.
Ich habe Berechnungen, die auf vielen Rechnern laufen sollen.
Woher weiß ich, dass die alle gleichzeitig anfangen?
Das sind ganz alte Probleme.
Es gibt immer militärische Anwendungen.
Ich möchte mit mehreren verteilten Kompanien einen Feind gleichzeitig
angreifen.
Wie kann ich gewährleisten, dass die alle wissen, wann sie tatsächlich
anfangen sollen?
Also Synchronisation von Startzeiten ist ein uraltes Problem.
Terminierungserkennung.
Ich lasse eine Berechnung laufen auf vielen verschiedenen Rechnern.
Und jetzt möchte ich wissen, wann bin ich eigentlich fertig?
Und wie weiß jeder einzelne Rechner, dass alle anderen auch schon
fertig sind?
Stellen Sie sich vor, ein verteiltes Suchverfahren.
Sie wollen irgendeinen Algorithmus ausführen, der über irgendeinen
großen Baum läuft.
Und Sie wissen, irgendwo gibt es einen Pfad in diesem großen Baum, der
zu einer Lösung führt.
Und derjenige, der diese Lösung entdeckt hat, bestimmt im Prinzip,
wann das Ganze fertig ist.
Wenn ich also an einer Stelle eine Lösung gefunden habe, sollen alle
anderen im Prinzip aufhören.
Ich muss dann auch darüber informieren, dass ich jetzt fertig bin,
dass alle anderen auch wissen, wir sind fertig.
Und dann am Ende alle wissen, die Berechnung ist beendet und wir
kennen vielleicht auch alle das Ergebnis.
Ein solches Problem habe ich bei der Leader Election.
Also wenn ich einen Anführer wählen möchte, das ist ein typisches
Konsensverfahren oder Abstimmungsverfahren.
Viele Rechner wollen eine Aufgabe gemeinsam bearbeiten und müssen sich
einigen darauf, wer der Anführer ist.
Wer sagt, wann es losgeht, wann man fertig ist und so weiter.
Das heißt, ich habe hier einen Konsens zu erzielen zwischen einer
Reihe von beteiligten Knoten und muss am Ende sicherstellen, dass alle
der gleichen Meinung sind darüber, welches Ergebnis man erzielt hat.
Dann muss ich dabei noch darauf achten, dass es Fehler geben kann.
Es kann sein, dass Verbindungen nicht funktionieren, dass Rechner
ausfallen und ähnliches typisches Problem in großen Rechnernetzen.
Und dann muss trotzdem das richtige Ergebnis rauskommen.
Also es gibt grundsätzliche Aussagen darüber, inwieweit man zum
Beispiel Konsensverfahren trotz des Auftretens von Fehlern immer noch
richtig ausführen kann.
Also wenn Sie wissen wollen, alle Rechner müssen sich einig sein
darüber, was man eigentlich berechnet hat, welches Ergebnis man
gekommen ist und Sie warten darauf, dass ein Rechner antwortet, der
aber gar nicht mehr antworten kann oder der Fehlermeldungen schickt.
Wie geht man damit um?
Kann man trotzdem noch zu Konsensverfahren kommen?
Das sind vielfältige Probleme, die man nicht hat, wenn man parallel
arbeitet, weil ich dann von vornherein von der Architektur her, dass
diese ganzen Probleme anders lösen kann.
Das sind Probleme, die muss ich im Prinzip bei verteilten Algorithmen
mir anschauen und die kommen eben dazu, zu dem eigentlichen Ausführen
der Probleme, die ich tatsächlich gelöst haben möchte.
Also typische Beispiele, Suchmaschinen, Absuchen des Internets nach
neuer, relevanter Information.
Da gibt es vielfältige Anwendungen für, ich schicke Software über
verschiedene Rechner hinweg und die sollen jetzt suchen.
Ich habe nicht einen Rechner, der an vielen anderen der Reihe
nachguckt und dort nach Informationen sucht, sondern ich setze viele
Rechner ein, um Informationen zu extrahieren und lasse mir dann die
Informationen schicken auf meine zentrale Suchmaschine oder den
zentralen Katalog.
Das Bearbeiten von Anfragen bei Suchmaschinen ebenso, kann man
verteilt machen, muss nicht hochparallel sein.
Kann sein, dass ich das also irgendwie in einem Netz verteile.
Verkehrssteuerung, ich habe lokal erhobene Daten, ich habe
Informationen über Situationen in der Nachbarschaft, ich habe hier
meinetwegen irgendein Verkehrsnetz und ich möchte jetzt vielleicht
irgendwelche hier, ich möchte steuern, wie jetzt der Verkehr an einer
Kreuzung ablaufen soll, dann habe ich lokale Informationen über die
Nachbarschaft, ich weiß, wie der Verkehrsfluss ist, in der Richtung,
in der Richtung, in der Richtung, durch die verschiedenen
Möglichkeiten hier einer Kreuzung definiert.
Der Verkehr wird gemessen, ich habe Informationen über die
Nachbarschaft, ich entscheide, wie ich meine lokale Ampel steuere und
ich möchte aber eigentlich auch in der Lage sein, zu entscheiden, wann
ich eine grüne Welle haben soll, soll vielleicht der Verkehr hier über
diese drei Kreuzungen hinweg in der grünen Welle laufen, das werde ich
nur dann haben wollen, wenn dadurch der Verkehr insgesamt besser
läuft, das heißt, wenn die Wartezeiten oder Anzahl der Halte insgesamt
für den Verkehr reduziert werden.
Dazu müssen die sich gegenseitig abstimmen, dann brauche ich einen
verteilten Algorithmus, um also so ein Konsensverfahren zu, oder als
Ergebnis eines Konsensverfahrens, eine grüne Welle einzurichten.
Das heißt, ich muss synchronisierte Grünzeiten haben, zwischen hier
drei aufeinanderfolgenden Verkehrsampeln.
Solche Dinge haben wir also in anderem Zusammenhang auch mal bei uns
entwickelt, also solche verteilten Entscheidungen sind an vielen
Stellen zu treffen, können Sie sich verschiedenste Infrastrukturen
vorstellen, wo man so etwas braucht.
Bei Energiesystemen ebenso, Demand-Site-Management ist etwas, wo Sie
viele Demand-Site-Manager haben, die sich irgendwie koordinieren
müssen.
Eine Koordinierungsmöglichkeit sind also Märkte, dass man sich über
Marktmechanismen abstimmt gegenseitig, auch das ist eine Möglichkeit,
wie man Kooperationen in verteilten Systemen erreichen kann.
Und auch da muss man sich darüber einigen, wer wann welche Nachfrage
extra dazufügt oder abschaltet und ähnliches.
Beim Data-Mining, wenn Sie Daten beschaffen wollen aus großen
verteilten Datenbanken, auch das wird häufig verteilt gemacht, es gibt
so eine schöne Anwendung, bei der man versucht, die Information aus
extraterrestrischen Daten irgendwie rauszufinden, also irgendwelche
Signale aus dem Weltraum aufgesammelt, versucht man rauszufinden, ob
es da irgendwelche interessanten Muster gibt.
Sobald ich Muster finde, die sich wiederholen, kann ich davon
ausgehen, dass das irgendwelche signifikanten Nachrichten sind oder
interessante Nachrichtenquellen.
Und solche Dinge kann man zum Beispiel sehr einfach verteilen auf
viele Rechner, dadurch, dass man Leute oder Personen fragt, darf
dieser Algorithmus ausgeführt werden, wenn der Bildschirmschoner
läuft, wenn also keine Aktivität auf dem Rechner ist, der
Bildschirmschoner springt an, das heißt der Rechner macht nichts
wirklich für den Konkreten, der den Rechner jetzt gerade nutzen will
und dann kann ich praktisch mit dem Bildschirmschoner ein solches
Verfahren abarbeiten, überprüfen, ob da irgendwelche interessanten
Muster in einem bestimmten Datenpaket sind.
Solche Anwendungen sind gelaufen, hunderttausende Rechner überprüfen
auf die Art und Weise, ob man irgendwelche interessante Informationen
in irgendwelchen Daten finden kann, die aus dem Weltraum hier auf die
Erde gelangen.
Irgendwelche Funkmuster, Strahlungsmuster oder ähnliches.
Also das ist das ganze Thema Big Data, was wir im Augenblick haben,
ist auch so ein Thema, wie kann ich mit den riesigen Datenmengen, die
ich habe, wie kann ich dort Daten beschaffen.
Wir reden heutzutage darüber, dass wir Petabytes an Daten haben, also
Terabytes sind schon gar nichts Besonderes mehr.
Wenn Sie sich den Large Hadron Collider, das Experiment in Genf
angucken, wo man eben versucht, interessante Teilchen zu finden, Sie
wissen, dass man dort das Higgs-Teilchen tatsächlich entdeckt hat,
nachgewiesen hat, das war eine große Hoffnung dieses Large Hadron
Colliders, man hat tatsächlich das Higgs-Teilchen gefunden.
Und da sind riesige Datenmengen aufgesammelt worden, mehrere Terabyte
pro Tag, die zum überwiegenden Teil hier in Karlsruhe auch gelagert
werden und von da aus dann auch an alle möglichen anderen Stellen
laufen.
Da arbeiten viele Rechner an verschiedensten Stellen dran, solche
Daten geeignet zu analysieren.
Wir reden im Augenblick gerade davon, dass wir das Smart Data
Innovation Lab hier in Karlsruhe einrichten.
Wenn Sie auf die Seite www.sdeal.de gehen, dann finden Sie
Informationen über sDeal, Smart Data Innovation Lab, große Datenmengen
aus Bereichen wie Verkehr oder Smart City oder Gesundheit oder
Industrie 4.0 oder Energie, werden dort aufgesammelt und können
systematisch dann weiterverwendet werden.
Nicht nur Big Data, sondern Smart Data, das heißt, es geht darum, wie
kann ich interessante Informationen aus großen Datenmengen ableiten.
Das sind alles Anwendungen, wo ich mich auch mit den problemverteilten
Algorithmen beschäftigen muss.
Und ich habe eben bei diesen Beispielen eigentlich keine sinnvolle
Alternative zur verteilten Bearbeitung.
Ich muss dezentral arbeiten.
Im zukünftigen Energienetz müssen wir dezentral arbeitende Komponenten
geeignet koordinieren und zu einer sinnvollen Gesamtsituation kommen,
Stabilität erreichen und ähnliche Dinge.
Viele interessante Aufgaben, alles Aufgaben bei verteilten
Algorithmen.
Das ist zu vorbemerken jetzt genug.
Jetzt müssen wir uns damit beschäftigen, was kostet das?
Wie bewerten wir den Aufwand für verteilte Algorithmen?
Was wir bisher betrachtet haben, war die Rechenzeit in Prozessoren.
Und dann kommt jetzt noch dazu der Kommunikationsaufwand.
Und die Frage ist, wie ist der Kommunikationsaufwand?
Wir können zählen die Anzahl der Nachrichten.
Jetzt schickt ein Prozessor, der schickt jetzt hier eine Folge von
Nachrichten, eine kleine Nachricht, eine sehr dicke Nachricht, wieder
eine kleine Nachricht, kleine Nachricht und so weiter.
Wir wissen, die schicken alle Datagrams, die haben eine gewisse Größe.
Aber wenn ich jetzt nur mir abstrakt den Rechner angucke, der schickt
bestimmte Datenumfänge oder Nachrichtenumfänge.
Ist es da ausreichend, die Anzahl der Nachrichten zu zählen?
Muss ich nicht die Länge der Nachrichten anschauen, analog zu dem, was
wir ganz zu Anfang gemacht haben, bei den Kostenmodellen für
Berechnungen hat man gesagt, die Länge der Zahlen, die bearbeitet
werden, spielt eine Rolle.
Hier müsste doch eigentlich die Anzahl der Bits aller Nachrichten eine
Rolle spielen.
Also wenn ich nur die Anzahl der Nachrichten zähle und ich habe ein
TCP -System, bei dem ich das einteile in relativ kleine Datenpakete
aufgrund der Randbedingungen des Netzes oder ich habe ein ATM
-Netzwerk, wo ich wirklich feste Blockgrößen habe.
Also die Anzahl der Nachrichten wäre dort unfair gegenüber einem
Verfahren, bei dem ich wirklich viele Daten innerhalb einer großen
Nachricht zusammenfassen kann.
Also Anzahl Bits aller Nachrichten wäre vielleicht etwas, was man sich
anschauen muss und nicht die Anzahl der Nachrichten.
Es sei denn, ich gehe davon aus, ich habe immer eine konstante Länge
pro Nachricht.
Das wäre aber das Gleiche wie Anzahl Bits der Nachrichten zu zählen.
Und dann muss ich mir die Übertragungszeiten anschauen.
Und da hatte ich schon gesagt, Übertragungszeiten sind lang.
Extrem lang im Vergleich zu dem, was wir als Rechenzeit zu
berücksichtigen haben.
Und ich könnte also messen, wenn ich hier Informationen schicke
zwischen irgendwelchen Rechnern, wie lang ist jetzt die Zeitdelay
hier, wenn das A, B und C sind, Delay A, B, Delay B, C und so weiter.
Wie lange dauert das eigentlich, Informationen hin und her zu
schicken?
Es wird allgemein gesagt, Rechenzeit rechne ich eigentlich gar nicht.
Kann ich vernachlässigen.
Bei all diesen Problemen, die ich gerade eben genannt habe, und die
wollen wir betrachten, ist eigentlich der Rechenaufwand lokal sowieso
klein.
Das Wesentliche ist die Abstimmung zwischen den einzelnen Knoten, das
heißt, da kann es nur um die Anzahl der Nachrichten gehen.
Und deswegen zähle ich da zunächst mal nur den Kommunikationsaufwand.
Wenn allerdings der Berechnungsaufwand sehr hoch ist, dann sieht das
ja so aus, dass ich hier irgendwo etwas berechne, kommuniziere zu
einem anderen Rechner, dort wieder etwas berechne und wenn ich dafür
sorgen kann, dass diese Zeit, in der etwas berechnet wird, wenn das
wirklich eine lange Zeit ist, also wirklich dicke Berechnungen, die
gemacht werden müssen, und ich vielleicht dafür sorgen kann, dass
diese Zeit für die Kommunikation irgendwie versteckt wird hinter
Berechnungen.
Dadurch, dass das ein anderer Teilprozessor macht.
Ich habe einen extra Prozessor für Kommunikation und der Rechner kann
eigentlich die ganze Zeit mit seinem Hochleistungsprozessor sinnvolle
Berechnungen machen.
Dann kann ich sagen, dann kommt es eigentlich im Wesentlichen auf die
Rechenzeiten an und weniger auf den Kommunikationsaufwand.
Und das ist etwas, was dann bei dem tatsächlichen Einsatz von
verteilten Anwendungen eine Rolle spielt.
Wie kann ich erreichen, dass der Kommunikationsaufwand versteckt wird
hinter dem Berechnungsaufwand?
Man nennt das Latency Hiding.
Latency Hiding ist also die, das ist hier die Latenzzeit oder hier
oben die ist DAB, DBC.
Die Latenzzeit, wie lange dauert es, eine Nachricht von A nach B zu
schicken, selbst wenn die Bandbreite sehr hoch ist.
Ich habe eine gewisse Latenz, die ich einfach brauche, um von A nach B
zu gelangen.
Und wenn ich diese Zeit verstecken kann hinter Berechnungen, dann habe
ich den Kommunikationsaufwand im Prinzip vernachlässigbar.
Das ist eine wichtige Art bei der Gestaltung von verteilten
Berechnungen, das so zu machen, dass die eben nicht warten müssen, bis
Information von A nach B gelangt ist, sondern dass ich es weitermachen
kann.
Ein typisches Prinzip, das man dort einsetzt.
Und ich möchte jetzt zu einem Problem kommen, das wir uns genauer
angucken.
Das ist das, was ich hier mir raussuche für diese wenige Zeit, die ich
noch habe, heute und nächste Woche.
Leader Election, Wahl eines Anführers.
Und ich kann auch sagen, Konsensprobleme.
Wahl eines Anführers ist ein typisches, einfaches Konsensproblem.
Und Sie werden sehen, man kann dort eine Reihe von interessanten
Erkenntnissen gewinnen, wenn man sich dieses Problem anschaut.
Es ist die Frage, was habe ich eigentlich für Anforderungen, wenn ich
ein Konsensproblem bearbeiten muss oder ein Leader Election Problem.
Und es gibt so eine Reihe von Annahmen bei verteilten Algorithmen,
dass man sagt, etwas ist verteilt, das soll symmetrisch sein.
Ich habe hier also symmetrisch, vollständig verteilt.
Das heißt, ich habe gleichberechtigte Prozesse, die alle die gleichen
Eigenschaften haben, die alle gleich vorgehen sollen.
Sie kennen das Philosophenproblem aus Grundlagen Informatik 2
vielleicht noch.
Das Philosophenproblem ist ein typisches Problem der verteilten
Berechnungen.
Und sie sind alle gleichberechtigt.
Und jetzt brauchen die einen Koordinator oder einen Anführer oder eine
Zentrale.
Sie erinnern sich bei dem Philosophenproblem, da haben wir die vielen
Philosophen, die um einen Tisch herum sitzen und alle hier ihre Teller
vor sich stehen haben.
Und das Problem ist, dass die jeweils nur eine Gabel dazwischen liegen
haben.
Sie brauchen aber, um zu essen, halt zwei Gabeln und müssen sich
einigen, wer jetzt eine Gabel nehmen darf und wer nicht.
Wenn Sie da einen Anführer wählen, kann der sagen, wer jetzt essen
darf und wer nicht.
Also typisches Problem bei Philosophen in einer verallgemeinerten
Form.
Und Sie wollen jetzt bei solchen gleichberechtigten Prozessen einen
neuen Anführer wählen.
Und die Anforderungen sind, dass das symmetrisch gleich verteilt ist.
Das heißt, wenn das symmetrisch ist, sind alle gleichartig beteiligt.
Eine typische Annahme ist, ich darf nicht jemanden wählen aufgrund
seiner Identität, also aufgrund seines Namens.
Ich muss andere Dinge wählen.
Sonst könnte man ja einfach den mit der kleinsten Nummer auswählen.
Tatsächlich macht man das so, wenn man sagt, das kommt nicht darauf
an.
Aber zunächst mal sagt man, eigentlich soll jeder die gleiche
Möglichkeit haben, Leiter zu werden.
Dann darf ich ihn nicht nach dem Namen auswählen, nach dem Alphabet.
Geht nicht.
Alle Beteiligten sollen in gleicher Weise mitwirken.
Symmetrisch.
Alle in der gleichen Art und Weise, sonst wären sie ja nicht
gleichberechtigt.
Hat was ähnliches wie allgemeine gleiche freie Wahlen und so weiter.
Und am Ende der Wahl des Leiters müssen alle Beteiligten die gleiche
Information über die Identität des Leiters haben.
Alle müssen wissen, wen sie gewählt haben.
Der Leiter muss wissen, dass er gewählt wurde.
Und alle anderen müssen wissen, dass er der Leiter ist.
Ganz einfaches Problem.
Sie sehen, man hat hier schon eine Reihe Anforderungen, die man hier
stellt.
Und das, was hier also gefordert ist, heißt, ich brauche einen in den
Termen der verteilten Algorithmen, einen vollständig verteilten
symmetrischen Algorithmus.
Alle entscheiden lokal mit identischem Algorithmus.
Und wenn man sich das genauer anschaut, jetzt nehmen wir noch an,
Topologie, welche Kommunikationsstruktur haben wir.
Wir nehmen an, dass die über einen Ring miteinander verbunden sind.
Das heißt, jeder kann von seinem Vorgänger Informationen bekommen über
irgendeine Nachricht.
Und dadurch, dass hier Nachrichten sukzessive rumgeschickt werden,
kann ich also kommunizieren.
Und es gibt schon einen alten Satz, 34 Jahre alt.
In einem Ring identischer Prozessoren kann es keinen
deterministischen, vollständig verteilten und symmetrischen
Algorithmus zur Wahl eines Leiters geben.
Also wenn alle genau die gleichen Entscheidungen treffen, sie dürfen
nicht die Identität verwenden, die die einzelnen Prozessoren haben.
Also die werden ja durchnummeriert sein, vielleicht irgendwie mit
irgendwelchen Zahlen.
Irgendwelche Zahlen können die haben.
Ich kann nicht diese Zahlen verwenden.
Und da kann man zeigen, und das geht ähnlich wie bei den
Philosophenproblemen, wenn sie alle die gleiche Entscheidung treffen.
Beim Philosophenproblem ist es so, nur um Ihnen das nochmal zu zeigen,
wenn alle die gleichen Entscheidungen treffen, würde zum Beispiel ein
Algorithmus, der sagt, ich greife mir zunächst die rechte Gabel, wenn
sie frei ist.
Dann würden alle, wenn die rechte Gabel frei ist, die rechte Gabel
greifen.
Und dann greifen sie als nächste Entscheidung, ich behalte also diese
Gabel in der Hand und wähle die linke Gabel, sobald sie frei ist.
Und das ist ein Deadlock.
Das ist ein typisches Verhalten eines symmetrischen Algorithmus, alle
treffen die gleiche Entscheidung und sie können in dem Fall bei den
Philosophenproblemen nur zu einer Lösung kommen, wenn sie
unterschiedliche Entscheidungen treffen.
Das funktioniert halt nicht unter diesen Annahmen, die ich hier hatte.
Ähnlich kann man das für diesen Ring identischer Prozessoren zeigen,
dass die also nicht in der Lage sind, unter diesen Annahmen mit einem
deterministischen, vollständig verteilten, symmetrischen Algorithmus
einen Leiter zu wählen.
Ich gehe auf den Beweis nicht weiter ein, ich habe viele andere Dinge,
die ich Ihnen auch erzählen möchte.
Und ich möchte Ihnen zeigen, wie man jetzt, wenn man sagt, okay, das
geht so nicht, machen wir das doch anders.
Wir erlauben die Ausnutzung der Identität.
Wir haben unseren Ring von Prozessoren und ich habe also hier einen
Ring von Prozessoren und jetzt wird folgenden Algorithmus ausgeführt.
Ich sende meine Identität, jeder hat also eine Identität, irgendeinen
Namen, eine Zahl.
Der Einfachheit halber nehmen wir an, wir haben N Prozessoren, jeder
Prozessor hat eine Zahl.
Und der sendet also seine Identität, seine Zahl zum Nachbarn, sendet
also die hier rüber zu seinem Nachbarn.
Der Nachbar oder jeder Prozessor wartet darauf, dass er, nachdem er
was rausgeschickt hat, dass er etwas bekommt.
Der möchte also gerne von seinem, also Next ist immer der Nachfolger
diesem Ring, Previous ist der Vorgänger in dem Ring.
Er wartet darauf, bis er etwas bekommt, das ist Receive X, from
Previous.
Und wenn das, was er bekommt, er hat ja seine eigene Identität hier,
wenn das, was er bekommt, kleiner ist als seine eigene Identität, dann
sendet er dieses Paket hier weiter zu seinem Nachbarn.
Wenn er als Nachricht von seinem Nachbarn eine Nachricht bekommt, die
genau seine eigene Identität ist, heißt das unter der Annahme, alle
Prozessoren haben unterschiedliche Identitäten, dass die Nachricht
einmal rumgelaufen ist und wieder zurückkommt.
Es kann aber eine Nachricht nur dann rumlaufen und wieder zu ihm
zurückkommen, wenn es immer eine Nachricht war, die kleiner war als
die Identität der Prozessoren, wo sie durchgelaufen ist.
Denn wenn sie größer wäre, dann würde man ja gar nichts machen.
Dann würde man die Nachricht ja nicht weiterschicken.
Derjenige, der jetzt die Nachricht wiederbekommen hat, der schickt
jetzt den negativen Wert seiner Identität weiter an den Nachbarn.
Wir gehen davon aus, alle Identitäten sind positiv, jetzt schicke ich
einen negativen Wert rum.
Dadurch, dass ich das Minus-X rumschicke, also danach ist er übrigens
fertig, until x gleich id, also dieser, der das gemacht hat, hört
anschließend hier mit dieser Repeat-Schleife auf.
Kann man auch als while formulieren, ich habe es hier als repeat
formuliert.
Oder wenn das x kleiner als 0 ist, dann hört er auch auf.
Dann hat er also hier vom Nachbarn einen negativen Wert erhalten.
Wenn er einen negativen Wert erhält vom Nachbarn, heißt das, dieses
Minus -X ist ja nur verschickt worden, weil eine Nachricht ganz
rumgelaufen ist.
Dieser Prozessor hat festgestellt, die Nachricht kam hier auch an und
das war genau diese Identität.
Das heißt, das muss die kleinste Identität sein in diesem Ring.
Wenn das aber die kleinste ist, dann ist das, was ich gerade unter
Ausnutzung der Identität feststellen wollte, ich wähle denjenigen, der
die kleinste Identität hat.
Und dadurch, dass ich diesen Wert x bekommen habe, oder Minus-X
bekommen habe, weiß ich auch, wie der heißt, nämlich x.
Also hier steht x kleiner 0, also jetzt natürlich x Absolutwert, davon
ist jetzt der Name meines...
dadurch, dass ich das Minus-X rumschicke, habe ich gleichzeitig den
Namen des Leiters mit rumgeschickt.
Das heißt, alle wissen, wenn sie hier rausgelaufen sind, wer der
Anführer ist.
Es weiß derjenige, der gewählt wurde, weil das genau die Nachricht,
die er bekommen hatte, seine eigene Identität war.
Und alle anderen wissen, wer gewählt wurde.
Und sie wissen auch, dass man fertig ist.
Weil das Erhalten einer negativen Nachricht heißt, es hat jemand
festgestellt, dass er gewählt worden ist.
Und wenn ich das jetzt bekommen habe, diese Nachricht, dann weiß ich,
ich kann jetzt auch praktisch wieder einschlafen, ich weiß, oder was
anderes tun, ich weiß, wer der Anführer ist.
Und derjenige, der jetzt das Minus-X rausgeschickt hatte, der wartet
noch darauf, dass er von seinem Vorgänger diese Nachricht noch einmal
bekommt.
Oder eine Nachricht bekommt.
Da muss ja eine Nachricht, die rausgeschickt wurde, muss auch
empfangen werden.
Und der direkte Vorgänger muss ja dieses Minus-X, was der hier
rausgeschickt hat, dann auch nochmal wieder weiterschicken.
Das muss also noch einmal akzeptiert werden.
Und dann ist man fertig.
Also über diese Bedingung x kleiner id, das gilt ja auch, wenn das x
kleiner als 0 ist.
Deswegen wird das Minus-X, also dieser negative Wert, auch ganz
rumgeschickt.
Und das heißt, dieses Verfahren ist eindeutig dafür geeignet, um
festzustellen, welches ist der kleinste Wert der Identitäten in diesem
Ring.
Sehr einfaches Verfahren.
Oh, Sie sehen, ich habe das hier sogar aufgemalt.
Da ist also jetzt das angedeutet.
Und wenn die jetzt alle ihre Nachrichten verschicken, das ist die
Anfangssituation.
Ich habe hier einen solchen Ring.
Alle schicken ihre Identitäten nach rechts.
An welchen Stellen haben wir jetzt diese Situation?
Eins wird weitergeschickt.
Hier müsste weitergeschickt werden, weil 1 kleiner als 6 ist.
6 ist größer als 5.
Der wird die 6 nicht weiterschicken.
5 ist kleiner als 9.
Das hier wird weitergeschickt an der Stelle.
9 ist größer als 2.
Da wird nichts weitergeschickt.
2 ist kleiner als 8.
An dieser Stelle wird etwas weitergeschickt werden.
8 ist größer als 4.
Da passiert nichts.
4 ist größer als 3.
Passiert auch nichts.
3 ist größer als 1.
Passiert auch nichts.
Und das waren alle, die hier in dem Fall rausgeschickt werden.
Also im nächsten Schritt werden nur noch diese 1, 2, 3 Nachrichten
verschickt.
An diesen drei Stellen.
Wir haben also erstmal alle etwas verschickt.
Da kann man sich fragen, wie erreiche ich denn, dass alle gleichzeitig
ihre Identitäten verschicken.
Dazu müssen sie ja wissen, dass sie das jetzt so machen sollen.
Das muss nicht unbedingt alles gleichzeitig passieren.
Die müssen nur angestoßen werden, dass sie die Nachricht rausschicken.
Sie müssen zunächst einmal ihre eigene Nachricht rausschicken, müssen
dafür angestoßen werden.
Das kann irgendeine Anstoßnachricht sein, die herumläuft.
Und dann geht es darum, was wird in der nächsten Runde jetzt
verschickt.
Und Sie sehen, hier werden nur noch drei Nachrichten verschickt.
Und jetzt trifft also hier die 1 auf die 5.
Dann wird jetzt an dieser Stelle was rausgeschickt.
Und ansonsten, die 5 trifft auf eine 2.
Da passiert nichts.
Die 2 trifft auf eine 4.
Dann wird hier noch was rausgeschickt.
Und das ist es.
An diesen beiden Stellen, die 1 und die 2 wandern weiter.
Die 2 ist kleiner als 3.
Auch das wird weiterlaufen.
Die 1 läuft natürlich weiter rum.
Die 2 ist größer als die 1 und damit fällt sie weg.
Und jetzt läuft die 1 hier noch weiter an den einzelnen Positionen
vorbei.
Trifft in diesem Fall auf die 1.
Und damit weiß derjenige Prozessor, dass er fertig ist.
Das heißt, es dauert genau, wenn ich n Prozessoren habe, genau n
Takte, bis das einmal rumgelaufen ist.
Die 1 läuft ja von vorne, also von dem Kleinsten läuft das Ding
natürlich in jeder Runde einmal 1 weiter.
Und dann geht anschließend der negative Wert rum.
Der weiß, dass er gewählt wurde.
Hat seine Farbe verändert.
Und er schickt die minus 1 an den Nachbarn.
Der weiß dadurch, dass die 1 gewählt wurde und ist fertig.
Jetzt läuft das entsprechend rum.
Und sukzessive wissen Sie alle, dass also die 1 gewählt wurde, weil
die minus 1 hier rumläuft.
Und anschließend müsste ich eigentlich sogar den nochmal anders
markieren.
Er weiß, dass er gewählt wurde.
Und er weiß jetzt auch, dass alle anderen wissen, dass er gewählt
wurde.
Weil er diese Nachricht wiederbekommen hat.
Das sind so die Probleme, die man alle dabei beachten muss.
Wie ist der Aufwand?
Wenn wir nur die Nachrichten zählen, also innen drin mussten sie ja
nicht viel tun, das ist ja trivial, was sie da machen mussten.
Wie viele Nachrichten habe ich?
Ich habe zunächst mal N Nachrichten, weil jeder seine Nachricht
verschickt.
Das ist die Frage, wie viele Nachrichten werden danach noch
weitergeschickt.
Also wir hatten gesehen, da wurden nur 3 Nachrichten weitergeschickt.
Danach noch weniger.
Wenn ich Pech habe, Sie haben eine Frage?
Genau, es kann immer 1 weniger werden.
Aber ich bekomme auf die Art und Weise quadratische Anzahl von
Nachrichten, im schlechtesten Fall.
Kann ich nicht vermeiden.
Wenn die ungünstig verteilt sind, die Identitäten, habe ich halt
quadratische Anzahl.
Das kann ich verbessern.
Ich kann die Anzahl der Nachrichten auf N log N reduzieren.
Das werden wir später sehen, wie das geht.
Das ist ganz interessant, wie man sich überlegen kann, wie man
Kommunikationsaufwand reduzieren kann.
Was muss ich eigentlich kommunizieren, um eine Information
weiterzugeben?
Ich muss ja nur eine Information weitergeben.
Wie kodiere ich meine Information?
Das ist die Frage dabei.
Muss ich da wirklich die Zahl, die Identitäten weiterschicken?
Oder kann ich irgendwas anderes weiterschicken?
Und das werden wir gleich noch sehen, wie man das macht.
Im besten Fall habe ich 3 N-1 Nachrichten.
Im besten Fall läuft nur die kleinste Nachricht ganz rum.
Die negative Nachricht läuft nochmal ganz rum.
Und jeder, das sind 2 N-1 Nachrichten.
Und jeder hat zu Anfang einmal eine Nachricht verschickt.
Das sind 3 N-1 Nachrichten.
Das wäre also der beste Fall.
Nur 3 N-1 Nachrichten.
Gut.
Das war der eine Ausweg.
Wir gehen später noch daran, das zu reduzieren auf N log N.
Anderer Ausweg ist, ich kann das ja auch probabilistisch machen.
Warum muss ich das deterministisch machen?
Ich kann es ja probabilistisch machen.
Dann machen die nicht unbedingt alle das Gleiche.
Und hier ist die Idee, alle Prozessoren sind nach wie vor identisch.
Jeder Prozess, ist jetzt erstmal eine Annahme, kennt die Gesamtzahl
aller beteiligten Prozesse.
Das war bei dem anderen Verfahren nicht notwendig.
Bei dem ersten Ausweg brauchten wir nicht zu wissen, wie viele da
sind.
Wir mussten nur wissen, die sind über einen Ring verbunden.
Jeder kennt seinen Vorgänger und Nachfolger.
Und mehr müssen die nicht wissen.
Die müssen nur darauf warten, dass eine Nachricht, die sie
rausgeschickt haben, irgendwann dazu führt, dass eine Nachricht wieder
reinkommt.
Also wenn ich jetzt aber sage, ich kenne die Anzahl der Prozesse, kann
ich ein bisschen mehr machen, ich habe mehr Informationen.
Und jeder Prozess besitzt einen unabhängigen Zufallszahlengenerator.
Damit habe ich natürlich nicht ein symmetrisches Verfahren.
Sie arbeiten nicht alle gleich, sondern sie haben unabhängige
Zufallszahlengeneratoren.
Das ist eine kleine Abweichung, dass sie eventuell in der Lage sind,
unterschiedliche Zufallszahlen zu erzeugen.
Das nutze ich jetzt aus.
Unterschiedliche Seeds für Pseudo-Zufallszahlengeneratoren, die
brauchen irgendeinen Startwert.
Und die kann sein, dass ich da unterschiedliche Startwerte habe.
Die Reihenfolge der Nachrichten bleibt im Ring erhalten.
Auch das nehme ich an, dass man die erhält in der gleichen
Reihenfolge, wie sie verschickt wurden.
Wenn ich einen Ring habe, sollte das aber eigentlich kein Problem
sein.
Der Algorithmus sieht jetzt so aus, ganz ähnlich wie vorher.
Das stimmt nicht ganz, nein, Entschuldigung, anders.
Hier habe ich jetzt folgendes Verfahren.
Ich nehme an, dass meine Prozesse irgendwie Werte von 1 bis K haben
und ich habe eine Liste von irgendwelchen Zahlen aus dem Bereich 1 bis
K, wobei K irgendeine große Zahl ist.
Und diese Liste ist zu Anfang leer.
In der Liste will ich jetzt Folgendes aufsammeln.
Jeder Prozess wählt zufällig eine Zahl zwischen 1 und K.
Da nutze ich meinen Zufallszahlengenerator aus.
Es macht jeder die gleiche Operation, aber das Ergebnis wird
unterschiedlich sein, weil ich davon ausgehe, dass die unabhängig sind
voneinander und dass sie unterschiedliche Zahlen wählen können, dass
sie unterschiedliche Seeds haben.
Wenn die natürlich alle genau identisch sind, würde es nicht
funktionieren.
Also hier nehme ich an, dass sie nicht ganz gleich sind, sondern dass
die gewisse Informationen haben können, die unterschiedlich sind.
Und dann mache ich Folgendes.
Ich füge den Namen, den ich lokal erzeugt habe, in meine Liste ein.
Dann sende ich den Namen, also ich habe hier den Namen lokal erzeugt,
ich sende den Namen zu meinem Nachfolger, das macht jeder, und
empfange von meinem Nachbarn, also ich schicke erst etwas rüber, der
hier empfängt natürlich dann eine Nachricht.
Und jetzt habe ich also diese variablen Namen überschrieben mit dem
Namen, den mein Vorgänger erzeugt hatte.
Und diesen Namen, das geht jetzt hier wieder rein, trage ich in die
Liste ein und so habe ich dann eine Liste von Namen, das sind jetzt
irgendwelche Zahlen N1, N2, N3 usw.
An dem Fall muss ich NN sagen, weil ich annahme, ich habe N
Prozessoren.
Eine Liste der Länge N und das wird N-mal gemacht.
Wenn ich es N-mal mache, ich weiß, ich habe N Prozessoren, hat jeder
einen Namen eingetragen und dann schaue ich nach, ob es einen Namen
gibt dabei, der nur einmal auftaucht.
Es kann ja sein, dass mehrere den gleichen zufälligen Namen gefunden
haben oder erzeugt haben.
Ich suche nur einen Namen, der nur einmal auftaucht.
Und dann nehme ich den, hier ist jetzt gesagt worden, der maximale
eindeutige Name in S.
Jeder Prozess hat lokal in seiner Liste, die er hier führt, jeweils
die ganzen Namen, die an ihm vorbeigelaufen sind, die Liste
eingetragen.
Das heißt, jeder Prozessor hat diese Liste S mit den Namen N1 bis NN
in unterschiedlichen Reihenfolgen, aber darauf kommt es gar nicht an,
muss nur feststellen, gibt es einen Namen, der nur einmal auftaucht.
Wenn es mehrere Namen gibt, die eindeutig sind, die nur einmal
auftauchen, nehme ich davon das Maximum, könnte auch sein das Minimum,
ist also völlig egal.
Und jeder kann diese Operation durchführen.
Anschließend weiß jeder, welcher Name gewählt wurde.
Wieso weiß jetzt der Prozessor oder ein Prozessor, dass er gewählt
wurde?
Naja, jeder hat einen Namen ausgewählt.
So, jetzt wird der Name rumgeschickt und er überschreibt den durch den
Namen, den er bekommen hat vom Nachbarn.
Und das Ganze wird N-mal gemacht.
Das heißt, als letztes empfängt er den Namen, den er selber verschickt
hat.
Das heißt, der Name, den er als letztes bekommen hat, ist der Name,
den er selbst gewählt hat.
Und wenn er jetzt feststellt, der Name, also die variablen Name oder
Name, hat am Ende genau den Wert wie der maximale eindeutige Name in
S, dann ist er selbst gewählt.
Alle anderen wissen, wen sie jetzt anschreiben müssen, wer also
gewählt wurde zum Anführer.
Der hat dann diesen Namen, der der maximale eindeutige Name in dieser
Liste ist.
Und damit, jeder weiß also, welchen Namen er hier zufällig für sich
gewählt hat.
Das ist nach diesem Durchlauf, nach Ausführung dieser Schleife
erledigt.
Da werden natürlich viele Nachrichten verschickt, quadratischer
Aufwand in der Anzahl der Nachrichten.
Aber ich habe jetzt nicht die Namen verwendet, die ursprünglich die
einzelnen Prozessoren als Identitäten haben, sondern ich nehme solche
zufällig erzeugten Namen.
Das heißt, jeder hatte die gleiche Chance, gewählt zu werden, abhängig
davon, welche zufälligen Namen er im Prinzip gewählt hat.
Das heißt, hier entscheidet im Prinzip der Zufallszahlengenerator
darüber, wer am Ende dann ausgewählt wird.
Das ist ein populistischer Algorithmus, um dieses Problem zu lösen.
Ein verteilter Algorithmus, der einen Anführer wählt, also im Ring,
ohne dass man Identitäten tatsächlich ausnutzt.
Aber es ist eben nicht ganz symmetrisch, weil ich annehmen muss, dass
die Zufallszahlengeneratoren tatsächlich unabhängig voneinander
arbeiten und unterschiedliche Werte erzeugen können.
Analyse ist hier nochmal angegeben.
Das Ding ist natürlich vollständig verteilt und symmetrisch, bis eben
auf diesen Zufallszahlengenerator.
Alle Prozesse sind in gleicher Weise beteiligt, haben die gleiche
Chance, gewählt zu werden.
Und sie wissen am Ende, wer der Anführer ist, weil sie alle die
gleiche lokale Liste haben, in unterschiedlichen Reihen folgen, alle
um eins zügig verschoben.
Aber sie haben also im Prinzip die gleiche Liste.
Und da sie selber am Ende wieder den Namen bekommen, den sie selbst
verschickt haben, wissen sie sofort, ob sie selbst ausgewählt wurden
oder nicht.
Damit ist das also auch einfach festzustellen.
Und die Frage ist, wann terminiert das Ganze?
Es war ja eine Bedingung drin.
Hier steht, until Mindesteseinnahme nur einmal vorhanden.
Jetzt ist die Frage, wie sieht das damit aus?
Also wir müssen einfach die Wahrscheinlichkeit annehmen, dass
Mindesteseinnahme oder ein Prozess einen eindeutigen Namen wählt.
Das hängt natürlich davon ab, wie groß unser K ist, wie viele Namen
habe ich zur Verfügung, wie groß ist die Anzahl der Prozesse, die
jetzt Namen auswählen, was für die Zufallszahlengeneratoren habe ich
hier drin.
Und das bestimmt die Wahrscheinlichkeit, mit der ich jetzt tatsächlich
einen eindeutigen Namen dabei finden kann.
Dann ist die Wahrscheinlichkeit, dass ich nach i Runden nicht fertig
bin, 1 minus p hoch i.
Die Wahrscheinlichkeit dafür, dass ich nach genau i Runden fertig bin,
ist 1 minus 1 minus p hoch i.
Und die Wahrscheinlichkeit, wenn ich das jetzt lang genug mache, ist
also die Wahrscheinlichkeit, dass das nicht terminiert, gleich 0.
Weil ich das eben hier durch Anzahl der Runden beliebig klein kriegen
kann, solange die Wahrscheinlichkeit dafür, dass mindestens ein
Prozess einen eindeutigen Namen wählt, größer als 0 ist.
Also damit wird dieser Algorithmus garantiert irgendwann terminieren.
Ich kann nicht genau sagen, wann er terminiert, aber er wird
terminieren.
Also das ist eine Alternative zu dem deterministischen Verfahren.
Typischer Ausweg aus solchen Unmöglichkeitsbeweisen, dass ein
deterministischer Algorithmus nicht die Aufgabe erfüllen kann, wie bei
den Philosophenproblemen oder was wir gerade gesehen haben, bei dem
Satz von Engluin.
Typischer Ausweg ist, das randomisiert zu machen.
Insgesamt N-Quadrat-Nachrichten-Proval-Vorgang, das ist auch klar,
weil ja jeder in jedem Schritt dort Nachrichten verschickt, N mal N
Nachrichten und dann bin ich fertig.
Da habe ich keine Möglichkeit, das zu reduzieren.
Ohne Kenntnis der Zahl der beteiligten Prozessoren habe ich natürlich
keine Möglichkeit zu wissen, wann ich alle zufällig gewählten Namen
erhalten habe.
Also ich kann nicht dadurch, dass ein Name nochmal geschickt wird,
annehmen, jetzt sind alle Nachrichten verschickt worden.
Es könnten ja die gleichen Namen oder Prozessoren die gleichen Namen
haben.
Also ich muss irgendwas wissen, wie viele Prozesse sind eigentlich
beteiligt.
Ich muss eine Information haben, um festzustellen, ich habe jetzt alle
Namen von allen Prozessen tatsächlich bekommen, alle diese zufällig
gewählten Namen und ich könnte aber, also das ist, ich brauche
irgendeine Information.
Jetzt kann ich aber auch ein bisschen anders vorgehen, das habe ich
hier nochmal angedeutet.
Ich könnte sagen, wenn die Prozesse oder Prozessoren eindeutige Namen
haben, ich nehme mal an, die sind durchnummeriert irgendwie, ich darf
nur die Identität verwenden für die Auswahl des Leiters.
Aber ich könnte ja die Information verwenden, um festzustellen, ob ich
bereits einmal rumgelaufen bin.
Das heißt, man kann dann einen modifizierten Algorithmus angeben, der
nach dem Prinzip vorgeht, wie hier in dem populistischen Algorithmus
angegeben, aber dann brauche ich die Anzahl der Prozesse nicht zu
kennen und ich werde dabei diese Namen oder die Identitäten der
Prozessoren nicht bei der Wahl des Anführers verwenden.
Die beeinflussen nicht, wer ausgewählt wird, die beeinflussen nur,
dass ich weiß, jetzt bin ich einmal rum und kann weitermachen.
Können Sie sich leicht überlegen, wie man das macht?
Hat einer eine Idee, wie man das machen könnte?
Ja?
Bitte?
Genau, ganz einfache Idee.
Ich schicke praktisch zwei Informationen rum, nicht eine Information,
habe dann immer Paare von It und Name und damit habe ich es schon.
Ganz einfach zu machen, also diese Annahme mit der Kenntnis der Zahl,
das kann man auch weglassen.
Dann muss ich allerdings etwas mehr Informationen verschicken.
Okay, das dazu.
Und jetzt kommen wir in den letzten Minuten von heute noch dazu, wie
man die Zahl der auszutauschenden Nachrichten reduzieren kann oder den
Kommunikationsaufwand.
Ich hätte gesagt, wir wollen von n² irgendwie runter auf n log n.
Und wir nehmen jetzt nochmal an, dass jeder eine eindeutige Identität
hat, wie bei dem Verfahren, das ich als ersten Ausdruck dargestellt
habe.
Ich möchte einen beliebigen... Quatsch, ich möchte einen Prozess
kleinster Identität auswählen und irgendeiner stößt den Prozess an,
könnte auch von Beliebigen, von allen angestoßen werden, das ist
ziemlich egal.
Die müssen nur irgendwann dazu aufgefordert werden, dass sie ihre
Nachricht rausschicken, sie aufgeweckt werden können.
Und ich nehme an, dass die als Ring verbunden sind.
Ganz einfache Topologie, man kann das alles auch betrachten für andere
Strukturen, beliebige Verbindungsstrukturen, für Bäume, für Gitter,
für was immer Sie haben wollen.
Ringe sind eine sehr einfache Struktur und nur für die will ich es
hier betrachten.
Aber wie gesagt, man kann das auch übertragen auf andere Situationen,
da muss man nur ein bisschen andere Algorithmen erzeugen, die leichte
Modifikationen sind von dem, was ich hier mache.
Und jetzt habe ich also hier meinen Algorithmus, den ich Ihnen vorher
schon gezeigt habe.
Ich schicke einfach meine Identität rum und wann immer ich einen
kleineren Namen bekomme oder es geschickt bekomme, als meine eigene
Identität ist, schicke ich die weiter, ansonsten vergesse ich die
Nachricht.
Und man kann sofort sich ein paar Dinge überlegen, wie man das
verbessern kann.
Also die erste Verbesserung wäre, dass ich folgendes mache, ich
vergleiche nicht nur mit der eigenen Identität, sondern mit der
kleinsten bisher erhaltenen Nachricht.
Ja, also, wo taucht das hier auf?
Das müsste eigentlich hier irgendwo...
Genau, das habe ich hier gar nicht reingeschrieben.
Das ist aber einfach zu machen.
Hier würde ich eben nicht vergleichen mit der eigenen Identität,
sondern ich würde vergleichen mit der letzten Nachricht, die ich habe,
immer wieder mir merken, das aktuelle Minimum, das ich lokal gesehen
habe, mit dem vergleiche ich.
Dadurch könnte ich schon die Anzahl der Nachrichten reduzieren, weil
ich dann mit einem kleineren Wert vergleiche.
Das würde die mittlere Zahl ein bisschen verbessern, aber kaum den
schlechtesten Fall.
Die Frage ist, kann man sich auf einen einzigen Initiator beschränken?
Das wäre ein bisschen schwierig, denn dann hätte man keinen
symmetrischen Algorithmus.
Also müssen im Prinzip alle gleichmäßig anfangen können.
Wenn man sich beschränken könnte auf einen Initiator in einem solchen
verteilten Algorithmus, auf einem Ring, dann hätte man ja schon einen
Anführer.
Derjenige, der beginnt, der wird einfach der Anführer.
Und dann wäre man schon fertig.
Also wir müssen davon ausgehen, das sind alles beliebige Prozessoren.
Also wenn ich nur einen hätte, der das anstößt, dann würde ja nur eine
Nachricht praktisch da einmal rumlaufen.
Alle könnten sofort kontrollieren, ist das eine kleinere als die
eigene und würden ihre eigene Nachricht nur dann weiterschicken, wenn
das, was kommt, größer ist als die eigene Nachricht.
Insofern könnte man das deutlich reduzieren.
Aber wir können das so nicht annehmen.
Das wäre aber durchaus eine Verbesserung oder eine Möglichkeit, wenn
die eben nicht alle gleichzeitig anfangen, sondern wenn es wenige
gibt, die jetzt das anstoßen, dann werden die durch die
Anstoßnachricht, bekommen sie schon die Identität desjenigen, die es
angestoßen hat und sie geben dann nur die Nachricht weiter, die
Identität weiter, wenn sie kleiner ist.
Ansonsten geben sie die eigene Identität weiter.
So, weitere Annahme.
Was nehmen wir noch an?
Das verteilte System arbeitet synchron.
Das heißt, die Prozesse arbeiten in Kommunikationsrunden.
Das ist eine starke Annahme.
Bisher haben wir nämlich nicht angenommen, dass die tatsächlich alle
gleichzeitig arbeiten.
Ich habe das so dargestellt in der Animation, als wenn das alles
gleichzeitig passiert.
Aber jetzt muss das nicht mehr so sein.
Wenn die nicht gleichzeitig arbeiten würden, wäre das ein anderer
Fall.
Wir nehmen an, die arbeiten in Kommunikationsrunden.
Sie wissen alle, Sie haben eine globale Zeit.
Und dadurch kann ich jetzt Folgendes machen.
Ich verzögere den Versand einer Nachricht X um F von X Runden.
Jetzt muss ich mir überlegen, was für eine Funktion F wähle ich denn
dafür.
Das schauen wir uns gleich an.
Voraussetzung ist, dass jeder Prozess eine Nachricht verschicken kann.
Er muss aber nicht.
Er kann auch warten damit.
Er muss nicht in jeder Runde eine Nachricht rausschicken.
Wenn ich also keine Nachricht bekomme innerhalb der Zeit für eine
Runde, weiß ich, der hat mir keine Nachricht geschickt.
Wenn also eine Nachricht nicht kommt, gehe ich davon aus, die ist
nicht verschickt worden.
Das ist kein Fehlerfall.
In jeder Runde prüft der Prozess, ob Nachrichten angekommen sind.
Ich muss also nicht in jeder Runde von allen Nachbarn, also von diesem
einen Nachbarn, man kann das auch auf eine allgemeinere Struktur
übertragen, Nachrichten bekommen haben.
Was heißt das für den Algorithmus?
Die Anzahl der Runden ist die, sagen wir mal T.
M ist die minimale Identität unter allen Identitäten, die da sind.
Ich habe maximal N Runden, ich habe ja N Prozessoren, bis der Prozess
M angestoßen wird.
Also wenn der, ich habe hier meinen Ring, wenn der hier anfängt und
nach rechts rüberschickt, das dauert ja eine Weile, bis der angestoßen
wird, dass er was tun soll.
Also diese Anstoßnachricht, die läuft da einmal rum, das sind N
Runden, bis der Prozess angestoßen wird.
Dass er seine Nachricht verschickt.
Dann muss die Nachricht einmal rumlaufen.
Einmal rumlaufen heißt, ich muss N mal F von M Runden abwarten.
F von M war die Anzahl der Runden, die ich warte, bis ich eine
Nachricht verschicke.
Bis die Nachricht M wieder von Prozess M empfangen wird.
Muss einmal rumgelaufen sein.
Und dann brauche ich noch N Runden für die Abschlussnachricht.
Das Minus X, das einmal rumläuft und allen mitteilt, oder das Minus M
in dem Fall, dass der Prozess M gewählt wurde.
Das heißt, meine Zeit insgesamt ist N mal F von M plus 2.
Diese N Runden für das Anstoßen, N Runden für die Abschlussnachricht,
N mal F von M Runden hier für das Durchlaufen der minimalen Nachricht.
Und dann gibt es noch Anzahl Verlierer Nachrichten.
Das sind gerade alle anderen Nachrichten.
Also für alle größeren Nachrichten sind so zu viele Nachrichten, die
verschickt wurden, T durch F von I, das sind die Nachrichten, die in
der Zeit T verschickt worden sein können, für diese größeren Werte.
Die werden verloren gehen.
Und das T ist N mal F von M plus 2, das durch F von I.
Und ich stelle fest, wenn ich jetzt das F von X als 2 hoch X wähle,
dann ist die Anzahl aller Nachrichten, das ist nach wie vor O von N,
und die Anzahl aller Nachrichten-Bits, die ich schicke, die ist dann
in O von N mal Log N.
Ich schicke ja, also die Anzahl der Nachrichten-Bits ist klar, die
Nachrichtendänge ist gerade Log N, weil ich gerade nur diese N
verschiedenen Identitäten habe.
Und ich habe insgesamt dann nur noch O von N Nachrichten übrig.
Dadurch, dass ich hier das F von M geeignet gewählt habe, so viele
Nachrichten gehen verloren.
Die eine Nachricht muss einmal rumlaufen und ich habe dann insgesamt
eine lineare Anzahl von Nachrichten hiermit erreicht.
Wir sind damit durch.
Ich werde an der Stelle wieder einsetzen beim nächsten Mal, das
nochmal wieder aufgreifen und dann machen wir noch die restlichen
Folien fertig.
Und es sind noch ein paar Sachen, die ich erzählen möchte,
insbesondere über eine untere Schranke, die wir brauchen, um
tatsächlich in so einem Ring den Anführer zu wählen.
Vielen Dank, das war es für heute.
Wir sehen uns nächste Woche noch einmal und dann haben wir eine
Klausur.
Vielen Dank.