So, schönen Morgen.
Ich begrüße Sie zur vorletzten Ausgabe von Effiziente Algorithmen
dieses Semester.
Nächste Woche sind wir nochmal heute zu einer etwas ungewöhnlichen
Zeit.
Bisschen früh, aber bei den Temperaturen gar nicht so unangenehm.
Mal sehen, dass wir heute hier noch ein Stück weiter kommen.
Die letzten beiden Male hat mich Herr Schukla vertreten und hat
insbesondere das Kapitel Algorithmische Geometrie behandelt.
Da sind einige interessante Themen gemacht worden.
Insbesondere ging es also um prinzipielle Dinge.
Was sind überhaupt geometrische Objekte, mit denen man es zu tun haben
kann.
Dann wurden einige Standardprobleme angeguckt, wie zum Beispiel Punkt-
oder Flächenabsuchungsprobleme.
Das heißt, ich frage, wie viele Punkte sind innerhalb eines Rechtecks
auf einer beliebigen Fläche.
Da gab es eben dann den Effekt, der hier wichtig ist, dass man bei
einem Verfahren, bei dem man eine Vorbereitung trifft, also erstmal
sich Gedanken macht drüber, was ist das für eine Punktmenge, in der
man dann viele solche Suchanfragen macht.
Da konnte man den Aufwand für die tatsächliche Beantwortung dieser
Frage, wie viele Punkte sind innerhalb eines Rechtecks, mit Log-N
-Aufwand beantworten.
Man musste allerdings einen Vorbereitungsaufwand von N² in Kauf
nehmen.
Das ist eben hier ein wichtiger Punkt, dass man vorher Informationen
ausnutzt.
Und dann natürlich lohnt sich das nur, wenn man mehrfach solche
Punktanfragen macht.
Danach ging es darum, inwieweit man feststellen kann, ob ein Punkt
innerhalb oder außerhalb eines konvexen oder eines einfachen Polygons
zunächst mal liegt.
Da gab es diese Strahlmethode, wo man also einfach die Anzahl der
Überschneidungen von Kanten zählt und dadurch weiß, ob man innen oder
außen ist.
Eine Methode mit praktischen Anwendungen in verschiedensten
Situationen.
Dann die gleiche Frage für ein konvexes Polygon, bei dem das viel
einfacher ist, weil ich eben weiß, dass ich jede Linie, den Rand nur
einmal schneide.
Dadurch konnte man eine einfache Suche auf der Menge der Punkte machen
und hatte dann so relativ schnell festgestellt, ob ein Punkt innen
oder außen ist.
Und die wesentliche Frage, die man beantworten musste, war dabei
natürlich, inwieweit ein Punkt links oder rechts von einer Kante
liegt.
Da ist eben wichtig, sich zu überlegen, dass es einfach nur die
Berechnung einer Determinanten ist und eigentlich nur die Überprüfung,
ob der Wert größer oder kleiner 0 ist.
Also man braucht gar nicht vollständig auszurechnen, sondern kann das
relativ einfach abschätzen.
Aber man muss immer aufpassen, wenn die Punkte sehr nah beieinander
liegen und das dann auch noch realwertige Koordinaten sein könnten,
dann wird es schwierig, das wirklich genau zu machen.
Das war also hier diese Berechnung, liegt ein Punkt links oder rechts
von einer Geraden.
Dann wurde das Problem der Überschneidungen von Kanten angeguckt, also
eine Menge von Geraden oder von Linien.
Man will alle Überschneidungspunkte suchen.
Dabei gab es dieses Planesweep-Verfahren, ein klassisches Verfahren,
um solche geometrischen Probleme zu lösen.
Das Wesentliche hierbei ist eben, dass man ein Problem, ein n
-Dimensionales Problem, reduziert auf ein n-1-Dimensionales und dann
eben eine Reihe von solchen n-1-Dimensionalen Problemen löst.
Bei diesen 2-Dimensionalen Problemen, also ein 1-Dimensionales
Problem, und das musste man nur an den Endpunkten der Kanten
bearbeiten, an jedem Punkt nur logarithmischen Aufwand, sodass man mit
n log n damit hinkam.
Ein klassisches Verfahren, Standardmethode mittlerweile.
Also ein weiterer, so ein klassischer Ansatz für den Entwurf von
Algorithmen.
Dann wurde das Ganze weiter...
Ja, das nächste Problem angeguckt, das nächste Problem war die konvexe
Hülle, Bestimmung eines Randes einer Menge von Punkten.
Und die Bestimmung der Extrempunkte, ein Problem, das man von
Optimierungsverfahren kennt, oder auch aus anderen Bereichen, dass man
die Extrempunkte einer solchen Punktmenge finden muss.
Das ist eben ein Standardproblem logarithmisch in Geometrie, oder
behaupte Geometrie und Orgeln.
Und jetzt haben wir dafür unterschiedlichste Verfahren.
Und das erste Verfahren war ein vielleicht zunächst mal ungewöhnlicher
Ansatz, wo man einfach eine Eigenschaft ausgenutzt hat, dass ein Punkt
oder dass ein Extrempunkt außen liegen muss.
Das heißt, der kann nicht im Inneren eines Dreiecks liegen.
Also ich muss nur feststellen, welche Punkte im Inneren von Dreiecken
liegen.
Die, die übrig bleiben, sind Extrempunkte.
Das Interessante ist, dass man das in unabhängigen...
Ja, dass man das in unabhängigen Fragestellungen machen kann.
Also ich habe viele Instanzen solcher Dreiecke und kann die alle
parallel untersuchen.
Allerdings mit einem sehr hohen Aufwand.
Der war eigentlich viel zu hoch, NO4.
Wenn man das ein bisschen verbessert oder einen anderen Ansatz nimmt,
dann hat man diesen Graham-Scan, bei dem man tatsächlich in Zeit nLog
n hinkommt, wo man die Menge der Randpunkte sukzessive abläuft.
Man sortiert alle Punkte und hat also so eine Art kreisförmige
Sortierung aller Punkte.
Ausgehend von einem Punkt im Inneren dieser Punktmenge.
Man kann einfach irgendeinen Punkt nehmen, kann den untersten sicheren
Endpunkt nehmen oder Extrempunkt nehmen oder irgendeinen Punkt.
Innerhalb der Punktmenge hat man die alle radial sortiert und kann
dann sukzessive gucken, inwieweit man bei den Winkeln, die man auch
bei aufeinanderfolgenden Punkten hat, einen konvexen oder konkarven
Winkel hat.
Bei dem, was ein konkarver Winkel ist, muss man den Punkt dann
rauswerfen.
Ansonsten ist es halt ein konvexer Winkel und dann habe ich einen
potenziellen Extrempunkt.
Und das Ganze lief also dann, wenn man alle Punkte durchlaufen muss,
weil man die erstmal sortieren muss in Zeit nLog n, die nächsten
Aufgaben sind eigentlich nur, dass man dann jeden Punkt einmal
anguckt, eventuell einmal rauswirft und das geht dann nachher in
Aufwand n.
Also nur das Sortieren zu Anfang hat den Aufwand nLog n.
Und das war also das, was man hier macht.
Dann kam der Jarvis-March.
Und ich weiß nicht, haben Sie letztes Mal die Animationen gezeigt?
Zu denen, denen die Animationen schon gezeigt wurden, war das nicht
normal zu machen.
Dann geht es heute um das nächste Verfahren.
Also Jarvis-March war eben ein interessantes Verfahren, bei dem man
sagt, ich muss ja nicht wirklich jeden Punkt betrachten, sondern nur
die potenziellen Extrempunkte.
Und wenn ich einen Extrempunkt habe, suche ich einfach den nächsten
Extrempunkt, dadurch, dass ich mir anschaue, welcher Punkt ist der,
der am weitesten außen liegt.
Ich gucke also alle anderen Punkte durch und kann dann den nächsten
Extrempunkt finden.
Und von dem aus mache ich das Gleiche.
Wenn ich Pech habe, muss ich halt jedes Mal mit Größenordnung n
anderen Punkten vergleichen.
Und ich habe dann eventuell, wenn ich viele Extrempunkte habe, einen
Aufwand, der bis zu n² sein kann.
Also wenn die Anzahl der Extrempunkte in der Größenordnung n ist, dann
habe ich n² Aufwand.
Wenn die Anzahl der Extrempunkte aber klein ist, und das ist eben
häufig so, dass ich nur relativ wenige Extrempunkte habe, dann ist der
Aufwand gerade Anzahl der Extrempunkte mal n und kann dann also besser
sein als das n-log-n-Verfahren.
Insofern hat es so ein bisschen ähnliche Charakteristik wie Quicksort,
im Extremfall n².
Wenn ich also Glück habe, etwas besser, wobei hier, ich habe hier
keine Aussage über das Verhalten im Mittel gemacht.
Da muss ich erst mal wissen, wie die Punkte im Mittel verteilt sind.
Und da haben wir ja gar nichts mit beschäftigt.
Jetzt kommt die erste neue Folie für heute.
Das ist das nächste Prinzip, um eine konvexe Hülle zu bestimmen.
Wir haben uns ja auch mit Divide & Conquer beschäftigt.
Wir wissen, wie wir bei Divide & Conquer vorgehen.
Wir wollen uns eine Punktmenge angucken, wollen dazu die konvexe Hülle
bestimmen und machen das halt so, dass wir die Punktmenge aufteilen in
zwei Punktmengen etwa gleicher Größe.
Also in zwei Mengen m1 und m2 haben wir hier unsere Punkte irgendwie
aufgeteilt.
Und jetzt machen wir zu diesen halben Punktmengen jeweils die konvexe
Hülle.
Regressiv bestimmen wir die.
Und wenn wir also die konvexe Hülle haben, haben wir also genau diese
Randpunkte unserer beiden Teilmengen.
Und jetzt wollen wir daraus aus den konvexen Hüllen zweier Teilmengen
die konvexe Hülle der Gesamtmenge finden.
Und das ist die Frage, wie kann man das denn machen?
Zwei solcher konvexe Hüllen verschmelzen?
Ich muss die ja irgendwie erstmal systematisch mir vornehmen.
Das Interessante ist, wenn ich die beiden bestimmt habe, dann, wie
gesagt, will ich die beiden verschmelzen.
Der Aufwand ist natürlich, für eine kleine Menge ist er konstant.
Für eine beliebige Menge zweimal der Aufwand, um hier regressiv die
konvexe Hülle zu bestimmen.
Und dann steht hier linearer Aufwand in der Anzahl der Punkte.
Also kann ja sein, dass der Rand auch aus linear vielen Punkten
besteht.
Und dann muss ich sehen, wieso habe ich hier linearen Aufwand, um die
konvexen Hüllen zusammenzubauen.
Die Idee ist eigentlich ganz einfach.
Ich gucke mir einfach erstmal den oberen Teil an, meiner beiden
konvexen Hüllen.
Wenn ich mir die konvexe Hülle hier die erste anschaue, naja, das ist
doch, die liegt da.
Was ich gerade gemacht habe, die drei Punkte angestrichen, das kann
ich natürlich ganz einfach machen.
Meine Polygone oder meine konvexen Hüllen sind ja gegeben als Folge
von Endpunkten.
Das heißt, ich habe eine Reihenfolge dieser Punkte, damit habe ich die
in sortierter Reihenfolge vorliegen.
Und zwar in Bezug auf die x-Achse hier sind das aufsteigende Punkte.
So, jetzt habe ich meine anderen Punkte der anderen konvexen Hülle.
Das ist ebenso eine aufsteigende Menge von x-Werten.
Das heißt, ich habe hier zwei Mengen von Punkten, bei denen die x
-Koordinaten jeweils aufsteigend sind.
Zwei sortierte Listen, die kann ich ganz einfach verschmelzen
bezüglich der x-Koordinaten.
Das Verschmelzen bezüglich der x-Koordinaten ist ja einfach.
Zwei sortierte Mengen, das geht in linearer Zeit.
Und ich muss ja nur, einfach weil ich hier diese x-Werte alle gegeben
habe, die der Reihe nach abarbeiten.
Ich gehe zu dem Punkt, dann zu dem, dann zu dem, dann zu dem, dann zu
dem, dann zu dem.
Die sind schon sortiert.
Und jetzt brauche ich einfach nur, mit dem Gram-Scan zum Beispiel,
diese Punkte der Reihe nach anzugucken.
Ich kann das in dieser Reihenfolge machen, ich kann es in einer
anderen Reihenfolge machen, das ist egal.
Gram-Scan hatten wir von rechts nach links betrachtet.
Das können Sie auch von links nach rechts machen, das ist ja völlig
egal.
Und der Aufwand, um jeweils hier die Winkel anzugucken, also da würde
dann der eine schon mal rausfallen, dann würde der rausfallen und Sie
hätten dann entsprechend die Kante und dann hätten Sie den noch.
Die Frage ist nur, wie weiß ich überhaupt, dass das hier die obere
Linie ist?
Naja, ich gehe durch die konvexe Hülle so lange durch, fange also bei
dem linkesten, bei dem Punkt an mit der linkesten x-Koordinate und
dann gehe ich der Reihe nach die Punkte durch, so lange wie die x
-Koordinaten wachsen.
Wenn die nicht mehr wachsen, dann bin ich an dem unteren Rand.
Und das heißt, ich kann ganz einfach den oberen Rand bestimmen von
beiden konvexen Hüllen.
Wir haben jetzt gesehen, dass man einfach durch Verschmelzen der
beiden Folgen und Verwendung von Gram-Scan in linearer Zeit die beiden
Ränder, die oberen Ränder verschmelzen kann zu dem oberen Rand der
endgültigen konvexen Hülle.
Und das gleiche mache ich dann auch nach unten.
Das ist beide Male lineare Aufwand.
Das heißt, insgesamt habe ich linearen Aufwand und wenn ich eine
solche Rekursionsformel anschaue, weiß ich, der Aufwand ist einfach
weg.
Also das ist das, was man eigentlich erhofft.
Divide and Conquer.
Bei solchen Problemen, das normalerweise N²-Zeit kostet, im
schlechtesten Fall beim naiven Ansatz, komme ich hier runter auf N².
Also ein ganz guter Ansatz.
Ich muss natürlich dafür sorgen, dass ich immer in gleich große Mengen
aufteile.
Das steht ja hier auch zweimal T von N½.
Also das ist Prinzip Divide and Conquer.
Und hier steht es nochmal aufgeschrieben, wie man das macht.
Das ist einfach die verbale Erklärung dessen, was ich Ihnen gerade
gezeigt habe.
Und hier, die haben Sie noch nicht gezeichnet, nehme ich an.
Oder die wurde noch nicht gezeichnet, diese Animation.
Die ist auch ganz nett.
Das ist aber eine ziemlich umfangreiche Animation.
Können Sie sich gerne angucken im Einzelnen.
Ich will die nur kurz mal aufmachen.
Es dauert ein Augenblick, bis die Verbindung da ist.
Achja.
Das Netz ist nicht so schnell heute Morgen.
Das tut irgendwie nicht das, was es soll.
Machen wir mal zwischendurch mal weiter und ich zeige Ihnen...
Doch, da ist das Konvex-Fall-Algorithmus.
Da habe ich also eine ganze Reihe.
Ja, ich akzeptiere das übliche Problem.
Wir sagen einfach, ja, ich nehme auch ein Zertifikat an.
Eine nicht signierte Anwendung.
Ich nehme ja an, dass alles in Ordnung ist.
Kommt ja von der Uni.
Und deswegen nehme ich das an, dass alles in Ordnung ist.
Und da sehen wir hier eine Menge von Punkten.
Und jetzt wird hier einfach schon ein Algorithmus ausgeführt.
Das Schöne ist hier, man kann das beliebig sich so hier angucken in
drei Dimensionen.
Das ist insofern eine sehr nette Darstellung.
Alles, was ich bisher gezeigt habe, war immer nur in zwei Dimensionen.
Hier können Sie sich sowas in drei Dimensionen anschauen.
Und das ist also wirklich eine schöne Sache.
Man kann hier unterschiedliche Verfahren anwenden.
Zum Beispiel Quick-Hall kann ich hier angucken.
Es steht hier InSphere, OnSphere.
Verschiedenste Dinge, die man hier machen kann.
Und man kann die Anzahl der Punkte verändern.
Spielen Sie mit rum.
Einfach eine schöne Animation solcher Verfahren für komplexe Hölle.
Hier haben wir alle auf einem Paraboloid, die Punkte.
Das heißt, da haben wir sehr viele, die außen liegen.
Also, das ist einfach.
Hier haben Sie noch ein anderes Verfahren.
Gift Wrap.
Habe ich Ihnen gar nicht vorgestellt.
Es gibt also viele verschiedene Verfahren für komplexe Hölle.
Und das ist einfach eine nette Animation für solche Verfahren.
So, das ist also nochmal eine nette Animation zu diesem Problem der
komplexen Hölle.
Damit sind wir fast durch, durch diese Verfahren.
Komplexe Hölle ist ein schönes Problem offensichtlich, ähnlich wie
Sortieren.
Man kann viele verschiedene Verfahren darstellen.
Und jetzt kommt noch ein weiteres Verfahren.
Ups, das wollte ich gar nicht.
Noch ein weiteres Verfahren.
Dieses hier.
Bei diesem Verfahren, da geht man noch wieder anders vor.
Und sagt, ich nehme mal an, dass die Punkte gleich verteilt sind.
Einigermaßen gleich verteilt.
In meiner Fläche.
So.
Jetzt nehme ich einfach, bestimme ich einfach einige Extrempunkte.
Ich sage einfach, ich bestimme die Extrempunkte in acht verschiedenen
Richtungen.
Extrempunkt im Norden, Extrempunkt im Osten, im Süden, im Westen.
Und dann noch die, die dazwischen liegen.
Diese Extrempunkte zu bestimmen, geht jeweils in linearer Zeit.
Das kann ich ja jeweils machen, das muss ich nur entsprechen mit das
Überlegen, wie ich da festlege, dass das ein Extrempunkt ist.
Wieder nur Vergleich, nicht einer links oder rechts.
Relativ einfach.
Und dann weiß ich doch, alle Punkte, die Extrempunkte sein können,
liegen nicht im Inneren des Polygons, das aufgespannt wird durch diese
acht Extrempunkte.
Wenn die nicht im Inneren liegen, können sie also virtuell außen
liegen.
Die sind gleich verteilt, meine Punkte.
Das heißt, die, die noch außen liegen können, das sind relativ wenige.
Und das ist sogar eine konstante Anzahl.
Ich habe hier ja keine großen Bereiche, das sind also relativ kleine
Flächen.
Das heißt, wenn ich jetzt alle Punkte im Inneren dieses Konvex- und
Polygons eliminiere, E1 bis E8, dann habe ich den Großteil der Punkte
schon eliminiert und ich muss mich nur um die Restpunkte kümmern, die
hier am Rand liegen.
Einige liegen draußen.
So, das heißt, der Aufwand dafür, jeweils für die Bestimmung der acht
Extrempunkte, ist linear.
Achtmal linearer Aufwand.
Der Aufwand, um die Punkte im Inneren zu eliminieren, ist auch linear.
Wie mache ich das?
Ich bestimme...
Ich erfinde heraus, ob ein Punkt im Inneren liegt, wenn er...
Gucken wir mal in diese Richtung, wenn er rechts von dieser Kante
liegt.
Rechts von der Kante.
Rechts von der Kante und so weiter.
Muss also immer innen liegen.
Und ein Punkt, der in Bezug auf irgendeine Kante nicht innen liegt,
wie zum Beispiel diese Punkte hier draußen, der ist halt nicht im
Inneren.
Ein Punkt im Inneren muss halt rechts von jeder Kante liegen.
Wenn ich hier so in dieser Drehrichtung hier einmal rumlaufe.
Einer, der dabei nicht rechts liegt, der ist halt draußen.
Und für die restlichen Punkte kann ich jetzt irgendein Verfahren
nehmen.
Das ist die Anzahl der restlichen Punkte, R.
Da kann ich also mit R log R das machen.
Wir wissen, Gram-Scan erlaubt das.
Und wenn ich jetzt gleich verteilte Punkte habe, dann habe ich
insgesamt ein lineares Verfahren.
Beweis mache ich nicht, aber kann man sich überlegen, dass das dann
tatsächlich ein lineares Verfahren insgesamt ist, weil die Punkte, die
außen sind, eine nur sehr kleine Teilmenge ausmachen können.
Und damit habe ich ein Verfahren, das im Mittel lineare Zeit braucht.
Also ist das deutlich einfacher als zum Beispiel das Sortieren.
Zunächst sah das so aus, dass es etwas ähnliches ist wie das
Sortierproblem.
Wir hatten im schlechtesten Fall M², bzw.
schlechtestes Verfahren kamen wir sogar bei NO4, bei diesem
Dreiecksverfahren.
Aber das war nun relativ naiv.
Und wenn wir also jetzt ein bisschen mehr nachdenken, dann kamen wir
eben auf Verfahren, das M² hatte, war der Jarvis-March, Gram-Scan
hatte NlogN, Jarvis-March hatte im besten Fall lineare Zeit, und hier
haben wir tatsächlich im Mittel lineare Zeit.
Das ist aber eben nur für die Annahme, dass wir gleich verteilte
Punkte haben.
Und da jetzt diese Annahme dabei steht, kann man sich überlegen, dann
gibt es vielleicht doch noch etwas, was hier wichtig ist.
Also für den schlechtesten Fall ist es tatsächlich so, dass man zeigen
kann, dann brauchen wir genauso viel Aufwand wie für das Sortieren.
Die Überlegung ist ganz einfach.
Wir konstruieren uns eine Menge von Endpunkten, die auf einer Parabel
liegen.
Dann liegt jeder Punkt, hier ist auch sofort was angegeben, hier
liegen die Punkte, liegen alle außen, sind alles Extrempunkte.
Die sind mir irgendwie gegeben, diese Menge von Punkten.
Damit ich diese Reihenfolge herstellen kann, muss ich sie sortieren,
diese Endpunkte.
In dem Augenblick, wo ich sie sortiert habe, habe ich eine Reihenfolge
der Punkte auf der konvexen Hülle.
Das heißt, ich habe die konvexe Hülle schon gegeben.
Das heißt, der Aufwand bei dieser Instanz für die Bestimmung der
konvexen Hülle besteht einzig und allein darin, diese Punktmenge zu
sortieren.
Danach bin ich fertig.
Das ist ein schlechter Fall für konvexe Hülle.
Für diesen Fall habe ich als untere Schranke für den Aufwand die
gleiche untere Schranke für das Sortieren, also N log N.
Und hier also habe ich für das mittlere Verhalten aber Omega von N als
untere Schranke.
Gleich verteilte Punkte, dann habe ich halt lineare Zahlen.
Insofern ist es ein bisschen anders als beim Sortieren, aber für den
schlechtesten Fall habe ich N log N als untere Schranke.
Sehr einfaches Beispiel.
Und das Schöne ist bei der algorithmischen Geometrie, man kann häufig
sehr einfache Beispiele angeben, um sich bestimmte Probleme dort oder
Eigenschaften zu verdeutlichen.
Man kann hier noch sehr viel mehr interessante Fragestellungen
betrachten, zum Beispiel Wochenneudiagramme und all solche Dinge, also
eine Aufteilung der Fläche.
Wobei ich eine Punktmenge habe, dann will ich gerade so die Linien
haben, die alle den gleichen Abstand jeweils haben zwischen
benachbarten...
Ups, das war falsch.
Die möchte ich gerne so darstellen, dass ich jeweils hier Linien habe,
die gleichen Abstand haben zu den Punkten der Menge.
Es gibt verschiedenste Probleme, die man sich angucken kann.
Ich habe das hier nicht alles drin in diesem Kapitel, aber ich wollte
einen Eindruck davon geben, welche Art Probleme man betrachtet und
welche Art von Vorgehensweise man hat, um diese Algorithmen zu
entwerfen.
Wir haben Planesweep kennengelernt.
Wir haben eben jetzt gerade bei der konvexen Hülle gesehen, dass man
durch Ausnutzen unterschiedlicher Eigenschaften in der Lage ist, sehr
verschiedene Verfahren für die Bestimmung der konvexen Hülle zu
bestimmen.
Und bei dem Anfangsproblem mit dem Range-Search-Problem, also Absuchen
von Bereichen, da hatten wir gesehen, dass man durch Vorbereitung den
Aufwand für die eigentliche Ausführung der Fragen, wie man hat, wie
viele Punkte liegen innerhalb eines Rechtext, dann auf einmal von N²
im einfachen Verfahren runterkommt auf logarithmische Zeit.
Man hat aber quadratische Zeit, um die ganze Voreinstellung zu machen.
Das ist also das, was ich Ihnen über rhythmische Geometrie erzählen
wollte.
Und damit sind wir mit diesem Kapitel durch.
Es kommt ein Kapitel, das ich Ihnen in der erstletzten Nacht
bereitgestellt habe.
Sie werden es wahrscheinlich noch nicht ausgedruckt haben oder nicht
vor sich liegen haben.
Sie haben das sogar schon.
Ich bin erstaunt.
Sehr gut.
Das wurde mir gestern klar, dass ich das noch gar nicht bereitgestellt
hatte.
Aber es ist jetzt da.
Und ich wollte Ihnen noch ein Problem vorstellen über Algorithmen, die
wir bisher eigentlich sehr vernachlässigt haben, nämlich die
verteilten Algorithmen.
Ich habe Ihnen bisher viel erzählt über sequenzielle Algorithmen, über
Parallele, auch über Hardware-Algorithmen.
Also wir hatten uns da mit verschiedensten Effekten beschäftigt.
Und das, was eigentlich noch gar nicht vorkam, waren verteilte
Algorithmen.
Und da ich die verteilten Algorithmen nicht mehr in einer extra
Vorlesung behandelte, dachte ich, ich kann mal einen Punkt einfach
rausnehmen und hier noch in diese Vorlesung mit reinstecken.
Das passt hier von der Zeit noch ganz gut rein.
Und jetzt habe ich hier ein Problem aufgeführt.
Leader Election.
Auswahl eines Handführers, eines Leiters.
Und zwar in verteilten Algorithmen.
Und an dem Beispiel kann ich Ihnen so einige Prinzipien von verteilten
Algorithmen darstellen, die dort eine Rolle spielen.
Also nochmal, worum geht es?
Ich habe eine Menge sequenzieller Prozesse.
Eine Menge sequenzieller Prozesse, die unabhängig voneinander
arbeiten.
Also ich habe hier eine Reihe von unabhängig voneinander arbeitenden
Prozessen.
Aber die sind nicht völlig unabhängig voneinander, sondern die wollen
durchaus in der Lage sein, miteinander zu reden.
Das heißt, die schicken irgendwelche Nachrichten raus und wollen
irgendwelche Nachrichten bekommen.
Das heißt, ich brauche hier irgendeine Art Kommunikationsnetz und da
sollen die jetzt jeweils in der Lage sein, zu kommunizieren.
Über irgendein Kommunikationsnetz.
Wie, ist mir völlig egal.
Die sind in der Lage, eine Nachricht rauszuschicken und können
Nachrichten bekommen.
Nur das ist wichtig.
Wie die Nachrichten dann über dieses Kommunikationssystem
weiterlaufen, lassen wir hier mal raus.
Wir haben also Kommunikation zwischen unseren Prozessen.
Die können miteinander reden.
Und wir nehmen in der Regel an, dass die in einem verteilten System
räumlich tatsächlich weit voneinander entfernt sind.
Können also beliebige Rechner im Internet sein.
Wir nehmen in der Regel an, dass das irgendwelche leistungsfähigen
Prozessoren sind.
Wie leistungsfähig, kann man sich überlegen.
Aber wir nehmen an, dass die relativ schnell sind.
Was heißt relativ schnell?
Relativ im Vergleich zum Aufwand, um zu kommunizieren.
Klassische Situation im Augenblick.
Wenn sie kommunizieren, sind sie im Millisekundenbereich.
Wenn sie Ping machen zu einem Rechner, sind sie im
Millisekundenbereich.
Wenn sie rechnen, sind sie im Nanosekundenbereich.
Das heißt, sie haben mit mehreren Größenordnungen Unterschied in der
Zeit für Ausführung einer Anweisung und Zeit für Kommunikation.
Das heißt, die Kommunikation ist wesentlich teurer als das Rechnen.
Das charakterisiert also verteilte Algorithmen.
In der Regel haben wir auch heterogene Netze.
Das heißt, die einzelnen Rechner können unterschiedlich kräftig sein.
Hier mal angedeutet durch die Größe des Notens, den ich male.
Wir haben auch unterschiedliche Verbindungen.
Sie wissen nur, sie können Nachrichten rausschicken und können wieder
Nachrichten empfangen.
Und Beispiele sind eben beliebig anzugeben.
Alle möglichen Rechner, die irgendwie miteinander verbunden sind.
Im weitestmöglichen Fall alle Rechner im Internet.
Das heißt, beliebige Rechner.
Es kann auch sein, dass es nur Rechner sind hier in diesem Raum.
Es kann auch ein verteiltes System sein.
Was mache ich mit solchen verteilten Algorithmen?
Ich möchte zunächst mal irgendein beliebiges Problem lösen.
Beliebiges Problem, wie ich auch mit sequenziellen oder parallelen
Algorithmen angeschaut habe.
Was interessant ist, aber ich habe auch Probleme, die treten nur in
verteilten Algorithmen auf.
Also in verteilten Systemen.
Ich muss mir zunächst mal angucken, welche typischen Probleme treten
eigentlich auf, wenn solche verteilten Rechner miteinander etwas tun
sollen.
Das ist interessant, das ist eine ganze Reihe von Problemen, die ich
hier betrachten muss.
Im Prinzip sind das Betriebssystemaufgaben.
Ein verteiltes Betriebssystem, um eine vernünftige, gemeinsame
Arbeitsweise von solchen Rechnern zu ermöglichen.
Das erste, was ich gewährleisten muss, ist zuverlässige Kommunikation
und Kooperation.
Die müssen überhaupt miteinander reden können.
Ich muss die Kommunikation aufrechterhalten, ich muss wissen, ob sie
kommunizieren können oder nicht.
Es mag sein, dass ich die Netztopologie herausfinden möchte.
Die muss nicht unbedingt von vornherein gegeben sein.
Das System sollte vielleicht aber wissen, was für eine Topologie das
ist, also wie die Rechner miteinander verbunden sind.
Ist das irgendein Stern?
Oder ist das vielleicht ein Ring?
Oder was ist das für eine Struktur?
Das kann wichtig sein für die Art der Verfahren, mit denen man dann
andere Probleme sinnvollerweise löst.
Ich möchte in der Lage sein, Nachrichten effizient zu verteilen.
Das kann ich nur machen, wenn ich etwas weiß über die Netztopologie.
Wer ist mit wem direkt verbunden.
Manchmal muss ich etwas wissen darüber, welcher Zeitpunkt gerade ist.
Wie machen wir das normalerweise?
Wir schauen auf die Uhr.
Wenn wir beide auf die Uhr schauen, dann werden wir wahrscheinlich
unterschiedliche Zeiten anschauen.
Und wenn ich auf den Rechner schaue, wird es noch eine andere Zeit
sein.
Wenn jetzt aber Rechner etwas gemeinsam tun sollen.
Und stellen Sie sich vor, Sie haben eine verteilte Auktion.
Und Sie machen mit einer verteilten Auktion irgendeine Entscheidung.
Dann müssen Sie wissen, zu welchen Zeitpunkten irgendetwas passiert
ist.
Oder ganz allgemein, Sie haben irgendein Verfahren, bei dem auf
unterschiedlichen Rechnern etwas getan wurde.
Jetzt müssen Sie wissen, wann hat der hier eine Nachricht
rausgeschickt.
Wann ist die hier angekommen?
Dieses Wann wird aber gemessen aufgrund der lokalen Zeit an den beiden
Knoten.
Jetzt machen Sie eine Auflistung aller Aktionen, die in Ihrem
verteilten System gewesen sind.
Woher wissen Sie, wie die Zeiten, die hier gemessen werden bei A, wie
die in Beziehung stehen zu den Zeiten, die bei B gemessen werden.
Sind das die gleichen Zeiten?
Unterschiedliche Zeitzonen vielleicht sogar.
Wie können Sie das denn genau vergleichen?
Wer hat denn eigentlich wann was verschickt?
Also, das ist gar nicht so einfach.
Man möchte gerne in der Lage sein, tatsächlich Aussagen zu machen
darüber, dass Ereignisse, die bei A auftreten, Vorereignisse, die in B
auftreten, geschehen sind.
Es gibt eine globale Zeit.
Dazu müssen die alle eine Ahnung haben, wie sie ihre Ereignisse
nummerieren müssen, mit Zeitstempeln versehen müssen, damit man so
eine globale Zeit tatsächlich hat.
Dafür kann man auch im Verfahren sich überlegen, wie man mit vielen,
also selbst wenn man viele verschiedene lokale Uhren hat, trotzdem
eine gemeinsame Zeit bekommen kann.
Sobald ich eine synchronisierte Zeitmessung habe, kann ich Aussagen
machen über Reihenfolgen von wesentlichen Ereignissen.
Das ist jedenfalls zunächst mal nicht trivial, wie man das hinkriegt.
Natürlich kann man sagen, ich nehme einfach ein GPS-Signal.
Habe ich irgendeinen globalen Zeitgeber, da ist die Zeit, und die, das
Signal, gebe ich einfach zu allen.
So eine globale Kommunikation, bzw.
man macht es ja anders, jeder empfängt GPS-Signale und kann dann
daraus auch die Zeit empfangen.
Eine Möglichkeit, die besteht, haben wir aber nicht unbedingt zur
Verfügung.
Und dann ist das Synchronisieren von solchen Rechnern gar nicht so
einfach.
Und es gibt also insbesondere Verfahren, bei denen man sagt, ich
möchte gerne alle Operationen gleichmäßig machen.
Gleichzeitig sollen alle eine Operation ausführen.
Gleichzeitig muss eben heißen, wenn ich hier meine Zeit angucke,
innerhalb eines bestimmten Zeitintervalls sollen alle Aktionen
ausgeführt worden sein, auf meinen N-Rechnern.
Dann können die nächsten ausgeführt werden.
Ich habe also irgendwelche zeitlichen sogenannten Runden.
Ich habe hier Runde 1, Runde 2 usw.
und kann dann ein einigermaßen synchrones Verhalten tatsächlich
durchführen.
Datenverwaltung auf solchen Rechnern.
Was ist mit Konsistenz von Daten?
Wie sieht es aus mit dem Zugriff?
Lesend, schreiben, wer darf wann auf welche Daten zugreifen?
Inwieweit habe ich hier Daten repliziert?
Ich muss wahrscheinlich sogar Daten replizieren.
Ich weiß ja gar nicht, wie lange ein solcher Knoten tatsächlich am
Netz ist.
Vielleicht geht er irgendwann weg.
Die Daten, die dort bearbeitet werden, sind aber vielleicht wichtig
für mein privates Problem.
Da werde ich einige Daten auch redundant ablegen müssen.
Ein typisches Problem in sogenannten Peer-to-Peer-Netzen, wo ich einen
spontanen Zugang und Abgang von Knoten haben kann.
Und wenn die gemeinsam eine Datenverwaltung machen, dann muss ich
dafür sorgen, dass die Daten selbst bei Ausfall eines Rechners
verfügbar sind.
Konsistenz hatte ich schon angesprochen.
Wenn ich replizierte Daten habe, wie stelle ich sicher, dass nach
einem schreibenden Zugriff überall die gleichen Daten stehen.
Synchronisation von Startzeiten hat etwas zu tun mit der globalen
Zeit.
Es gibt so ein typisches Problem, das sogenannte Firefly-Problem.
Firefly-Problem ist folgendes, oder Firefly-Effekt, den man in der
Natur beobachten kann.
Es gibt Insekten, die die Eigenschaft haben, dass sie...
Sie haben so eine Leuchtmöglichkeit, ähnlich wie Glühwürmchen.
Glühwürmchen leuchtet meistens über längeren Zeitraum.
Diese Fliegen hier, diese Fireflies, die leuchten nur für einen kurzen
Augenblick.
Also, wenn man sie anschaut, die leuchten mal für einen Augenblick,
dann leuchten sie nicht, dann leuchten sie wieder, dann leuchten sie
wieder, dann leuchten sie wieder.
Und das interessante ist, wenn man sich einen solchen Schwarm von
Fliegen anschaut, dann leuchten die alle gleichzeitig.
Das heißt, die fliegen da irgendwie im Schwarm rum, und auf einmal
leuchten die alle gleichzeitig.
Das heißt, sie haben so einen blinkenden Effekt.
Es ist interessant, sich anzugucken, wie kann man das eigentlich
hinbekommen, dass irgendwelche Insekten, die eigentlich gar nicht
miteinander reden, die machen ja keine Abstimmung, wann sie
tatsächlich anfangen wollen, die sind in der Lage, gleichzeitig
aufzuleuchten und wieder ihr Leuchten zu beenden.
Das ist also ein sogenanntes Firefly-Effekt, das beobachtet worden
ist, ein Lagerfeuer, wo dann solche Schwärme von Fliegen rumfliegen,
und auf einmal leuchten die als Schwarm gleichzeitig.
Kann man nachbilden, kann man sich Verfahrens überlegen, wie man das
hinbekommen kann.
Das ist also eine Synchronisation zwischen den einzelnen Insekten.
Man kann das in verteilten Systemen nachbilden.
Terminierungserkennung.
Sie haben eine Aufgabe, die auf vielen Rechnern gemacht werden soll.
Jetzt wollen Sie irgendwann feststellen, ich bin fertig.
Der eine ist fertig.
Sind die anderen auch fertig?
Woher weiß ich, dass alle anderen fertig sind?
Gar nicht so einfach.
Also wenn einer fertig ist, wenn eine Operation beendet ist, dann
macht er ja nichts mehr.
Wie kann ich also feststellen, dass alle anderen beendet sind?
Fehlerbehandlung.
Was mache ich, wenn einer ausfällt, wenn er etwas Falsches macht?
Wahl eines Anführers.
Habe ich schon gesagt, das ist das Problem, das wir genauer angucken
werden.
Wie kann ich einen auswählen?
Für irgendwelche Aufgaben.
Meinetwegen Taktgeber für irgendwas.
In dem Augenblick, wo ich einen Anführer habe, können sich alle nach
dem Anführer richten.
Dann ist Synchronisieren einfach.
Aber wie mache ich das?
Beziehungsweise, wie stelle ich sicher, dass einer weiß, er ist
Anführer, und alle anderen wissen auch, dass das der Anführer ist?
Wir sehen in praktischen Beispielen, dass das in der Welt der Menschen
auch gar nicht so einfach ist, um einen Anführer zu wählen.
Vor allem, wenn alle einigermaßen gleichberechtigt sind, und es nicht
auf Geburt oder Ähnliches ausgerichtet ist, dass jemand der Anführer
ist.
Sondern das muss irgendwie bestimmt werden.
Ganz allgemein ist das ein Konsensverfahren.
Das heißt, ich habe eine Menge von Prozessen, und die müssen sich
einigen über irgendein Sachverhalten.
Ich muss eine Entscheidung treffen, bei der es mehrere mögliche
Antworten gibt, und die Aufgabe ist, in einem verteilten Verfahren
dafür zu sorgen, dass alle am Ende die gleiche Entscheidung getroffen
haben, beziehungsweise wissen, welche Entscheidung getroffen wurde.
Alle müssen das gleiche Ergebnis dieser Entscheidung kennen.
Und das heißt, wir müssen einen Konsens erreicht haben.
Leader Election, Wahl eines Anführers, ist ein solches Konsensproblem.
Alle wollen einen Anführer haben.
Der Anführer muss wissen, dass er Anführer ist.
Und alle anderen müssen wissen, dass das tatsächlich der Anführer ist.
Und mit solchen Problemen wollen wir uns jetzt genauer beschäftigen.
Solche Konsensverfahren und das schöne Beispiel, diese Leader Election
Verfahren.
Dazu müssen wir jetzt genauer das nochmal angucken.
Beispiele von verteilten Algorithmen.
Suchmaschinen sind typische Beispiele für verteilte Algorithmen.
Wenn Sie also das Internet nach Informationen absuchen, das können Sie
alles von einem Rechner machen.
Sie können es aber auch verteilen, indem Sie so eine Spider da
rumlaufen lassen.
Also einzelne Agenten, die Sie praktisch auf den verschiedenen Knoten,
den wesentlichen Knoten verteilen.
Und dann eine verteilte Suche nach neuer Information machen.
So arbeiten heutzutage alle Suchmaschinen.
Dass die eigentlich ein völlig verteiltes System haben.
Die nennt man dann Spider oder nennt man auch Bots manchmal.
Bot, Abkürzung von Robot.
Roboty heißt ja Arbeiten im Russischen.
Also Arbeiter, verkürzte Arbeiter, also ein Bot.
Kein Robot.
Bots sind häufig identifiziert mit irgendwelchen negativen Dingen.
Dass es irgendwelche Malicious Agents sind.
Also irgendwelche Agenten mit schlechten Eigenschaften oder mit
Angriffsideen.
Also es mag Institutionen geben, die Bots verteilen, mit irgendwelchen
Vorhaben etwas auszuspielen.
Und wir kennen solche Ansätze sowas zu machen.
Aber es gibt viele solche verteilte Agenten, die irgendwelche
Informationen sammeln.
Aus verschiedensten Gründen.
Ja, aus wirtschaftlichen Gründen, aus sonstigen Gründen auch.
Ok, und dann werden eben Anfragen beantwortet.
Irgendeine Anfrage muss beantwortet werden.
Dafür brauche ich Informationen von vielen Rechnern.
Das ist ein typisches verteiltes Verfahren heutzutage.
Verkehrssteuerung.
Sie haben ihr Straßennetz, irgendwelche Straßen, die irgendwie
miteinander verbunden sind und haben alle möglichen Kreuzungen.
Und jetzt wollen sie diesen Verkehr steuern auf diesen Kreuzungen oder
zwischen diesen Kreuzungen.
Dazu haben sie Informationen darüber, wie viele Autos hier jeweils
hinkommen, wie viele wegfahren usw.
Sie haben also lokale Daten.
Sie können lokal eine Steuerung vornehmen.
Sie können die Daten alle sammeln in einem zentralen Rechner.
Und der kann das Ganze steuern.
Sie können auch verteilt Entscheidungen treffen.
Und Sie können zum Beispiel auch sich überlegen, naja, wenn diese
Knoten feststellen, ganz viel Verkehr läuft immer in diese Richtung,
dann würde es Sinn machen, dass die sich synchronisieren und dafür
sorgen, dass die Autos durchfahren können, ohne anhalten zu müssen,
was wir normalerweise grüne Wellen nennen.
Auch etwas, was man planen kann, zentral.
Man kann aber auch sagen, die Ampelsteuerer und die Kreuzungen wissen
ja, wie die aktuelle Situation ist.
Und wenn die so ist, dass eine solche grüne Welle sinnvoll ist, dann
können wir das ja auch gemeinsam entscheiden.
Ist also auch ein Ansatz für verteilte Verkehrssteuerung.
Da haben wir auch bei uns am Lehrstuhl Verfahren für entwickelt.
Energiesysteme, weiteres Beispiel.
Das Energiesystem ist ein weit verteiltes Netz.
Heutzutage ist die Intelligenz an relativ vielen zentralen Punkten,
oder wenigen zentralen Punkten.
Sie muss aber vielmehr dezentral an verteilten Punkten vorhanden sein.
Insbesondere reden wir heute über den Bedarf an demand-side
-management, also am Rande des Netzes bei den Verbrauchern,
tatsächlich eine Steuerung des Verbrauchs zu machen.
Etwas, was eigentlich bisher gar nicht möglich war.
Weil man meinte, das brauchen wir ja nicht, weil wir ja das Angebot an
Energie ständig beeinflussen können.
Wir drehen einfach die Kraftwerke rauf oder runter, je nachdem welche
Nachfrage da ist.
Wir können sie leider nicht eine Photovoltaikzelle rauf oder runter
drehen, sondern nicht aufdrehen.
Wir können sie eventuell etwas reduzieren.
Wir können auch ein Windkraftwerk, können sie auch das Windrad einfach
abstellen und nicht mehr Strom produzieren lassen.
Aber wir haben das Ziel, dass wir das Angebot an erneuerbarer Energie
weitgehend nutzen wollen.
Das heißt, im Prinzip ist das nicht beeinflussbar.
Und dann müssen sie den Verbrauch steuern, dann müssen sie lokal
Entscheidungen treffen, an ganz vielen Punkten im Netz.
Also wenn sie hier so ein Netzsegment haben, dann haben sie hier also
irgendwelche Endverbraucher und die sollen alle irgendwie entscheiden,
was sie mit ihren Verbrauchern machen, zu welchen Zeiten sie die
einsetzen.
Das ist eine interessante Aufgabe für verteilte Algorithmen.
Ein weiteres Problem heutzutage, Big Data, Data Mining.
Sie haben große verteilte Datenbanken, wollen die Informationen
sammeln.
Hat was zu tun, auch mit den Suchmaschinen hier oben.
Aber das Thema Big Data hat nicht nur mit Suchmaschinen zu tun,
sondern auch mit anderen riesigen Datenmengen.
Und sie wollen hier interessante Informationen sammeln.
Die kann nicht erfassen, was eine interessante Information ist.
Das ist so das typische von Data Mining oder dem Schlagwort heutzutage
Big Data.
Dass sie zunächst mal gar nicht wissen, welche Informationen
eigentlich da sind.
Und sie suchen interessante Artefakte in solchen Datenmengen.
Manchmal suchen sie auch nach bestimmten Dingen.
Irgendwelche Schlüsselwörter oder ähnlichen.
Das kann man auch machen, um in riesigen Datenmengen etwas zu suchen.
Aber wenn sie einfach nur die riesigen Datenmengen haben, sie haben
also meinetwegen Energiedaten.
Sie wollen wissen, was sind interessante Verbrauchsmuster in solchen
Energiedaten.
Dann müssen sie halt irgendwie Verfahren haben, um statistische
Untersuchungen zu machen.
Und dort irgendwelche interessanten Wiederholungen oder Ähnliches
festzustellen.
Also da gibt es zig verschiedene Verfahren.
Verfahren ist nicht mein Thema direkt, aber ein relativ wichtiges
Thema.
Agentensysteme allgemein sind verteilte Algorithmen.
Und bei den meisten Problemen, die ich hier genannt habe, gibt es zwar
Möglichkeiten, etwas zentral zu machen.
Aber wenn sie sehr große verteilte Systeme haben, da ist eigentlich
eine zentrale Entscheidung oder zentrale Informationsverarbeitung gar
nicht mehr sinnvoll.
Sondern sie haben als sinnvollste Realisierung die verteilte
Bearbeitung.
Und da müssen sie mit all diesen Problemen umgehen können, die ich auf
der vorigen Folie genannt habe, was so typische Probleme bei einer
verteilten Bearbeitung sind.
Die muss man zunächst mal im Griff haben.
Und damit werden wir uns dann beschäftigen, sobald wir etwas wissen,
auch über die kostenverteilten Algorithmen.
Das eine, was gemacht wird, ist etwas im Rechner, im Knoten.
Wie schon gesagt, die Rechenzeit in Prozessoren, die ist gar nicht so
hoch.
Beziehungsweise im Vergleich zum Kommunikationsaufwand muss natürlich
im Rechner auch etwas tun.
Aber da die Ausführungszeit der einzelnen Instruktionen im Rechner um
mehrere Größenordnungen kleiner ist als der Kommunikationsaufwand,
kann ich auch sagen, die Rechenzeit, die ist vernachlässigbar.
Ich kann sagen, ist null oder ist konstant, also die spielt keine
Rolle.
Natürlich, beim Faktor ist null oder konstant schon wichtig.
Also ich nehme an, die spielt keine Rolle.
Ich vernachlässige die einfach.
Ich zähle nur den Kommunikationsaufwand.
Wie ist der Kommunikationsaufwand überhaupt definiert?
Ich kann mir angucken, die Anzahl der Nachrichten.
Zwei Knoten tauschen Nachrichten aus.
Das können die natürlich sehr unterschiedlich groß sein.
Was ist dann der Nachrichtenaufwand?
Die Anzahl der Nachrichten?
Verschicken Sie dann kleine Dateien mit jeweils wenigen Bytes?
Oder verschicken Sie Gigabyte-Nachrichten?
Oder Megabyte-Nachrichten?
Das heißt, die Anzahl der Nachrichten zu zählen, macht nur Sinn, wenn
ich weiß, dass die Nachrichten alle einigermaßen gleich groß sind.
Sie erinnern sich an ein Problem, das Sie ganz zu Anfang der Vorlesung
betrachtet haben.
Das war die Aufwandsabschätzung für einzelne Operationen.
Da hatten wir das Uniform- und das logarithmische Kostenmodell.
Das brauchen wir hier im Prinzip auch.
Wir müssen uns anschauen, die Länge der Nachrichten, bzw.
wir könnten zählen, die Bits aller Nachrichten.
Beziehungsweise, wenn ich konstante Nachrichtengröße habe, reicht es,
alle Nachrichten zu zählen.
Wenn die Nachrichten unterschiedlich lang sein können, dann müsste ich
die Längen aller Nachrichten addieren, bzw.
die Bits aller Nachrichten zählen.
Und was natürlich auch eine Rolle spielt, sind die Übertragungszeiten.
Das Problem ist, wenn Sie ein großes Netz haben, dann sind die
unterschiedlich lang, die Verbindungen.
Das sieht hier so einfach aus, dass die so direkt verbunden sind.
Das muss ja nicht so sein, dass das direkte Leitungen sind.
Das ist ja irgendein Kommunikationsnetz.
Nun kann es sein, dass wenn Sie hier von A nach B eine Nachricht
schicken, dass die relativ schnell geht, oder von A nach C oder A nach
D, mag es sehr lange dauern.
Das heißt, Sie können eigentlich in einem verteilten System kaum
Aussagen darüber machen, wie groß die Zeit ist für die Übertragung.
Man macht das normalerweise so, dass man irgendwelchen Zähler hat.
Also irgendeinen Zähler.
Und setzt den also zu Anfang auf irgendeinen Wert K.
Und dann zähle ich runter, bis T gleich Null ist.
Und wenn er auf Null ist, dann sage ich, okay, Time Out.
Und ich darf die Aktion nochmal machen.
Das heißt, ich mache irgendwelche Annahmen über die Dauer einer
Kommunikation.
Jetzt kann es ja sein, dass ein Knoten ausgefallen ist.
Da will ich nicht mit meinen Algorithmen warten müssen, ewig warten
müssen.
Da kommt gar keine Antwort mehr.
Dann muss ich irgendeine Entscheidung treffen, wenn ich so einen Time
Out festgestellt habe.
Das heißt, die Übertragungszeiten sind ein schwieriges Thema.
Die können auch von Mal zu Mal unterschiedlich sein.
Und deswegen beschränkt man sich darauf, nur den Kommunikationsaufwand
zu bestimmen, in Bezug auf Anzahl der Bits aller Nachrichten.
Das ist eigentlich das, was wir normalerweise messen, als Aufwand für
den verteilten Algorithmus.
Wir können nur annehmen, ich kann Nachrichten verschicken, ich kann
Nachrichten empfangen, aber ich weiß nichts über die Dauer.
Es kann sein, dass Nachrichten verschwinden.
Ich kann auch annehmen, irgendwann werden sie ankommen.
Also keine verschwinden.
Auch das muss ich überlegen.
Also diese ganzen Fehlerüberlegungen.
Was passiert, wenn eine Nachricht nicht ankommt?
Wie gehe ich damit um?
Ist auch ein wichtiges Thema, das ich hier gar nicht behandeln werde,
in diesem kurzen Abschnitt.
Also die ganzen Fragen der Fehlerbehandlung.
Ist ein wichtiges Thema bei verteilten Algorithmen.
Was mache ich, wenn Fehler auftreten, wenn Nachrichten verschwinden?
Oder wenn Knoten ausfallen, oder wenn Nachrichten verfälscht werden?
Interessante Fehler, sogenannte byzantinische Fehler.
Wieso nennt man die byzantinische Fehler?
Byzantinisch, das hat was zu tun mit kriegerischen Handlungen, wieso
vieles in der Informationsverarbeitung mit irgendwelchen militärischen
Dingen zu tun hat.
Da hat man irgendwelche Nachrichten verschickt, um Informationen von
einem Truppenteil zum anderen zu schicken, durch feindliche Linien
hindurch.
Und dann gab es irgendeinen Kurier, der halt falsch gehandelt hat,
oder der ein Spion war, oder eben ein Saboteur, der einfach
Nachrichten verfälscht hat.
Von daher nennt man das byzantinische Fehler.
Wenn Nachrichten verfälscht werden, ich kann nicht mal sowas erkennen.
Also Fehlerbehandlung ist ein interessantes Thema, blende ich hier
völlig aus.
Ist aber ein wichtiges Thema in verteilten Algorithmen.
Wenn ich eine Vorlesung halte darüber, dann ist das ein wichtiges
Kapitel, wie ich mit solchen Fehlern umgehe.
Ein anderer Punkt ist, es ist ja so, dass diese verteilten Rechner
nicht alle nur schrecklich sind.
Ich weiß nicht, wie lange die Nachrichten laufen.
Irgendwann kommt was an.
Ich kann mich nicht darauf verlassen.
Ich brauche die ganzen Zähler.
Ich muss Timeout-Zähler machen und all sowas.
Das hört sich ja alles schrecklich an.
Warum mache ich nicht alles auf einem Rechner?
Ich kann viele Operationen nicht sinnvoll nur auf einem Rechner
machen, weil Berechnungszeiten zu groß sind.
Ich möchte gerne meine Berechnung auf mehrere Rechner verteilen.
Und wenn ich dort dicke Berechnungen habe, sehr aufwendige
Berechnungen, dann ist diese Annahme hier oben, dass die Rechenzeit
gleich 0 ist, natürlich nicht richtig.
Dann habe ich eher so Situationen, dass ich irgendeine Berechnungszeit
habe und da soll kommuniziert werden.
Dann warte ich auf einen anderen Rechner.
Dann warte ich wieder auf einen anderen Rechner.
Und nochmal auf einen anderen Rechner.
Und ich möchte gerne diese Wartezeiten hier verstecken hinter
Berechnungen.
Wenn ich also sehr aufwendige Berechnungen habe, und ich muss
kommunizieren zwischen Rechnern, die gemeinsam ein schwieriges Problem
bearbeiten, dann muss ich dafür sorgen, dass diese Zeiten hier
zwischen für die Kommunikation irgendwie versteckt werden.
Das ist aber etwas, was wir schon öfter angeguckt haben in anderen
Zusammenhängen, im ganzen Verfahren der Pipelining, also des
vernünftigen Überlappens der Ausführung von verschiedenen Prozessen.
Ich muss also in der Lage sein, ein sogenanntes Latency-Hiding zu
machen.
Das ist das typische Schlagwort dafür, dass ich Kommunikation hinter
Berechnungen verstecke.
Während eine Kommunikation ausgeführt wird, durch irgendeinen internen
Kommunikationsprozessor, rechne ich an meinem Problem weiter und werde
nicht aufgehalten.
Das ist also ein weiteres wichtiges Thema, das man sich hier anschaut.
Aber das ist ein Thema, was sich beschäftigt mit dem Aufwand für große
schwierige Probleme und wie man diesen Aufwand verteilen kann, ohne
dass der Kommunikationsaufwand die Berechnungszeit vernachlässigt,
also ein Overhead verursacht.
Und das ist eine interessante Art, solche verteilten Algorithmen zu
entwerfen.
Ich schaue mir aber im Weiteren erstmal die Probleme an, die ich habe,
um überhaupt mit verteilten Systemen umzugehen.
Da ist eben das typische Problem der Abstimmung in einem solchen
verteilten System.
Wie kann ich dafür sorgen, dass die alle zu einer einheitlichen
Meinung kommen, über das Ergebnis einer Entscheidung?
Der typische Fall ist, dass ich irgendeinen Anführer wähle.
Das Wiederelection-Problem.
Das schauen wir uns jetzt sehr intensiv an.
Und Sie werden sehen, dass wir das durchaus intensiv anschauen oder in
einer vereinfachten Situation.
Wir werden uns im Wesentlichen auf ringverbundene Prozessoren
beschränken.
Ich fange aber zunächst mal damit an, dass wir sagen, wie ist das
Problem definiert.
Konsensproblem, ich habe vollständig gleichberechtigte Prozesse.
Hört sich leicht an, hat drastische Konsequenzen.
Vollständig gleichberechtigt heißt, jeder Prozess ist in gleicher
Weise beteiligt.
Das heißt, jeder dieser Prozesse P0 bis Pn-1 hat die gleiche Chance,
Leiter zu werden.
Vollständig gleichberechtigt.
Es werden keine differenzierenden Eigenschaften ausgenutzt.
Beim Start des Algorithmus ist völlig offen, wer Leiter wird.
Es mag sein, dass man einen Leiter hatte, der ist ausgefallen und man
braucht einen neuen Leiter.
Irgendeiner muss es machen.
Und wir sagen nebenan, die sind vollständig gleichberechtigt.
Vollständig gleichberechtigt heißt, niemand darf aufgrund einer
speziellen Eigenschaft, z.B.
seiner Identität, ausgewählt werden.
Wenn Sie hier vollständig gleichberechtigte Prozesse haben und diese
durchnummeriert, dann wäre es natürlich einfach zu sagen, ich nehme
einfach den mit der kleinsten Nummer.
Das ist ja einfach.
Dann sind sie aber nicht alle gleichberechtigt.
Der, der leider hier so eine Nummer 17 abgekriegt hat, der wird ja nie
Leiter, weil so viele andere eine kleinere Nummer haben werden.
Das geht nicht.
Das wäre nicht vollständig gleichberechtigt.
Alle Beteiligten sollen in gleicher Weise mitwirken.
Sonst wären sie ja nicht gleichberechtigt.
Wenn die unterschiedliche Dinge machen, dann sind sie ja nicht
wirklich gleichberechtigt.
Der eine kann vielleicht mehr als der andere.
Nicht gleichberechtigt.
Das geht nicht.
Das heißt, das hier nennt man auch symmetrisch.
Und auch also vollständig verteilt, es sollen alle wirklich etwas tun.
Alle müssen das gleiche machen.
Am Ende der Wahl müssen alle Beteiligten die gleiche Information über
die Identität des Leiters haben.
Es macht keinen Sinn, wenn die nicht einer Meinung sind, wenn sie
meinen unterschiedliche Leute gewählt zu haben.
Und das heißt, ich muss einen vollständig verteilten, symmetrischen
Algorithmus haben.
Jeder ist gleichartig beteiligt und hat die gleiche Chance tatsächlich
gewählt zu werden.
Und sie entscheiden lokal.
Die können also nur durch Kommunikation untereinander oder hier über
so ein Kommunikationsnetz kommunizieren.
Führen lokal Operationen aus und alle verfolgen den gleichen
Algorithmus.
Dann sind sie wirklich gleichberechtigt, alles ist symmetrisch, alles
ist schön einhängig.
Da muss man sich überlegen, wie kann es sein, wenn ich keine
wirklichen Möglichkeiten habe, etwas unterschiedlich zu machen, also
unterschiedliche Eigenschaften auszunutzen, wie kann ich dann
überhaupt entscheiden, wer ausgewählt wird.
Außerdem nehmen wir noch an, dass sie durch einen Ring verbunden sind.
Das sagte ich schon.
Das ist also eine einfache Annahme.
Die sind über einen Ring verbunden.
Sehr einfache Topologie.
Das kann ich natürlich ausnutzen für meine Verfahren.
Und der ein Satz, schon ziemlich alt, 33 Jahre alt, von Anguin, der
hat also sich überlegt, dass es in einem Ring identischer Prozessoren
keinen deterministischen, vollständig verteilten und symmetrischen
Algorithmus geben kann zur Wahl eines Leiters.
Liegt einfach daran, was ich jetzt so mehrfach betont habe, alle haben
gleiche Rechte, alle machen das gleiche.
Wenn sie alle das gleiche machen, dann kommen sie entweder in
Deadlocks oder sie hören gar nicht auf.
Das heißt, sie bekommen keine Entscheidung.
Das heißt, dieser idealistische Ansatz hat er gleichberechtigt,
irgendwie müssen die tatsächlich einen auswählen.
Deterministisch, deterministisch heißt, jeder hat genau die gleiche
Entscheidung, alle den gleichen Algorithmus.
Sie kennen ein solches Problem, das Philosophenproblem.
Wer kennt das Philosophenproblem nicht?
Sie kennen das.
Gut, brauche ich nichts mehr zu sagen.
Sie wissen, dass da das Problem ist, wenn ihr alle die rechte Gabel
nehmt, dann kann keiner mehr in der linken Hand die Gabel aufnehmen,
weil die alles schon wechseln.
Alle machen die gleiche Entscheidung, deswegen, wenn man ein
Philosophenproblem lösen will, geht das genauso wenig.
Jetzt müssen wir also sehen, dass wir das anders machen.
Jetzt könnten wir zum Beispiel sagen, wir nutzen einfach die Identität
aus.
Das ist der einfachste Ansatz.
Wir nutzen die Identität aus und sagen, also der Name oder die Nummer
des Prozesses ist Grundlage für die Auswahl des Leiters.
Ist ja völlig egal, welchen wir nehmen.
Können wir auch den nehmen, der die kleinste Nummer hat.
Jetzt haben wir einen Ring.
Und wir wollen den wählen mit der kleinsten Nummer.
Wie kann ich in einem Ring von Prozessen...
Das wahl ich jetzt nicht hier rein, da kommt gleich eine Animation.
Wie kann ich dort den auswählen, die kleinste Nummer?
Das Verfahren steht hier.
Sehr einfach, wir haben hier unsere Situation, das sind unsere
Prozessoren.
Irgendwie durchnummeriert.
Sind nicht alle Zahlen von hier da, einige fehlen, aber irgendwelche
Nummern haben.
Wir sehen natürlich sofort, naja, das ist doch hier die 1.
Aber das kann der natürlich nicht sehen, dass da einer ist mit der
Nummer 1.
Der sieht nur sich selbst und kann Nachrichten an den Nachfolger
schicken.
Jeder kann folgendes machen.
Der kann seinen Namen, seine Identität an den Nächsten schicken.
Die sind halt ringförmig verbunden, gerichteter Ring.
Also schicken sie ihren Namen zum Nächsten.
Alle schicken den raus.
Wieso können die eigentlich alle gleichzeitig ihre Identität
rausschicken?
Das muss nicht unbedingt gleichzeitig sein.
Es kann auch einer anfangen damit.
Der muss dann den Nächsten dadurch aufwecken, dass der die Nachricht
empfängt.
Und bevor er die empfängt, muss er erstmal eine Nachricht
rausschicken.
Das heißt, ich nehme einfach an, die können das gleichzeitig.
Das kann aber zeitlich verteilt sein.
Logisch ist das der erste Schritt, dass alle eine Nachricht
verschicken.
So, jetzt haben wir diese Situation, jeder verschickt die Nachricht.
Jetzt empfängt jeder Prozess eine Nachricht vom Vorgänger.
Also eigentlich vom Predecessor.
Wenn du Predecessor sagst, ist egal.
Also von dem Vorgänger.
Und das heißt, die Eins bekommt die Drei als Nachricht.
Die Sechs bekommt die Eins als Nachricht.
Wenn jetzt der Wert, den man empfängt, mit der kleinsten Nummer wählt.
Wenn der Wert, den man empfängt, kleiner ist als die eigene Identität,
weiß man schon, Pech gehabt, ich bin nicht der Leiter.
Und ich brauche eigentlich dem Nächsten gar nicht mehr meine Nummer,
sondern der soll lieber die Nummer von dem erfahren, der die kleinere
Nummer hat.
Das heißt, als nächstes schicke ich die kleinere Nummer weiter.
Das ist hier, Send X to Next.
Wenn das X kleiner ist.
Und ansonsten mache ich Go Next.
Beziehungsweise, wenn der Name, den ich bekomme, mein eigener Name
ist.
Dann weiß ich, ich bin gewählt.
Ich habe angenommen, das hat hier gar nicht genau gestanden, dass alle
unterschiedliche Identitäten haben.
Jeder hat eine eindeutige Identität, muss auf der vorigen Folie
gestanden haben.
Jeder hat eine eindeutige Identität, die Namen tauchen nicht doppelt
auf.
Wenn also eine Nachricht, wenn der Nummer 1 seinen Namen wieder
bekommt, es werden nur existierende Namen in den Ring verschickt, dann
muss seine Nachricht hier einmal rumgelaufen sein.
Das heißt, derjenige, der seine Nachricht bekommt, kann sie nur
bekommen haben, weil seine Nummer kleiner war, als die von allen
anderen.
Offensichtlich ist er dann gewählt worden.
Wenn er gewählt wurde, dann schickt er einfach Minus X zum nächsten.
Also das, was hier passiert war, war, dass diejenigen, die eine
größere Nummer haben, die kleinere Nachricht rumschicken.
Das heißt, das passierte hier, die Nummer 9 hat die 5 weitergeschickt,
die Nummer 8 hat die 2 weitergeschickt.
Alle anderen hatten größere Namen bekommen, die verschicken gar
nichts.
So, jetzt läuft das hier also eine Weile rum.
Die 1 läuft rum, die 2 läuft rum.
Nochmal, die 2 verschwindet jetzt, weil sie bei der 1 gelandet war.
Die 1 läuft weiter rum.
Und jetzt haben wir die Situation, dass die 1 als nächstes von der 1
empfangen wird.
Und dann weiß derjenige, er ist ausgewählt.
Betrinkt sich, wird blau.
Und die Minus 1 wird weitergeschickt.
Wenn ich eine Minus 1 verschicke, alle Identitäten sind positiv.
Weiß der Nächste, er bekommt, also die haben ja aufgehört hier, also
Until X gleich Idee oder X kleiner als 0.
Ja, wenn also X kleiner als 0 ist, weiß er auch, Pech gehabt, ich bin
nicht gewählt.
Er betrinkt sich, wird auch blau.
Und feiert, dass er nicht Anführer geworden ist.
Und verschickt die Minus 1, beziehungsweise, wo hab ich das jetzt?
Die Minus 1 muss ja weitergeschickt werden.
X ist kleiner als die Identität.
Dann verschickt er X an den Nächsten.
Wenn das ein negativer Wert ist, ist er kleiner als die Identität
jedes anderen Knotens.
Das heißt, jeder verschickt zunächst mal die Minus 1 und stellt dann
fest, X war kleiner als 0, ich bin nicht gewählt worden.
Es war also ein anderer, der gewählt wurde.
So.
Dann steht hier als letztes, If X gleich Idee, also wenn ich
derjenige, der gewählt wurde, dann warte auf eine Nachricht X vom
Vorgänger.
Diese Nachricht kann erst ankommen, wenn die Minus 1 bei allen anderen
vorbeigelaufen ist.
Alle merken nacheinander, dass sie nicht gewählt wurden.
Und dann endlich ist die Minus 1 rumgekommen.
Derjenige bekommt eine Nachricht geschickt, hier in dem Fall.
Und dadurch, dass er eine Nachricht bekommen hat, weiß er, jetzt ist
alles fertig.
Alle anderen wissen auch, dass sie fertig sind, weil sie ja hier
festgestellt haben, der Wert war kleiner als 0.
Es war also nicht die eigene Identität, kein anderer kann das
festgestellt haben.
Und derjenige, bei dem X gleich Idee ist, das war bei der 1 der Fall,
der wartet nur darauf, dass er eine Nachricht bekommt.
Er kann nur eine Nachricht bekommen, die gleich der Minus 1 ist, dann
ist er fertig.
Was ich hier nicht drin stehen habe, ist, dass natürlich jeder im
Anschluss sofort sagen kann, ich habe hier diese Nachricht X bekommen.
Und der Betrag von X ist die Nummer des Anführers.
Dadurch, dass ich einen negativen Wert bekommen habe, weiß ich, der
Absolutwert dieses Wertes X ist die Nummer des Anführers.
Jetzt wissen wir, wer der Anführer ist.
Wie groß ist der Aufwand?
Wenn Sie Pech haben, wie groß der Aufwand ist, ist die Anzahl der
Nachrichten.
Jede Nachricht hat log N Bits, das ist also nicht weiter schlimm.
Aber immerhin log N, wir haben ja N verschiedene Noten drin, die
müssen mindestens N verschiedene Identitäten haben.
Also Größenordnung log N pro Nachricht.
Und ich kann auch sagen, die Nachricht hat eine feste Größe, aber es
wird mindestens log N sein.
Wenn ich Pech habe, wenn die Pech ungünstig angeordnet sind, bekommen
die immer Nachrichten, die...
wie ist denn das, wenn ich eine Nachricht bekommen habe, die ist
kleiner, dann schicke ich die Nachricht weiter.
Wenn also jeder, der eine Nachricht bekommt, eine von einem kleineren
bekommt, dann habe ich nicht die Situation, die ich hier gezeigt habe,
dass sehr schnell nur noch wenige Nachrichten verschickt wurden,
sondern es werden fast von allen Prozessoren in jedem Schritt einer
weniger Nachrichten verschickt.
Es dauert also lange, bis die Anzahl der Nachrichten letztendlich
abnimmt.
Wenn ich Pech habe, komme ich auf Größenordnung N Quadratnachrichten.
Also wir hatten hier zu Anfang N Nachrichten, jeder verschickt seine
Identität.
Und bei all denen, bei denen die Nachricht kleiner war, wurde eine
Nachricht weitergeschickt.
Und die anderen haben die Nachricht einfach verfluckt.
Das ist dann nicht weitergegangen.
Größere Nachrichten brauche ich nicht weiterzuschicken, weil größere
Nachrichten nichts beitragen können zur Auswahl des Anführers.
Also im schlechtesten Fall O von N Quadratnachrichten.
Im besten Fall, das war hier der Fakt, das war hier angedeutet, da
hatte ich also nur sehr wenige Nachrichten, die übrig bleiben.
Wenn alle verschickten Nachrichten größer sind als die eigene
Nachricht oder als die eigene Identität, dann verschwinden fast alle
Nachrichten nach dem ersten Schritt.
Und ich habe im besten Fall insgesamt drei N-1 Nachrichten, die
verschickt werden müssen.
Das heißt, wieder diese Spanne von linear bis auf N Quadrat.
Und es zeigt auch, dass die Auswahl seines Anführers gar nicht so sehr
einfach ist.
Jetzt werden wir uns diesen Algorithmus anschauen und werden sehen, ob
man den hier steht, verbesserbar auf O von N Log N.
Ich kann sogar den Aufwand auf linearen Aufwand runterdrücken.
Das werden Sie nachher noch sehen.
Nicht heute, das schaffen wir heute nicht mehr.
Das wird eine ziemlich aufwendige Überlegung.
Aber das ist das Interessante, ich kann dieses Verfahren so weit
verändern, dass ich am Ende tatsächlich auf lineare Komplexität komme,
linearen Aufwand in der Anzahl der Bits, um insgesamt den Anführer zu
wählen.
Von N Quadrat runter.
Das ist schon erstaunlich.
Und das ist im Prinzip immer dieser eine Algorithmus, den wir uns
anschauen.
Das Einzige, was wir machen können, ist modifizieren, welche
Nachrichten wir verschicken und wann wir Nachrichten verschicken.
Das sind jetzt die Überlegungen, die hier kommen.
Zunächst mal eine andere Variante.
Ich überlege mir, das Ganze muss ja nicht deterministisch ablaufen.
Ich könnte ja auch einen stochastischen Algorithmus nehmen.
Also, die Annahmen sind, das haben Italien und Rode hier gemacht,
1981, nachdem klar war, deterministisch, vollständig verteilt geht es
nicht.
Probabilistisch kann ich es machen.
Ähnlich wie bei Philosophen-Problemen.
Ich nehme also an, alle Prozesse sind identisch.
Jeder Prozess kennt die Gesamtzahl aller beteiligten Prozesse.
Ich weiß, ich habe 357 Prozesse insgesamt in dem Ring.
Also wir haben nach wie vor einen Ring von Prozessoren.
Und jeder Prozess des verteilten Algorithmus ist in der Lage,
unabhängig von den anderen eine Zufallszahl zu bestimmen.
Ich nehme auch an, dass die Reihenfolge der Nachrichten im Ring
erhalten bleibt.
Das heißt, die Nachrichten werden in genau der Reihenfolge erhalten,
wie sie verschickt wurden.
Typische Annahmen, die dürfen sich nicht überholen unterwegs.
Was ich, wenn ich kommuniziere, über ein beliebiges
Kommunikationsmedium nicht weiß, kann ich nicht garantieren.
Im Internet kann ich das nicht garantieren.
Wenn Sie zwei E-Mails verschicken, kommen die nicht notwendigerweise
in der gleichen Reihenfolge an, wie sie verschickt wurden.
Wenn die eine größer ist, kann die größere länger brauchen.
Und dann verwende ich diesen Algorithmus.
Ich habe zwei Variablen, Name und Anführer.
Und das sind Zahlen aus einem Bereich 1 bis K.
Und K kann irgendeine Zahl sein.
Nehmen wir mal an, die ist ziemlich groß.
Größer als N.
Und wir haben eine Liste S, das ist eine Liste von Werten aus diesem
Bereich 1 bis K.
Also eine Liste von Namen.
Zu Anfang ist diese Liste leer.
Ich fange also mit einer leeren Liste an.
Ich mache die auf.
Da steht irgendwas da drin.
Jetzt wählt jeder Prozess zufällig eine Zahl zwischen 1 und K.
Wir haben hier also unsere Prozessoren.
Ich male die mal einfach hier rein.
Das sind meinetwegen unsere Prozessoren.
Der wählt hier meinetwegen 17.
Der wählt 21.
Der wählt 6.
Der wählt 8.
Der wählt 2.
Und der wählt meinetwegen 9.
So.
Irgendwie angeordnet.
Jeder wählt zufällig irgendeinen Wert.
Jetzt wiederhole ich N mal.
Ich weiß, ich habe N Prozesse damit.
Ich trage den Namen ein in die Liste S.
Jeder macht das gleichzeitig.
Das heißt, jeder fängt an, lokal eine Liste zu führen.
Und trägt seinen eigenen Namen ein.
Gucken wir uns mal hier diesen Prozess an.
Der trägt also zu Anfang 17 ein.
Nehmen wir mal an, die sind in dieser Reihenfolge miteinander
verbunden.
Der trägt die 17 ein.
Und dann schickt er seinen Namen an den Nachfolger.
Der schickt also das an den Nächsten und bekommt von seinem Vorgänger
die 8.
Jetzt ist also, weil er jetzt den Wert für Name vom Vorgänger bekommt,
hat der Wert Name oder hat die Variable Name jetzt den Wert 8.
Auch das trägt er wieder ein.
Trägt also hier 8 ein.
Als nächstes kommt die 2 bei ihm an.
Dann kommt die 9 bei ihm an.
Dann kommt die 6 bei ihm an.
Dann kommt die 23 an.
Und dann kommt die 17 an.
Ähm...
So.
Das war aber, ich mach's ja nur einmal.
Die 17, die wird nicht mehr eingetragen.
Er hat also als letztes die 17 bekommen, aber die trägt er nicht mehr
ein.
Die hat er ja schon eingetragen.
Das ist so ein bisschen auch überprüfen.
Es muss am Ende der Wert, der empfangen wurde, der Wert von Name,
wieder der eigene Name sein.
Kann man also überprüfen, ob ich tatsächlich nach hier so und soviel
mal, nach innen mal, tatsächlich rum bin.
Und was man sich jetzt überlegt natürlich ist, jetzt ist ja in jedem
Knoten eine Liste entstanden.
Mit Namen.
Die sieht überall ein bisschen anders aus.
Die ist bei jedem zyklisch verschoben.
Entsprechend der Position im Ring.
Also hier fängt es mit 6 an.
Ja, da steht also 6, 23, 17, 8, 2, 9.
Ich hab also überall zyklisch verschobene Listen.
Aber die Einträge in der Liste sind bei allen gleich.
Und jetzt kann ich natürlich überprüfen, ob mindestens eine Name nur
einmal vorhanden ist.
Das sind ja alles Zufallswerte gewesen.
Wir haben ja eine zufällige Auswahl von Zahlen zwischen 1 und K.
Da werden einige Konflikte bei sein.
Und wir wissen das, Geburtstagsparadoxon, selbst wenn sie eine große
Zahl K haben und sie wählen dort jetzt N verschiedene Werte aus, da
werden einige den gleichen Wert haben.
Es reicht aber, wenn mindestens ein Name nur einmal auftaucht.
Das können alle überprüfen.
Ob es einen Namen dabei gibt, der nur einmal auftaucht.
Und dann nehme ich hier in dem Fall den maximalen eindeutigen Namen in
der Liste und sage, das ist der Anführer.
Ich könnte auch den Minimalen nehmen, ist völlig egal, welchen ich
nehme.
Das ist die Entscheidung, die wird von allen so ausgeführt.
Dieser Algorithmus wird von allen durchgeführt.
Das einzige, was sie unterschiedlich machen, ist, dass sie
unterschiedliche Werte erzeugen durch ihre Zufallszahlen-Generatoren.
Natürlich geht das nur, wenn das keine, also das können Pseudo
-Zufallszahlen -Generatoren sein, aber wenn sie alle das gleiche tun
würden, müssten sie alle mit dem gleichen Startwert anfangen, mit dem
gleichen Seed reinstecken in den Pseudo-Zufallszahlen-Generator, wenn
das ein vollständig verteilter Algorithmus wäre.
Also ein Algorithmus mit einem Pseudo-Zufallszahlen-Generator, der
vollständig verteilt und symmetrisch ist, würde bei allen den gleichen
Zufallswert erzeugen.
Das ist ja deterministisch.
Ich brauche deswegen wirklich unabhängige Zufallszahlen-Generatoren.
Ich muss dafür sorgen, dass die unterschiedlichen Werte tatsächlich
auswählen können.
Also es muss wirklich zufällig sein, was hier passiert.
Und wenn man Pech gehabt hat, jeder Name taucht mindestens doppelt
auf, dann mache ich das Ganze nochmal.
Und die Wahrscheinlichkeit dafür, dass irgendwann mindestens ein Name
nur einmal auftritt, wird schon groß genug sein, hängt natürlich davon
ab, welchen Wert ich für das K gewählt habe.
Das heißt, ich habe auf die Art und Weise von keinem Prozess die
Identität ausgenutzt, abgesehen davon, dass sie zufällig etwas gewählt
haben, weil jeder gleichmäßig beteiligt war.
Das heißt, diese Anforderung, alle sind gleichberechtigt, die ist
schon wirklich recht gut erfüllt.
Es sei denn, jemand manipuliert den Zufallszahlen-Generator und sorgt
dafür, dass ein bestimmter jetzt dann ausgewählt wird.
Aber das sind, nehmen wir an, unabhängige Zufallszahlen-Generatoren.
Dann ist das ein Verfahren, das eben randomisiert ist durch den
Zufallszahlen -Generator, aber auf die Art und Weise tatsächlich in
der Lage ist, so einen Namen zu wählen.
Allerdings brauchte ich die Eigenschaft, dass ich weiß, wie viele
Prozessoren drin sind in dem Ring.
Das brauchte der andere nicht zu wissen.
Das lief unabhängig von der Kenntnis, wie viele Prozesse im Ring drin
sind.
Hier muss ich das wissen.
Also das ist die Annahme gewesen.
Gut, das ist auf dieser Seite alles erläutert.
Das ist genau nochmal dieses Verfahren.
Alle Prozesse sind gleicherweise beteiligt, haben die gleiche Chance,
gewählt zu werden.
Alle Prozesse ermitteln, also vollständig verteilt und symmetrisch,
stimmt eben nur bis auf die Tatsache, dass sie in der Lage sind,
unterschiedliche Zufallszahlen zu erzeugen.
Und sie ermitteln natürlich am Ende alle den gleichen Namen als
Anführer, da am Ende jeder die gleiche lokale Liste hat, bezüglichen
Vertauschungen.
Und da jeder Prozess am Ende wieder seinen eigenen Namen empfängt, den
er vergessen hatte in dem Augenblick, wo er ihn rausgeschickt hat,
nach diesem Verfahren, kann er am Ende überprüfen, ob sein eigener
Name der gewählt ist.
Auch das ist hier also möglich.
Jeder Prozess kann sofort feststellen, ob er der Anführer ist.
Und alle anderen wissen, wer der Anführer ist.
Beziehungsweise sie können also jetzt Ideen unter dem Namen
ansprechen.
Der ist eindeutig.
Terminierung hängt davon ab, wie wahrscheinlich es ist, dass die
tatsächlich solche Namen finden, die eindeutig sind.
Pro Runde habe ich eine gewisse Wahrscheinlichkeit, dass mindestens
ein Prozess einen eindeutigen Namen wählt.
Hängt davon ab, was für Zuwachszahlengeneratoren gewählt werden, wie
groß das K ist und das N.
Die Wahrscheinlichkeit, dass ich nach I Runden nicht fertig bin, ist
also 1-POI.
Die Wahrscheinlichkeit, dass ich nach I Runden fertig bin, also nach I
Runden, also in der I plus ersten Runde, heißt, ich habe I mal keinen
Erfolg gehabt und dann bin ich tatsächlich fertig.
Also 1-POI.
Und das heißt, wenn ich das I hoch genug treibe, wenn ich genügend
Runden mache, dann geht die Wahrscheinlichkeit hier gegen 0, dass ich
nicht terminiere, beziehungsweise die Wahrscheinlichkeit, dass ich
terminiere, geht gegen 1.
Damit habe ich also hier ein sicheres Verfahren.
Das wird irgendwann terminieren und ich habe dann den Anführer.
Ich weiß zwar nicht, wie lange das dauert, aber ich habe eben meinen
typischen formalistischen Algorithmus, der dafür sorgt, dass das
gewünschte Problem tatsächlich gelöst wird mit dem Ergebnis, dass
jeder die gleiche Chance hat.
Die Nachrichten, die verschickt werden, hier wird keine Nachricht
irgendwo verschluckt.
Das heißt, die laufen wirklich alle rum.
Jeder muss die Liste aufbauen.
Jeder braucht N Nachrichten, das heißt, insgesamt habe ich N Quadrat
Nachrichten pro Wahlvorgang.
Der Aufwand ist relativ hoch, aber dafür eben vollständig verteilt und
symmetrisch.
Wenn ich jetzt die Zahl der beteiligten Prozesse nicht kenne, wie kann
ich das dann auch hinkriegen?
Nach dem Verfahren kann ich nicht feststellen, wann alle zufällig
gewählten Namen erhalten wurden.
Es könnte ja sein, dass der eigene Name doppelt...
Normalerweise würde man sagen, wenn mein Name wieder auftaucht, dann
bin ich fertig.
Es könnte aber sein, dass der Name doppelt auftaucht.
Dann bekomme ich den Namen schon wieder zurück.
Ich bin aber noch nicht ganz durch.
Das kann ich mir aber nicht feststellen.
Also in dem Augenblick, wo ich mehrfach Namen habe, kann ich nicht
entscheiden, wann eine Runde beendet ist.
Nicht sicher entscheiden.
Jetzt nehmen wir aber mal an, jeder Prozess bzw.
Prozessoren haben eindeutige Namen.
Die sind durchnummeriert.
Eindeutig.
Ich darf aber diese Eigenschaft, dass sie durchnummeriert sind, nicht
verwenden für die Auswahl meines Algorithmus.
Ich kann die aber vielleicht diese Eigenschaft nutzen, um
Terminierungen festzustellen.
Das können Sie sich einfach überlegen.
Das geht also wirklich relativ einfach.
Und das habe ich als Übungsaufgabe angegeben.
Können Sie in den Übungen darüber diskutieren oder sich zu Hause kurz
überlegen.
Ist eine ganz einfache Idee, wie man das macht.
Also die Identität verwenden, um festzustellen, wann man fertig ist.
Und ansonsten bleibt alles gleich.
Und damit bin ich für heute am Ende.
Nächstes Mal gucken wir uns an, wie man die Anzahl der Nachrichten
bzw.
den Kommunikationsaufwand insgesamt einschränken kann.
Bei dem Algorithmus, den ich Ihnen als erstes vorgestellt habe für die
Auswahl eines Leiters.
Das machen wir aber nächste Woche.
Dann wieder zur normalen Zeit, wieder im anderen Raum.
Vielen Dank für die Aufmerksamkeit.