So, schönen guten Tag.
Ich begrüße Sie zur Vorlesung, zur letzten Vorlesung über effiziente
Algorithmen diesen Semester.
Wir waren beim Thema verteilte Algorithmen.
Kurze Vorbemerkung, es war so, dass ich letztes Mal ja zu Beginn
bemerkte, ich habe Probleme mit der Aufzeichnung, habe dann nochmal
neu gestartet, habe das Mikrofon richtig, dachte ich, installiert und
das war alles richtig eingestellt und dummerweise hat er dann leider
keinen Ton aufgenommen.
Da war nur ein Rauschen drin in der Aufzeichnung und deswegen mussten
wir dann leider wieder den Ton von der Vorlesung vom vorigen Jahr dazu
schnipseln.
Das hat dann Herr Braun erledigt, aber das geht ja einigermaßen.
Zum Glück habe ich ja die Aufzeichnung vom vorigen Jahr.
Heute wird es hoffentlich dann vernünftig ablaufen, dass es richtig
aufgezeichnet wird.
Zur Klausur, die ist, das wissen Sie, die ist nächste Woche.
Ich bin mir gar nicht sicher, wann die Klausur ist, welche Uhrzeit.
Könnte ich noch nachgucken, Sie wissen das wahrscheinlich.
Mittwochs um zwei.
Und im Audimax nehme ich an, oder?
Jetzt, ok.
Also, ich denke, das wissen Sie, die Informationen sind ja raus und
dann gibt es hoffentlich auch keine Probleme mit gleichzeitig
laufenden Lehrveranstaltungen.
Jetzt muss ich hier noch kurz mein Netzteil anschließen und dann sind
wir hoffentlich gleich so weit.
So, damit sind wir so weit und ich kann anfangen.
Also, wir haben uns letztes Mal angeguckt, verteilte Algorithmen.
Wir waren bei Konsensproblemen, Leader Election, das hatten ja einige
Dinge uns hier angeguckt gehabt.
Das Problem war, wenn wir einen völlig symmetrischen verteilten
Algorithmus nehmen, vollständig verteilt, symmetrisch,
deterministisch, dann war das so, dass man Konsens eigentlich nicht
herstellen kann.
Dazu muss man halt irgendwie sich unterscheiden, unterscheidende
Merkmale haben, um Entscheidungen treffen zu können.
Das eine war, dass man die Identität einfach ausnutzt.
Die andere Idee war, dass man einfach zufällig sich Werte erzeugt,
natürlich mit unabhängigen Zuweisszahlengeneratoren und auf die Art
und Weise dann eine Entscheidung treffen kann für die Bestimmung eines
Anführers.
Und dann haben wir anschließend überlegt, wie man die Anzahl der
auszutauschenden Nachrichten reduzieren kann und hatten dann eine
Reihe von Überlegungen gemacht.
Das eine war, das war die einfachste Art, dass man immer mit dem
Minimum vergleicht und nicht mit der eigenen Identität und dadurch das
etwas reduziert.
Die andere Sache war, dass man die Nachrichten verzögert um eine
gewisse Anzahl, abhängig von dem Wert der Identität, wenn man eine
entsprechende Identität wählen möchte und der kleinste gewinnen soll,
dann macht es Sinn, die Nachrichten mit der kleinsten Information
schnell zu schicken und die anderen langsam, sodass dadurch dann eben,
das hatten wir hier auf der Folie gesehen, dann eben die Anzahl der
Nachrichten, die insgesamt verschickt werden, klein wird, weil die
Nachrichten, die sowieso keine Chance haben, halt auch nur sehr selten
oder sehr, sehr spät verschickt werden.
Das war diese etwas längere Überlegung hier, bis ich dann auf die Idee
kam, dass ja das I immer größer ist als das M und dass es also eine
einfache Summe ist von negativen Zweierpotenzen, die man natürlich
durch zwei abschätzen kann und dann hat man sofort, dass das insgesamt
eine lineare Anzahl von Nachrichten war.
Da hatte ich etwas länger gebraucht für diese Folie letztes Mal, was
aber in der Aufzeichnung nicht zu sehen ist, weil ich in der
Aufzeichnung das halt einfach, das ist halt vom vorigen Mal, aber das
ist auch egal.
Dann war die dritte Verbesserung, das hat auch wieder was damit zu
tun, dass man das Zeitverhalten verändert.
Die dritte Verbesserung war, dass man sagt, ich messe einfach die
Anzahl der Runden, die ich brauche, um eine Information zu verschicken
und die Idee war, dass ich eine Beginn- und eine Endnachricht oder
eine Open- und Close-Nachricht verschicke und einfach zähle, wie viele
Runden es dauert, bis die Close-Nachricht gekommen ist und dadurch
habe ich dann den Wert, der verschickt werden soll, auch mitgeteilt.
Das war also hier eben x plus 1 Runden für die Übertragung des Wertes
x.
Damit habe ich dann die Möglichkeit mit sehr wenig Inhalt in den
Nachrichten trotzdem Informationen weiterzugeben.
Und das ist schon interessant, dass man eben sagt, die Information
steckt nicht in der Nachricht, sondern in dem zeitlichen Ablauf dieses
Verfahrens.
Und das sind einfach so Dinge, die man sich überlegen muss, wie kann
man kommunizieren, nicht nur dadurch, dass man direkt Informationen
verschickt, sondern auch dadurch, dass man sich voreinigt auf gewisse
Zeitabläufe und dann durch den Zeitablauf auf einmal feststellt,
welche Informationen eigentlich verschickt werden sollten.
Also das war dann diese Idee und dadurch kamen wir dann insgesamt auf
ein Zeitverhalten, das natürlich linear, also die Anzahl der
Nachrichten linear, aber eben auch die Anzahl der Witz tatsächlich
linear.
Das heißt, man kann in einem synchronen Ring tatsächlich mit linearem
Aufwand, das war hier oben angedeutet, oder nicht nur angedeutet,
sondern in grün hervorgehoben, mit Nachrichtenaufwand, der linear ist
in der Anzahl der beteiligten Knoten, einen Anführer wählen und damit
eben diesen Aufwand deutlich reduzieren.
Wobei man natürlich den Aufwand hat für die Synchronisierung der
Knoten, wo das kann sein, dass man das sowieso diesen Aufwand hat und
dann ist es eben relativ einfach zu machen.
Das Ganze kann man natürlich dann noch weiter vertiefen.
Man kann sich angucken, wie man vorgeht, wenn man Fehler hat in
solchen Systemen und ähnliches.
Darauf gehe ich aber nicht weiter ein.
Und das, was wir heute genauer angucken werden, ist eine untere
Schranke für die Wahl eines Anführers in asynchronen Ringen.
Und da waren wir letztes Mal an dieser Folie stehen geblieben und da
fange ich jetzt nochmal wieder mit an.
Die untere Schranke für die Leader Election in Ringen.
Die Annahmen sind, dass wir also den mit der kleinsten Identität
wählen wollen und dass wir einen asynchronen Ring haben, der natürlich
gerichtet ist.
Die Prozesse kennen nicht die Größe des Ringes, sie wissen nur, dass
sie in einem Ring sind.
Sie kennen ihren Vorgänger und ihren Nachfolger.
Die Reihenfolge der Nachrichten bleibt erhalten.
Das ist wichtig und ich habe in jeder Nachricht höchstens eine
konstante Anzahl von Prozessnummern bzw.
von Log N Bits.
Und das nächste ist noch, dass eben die Prozessore im Prinzip alle
Initiatoren sein können.
Jeder kann feststellen, wir brauchen einen neuen Anführer und dann
wird halt einfach einer das anstoßen.
Und jetzt ist die Frage, wie viel Informationen müssen verschickt
werden oder wie viele Nachrichten müssen verschickt werden im
schlechtesten Fall und im Mittel mindestens.
Und da muss man sich halt überlegen, wodurch wird die Anzahl der
Nachrichten beeinflusst.
Irgendwann wird das gestartet.
Das ist die Anfangskonfiguration, die wir haben.
Das ist also die Anfangskonfiguration für unseren Ring.
Und abhängig von der Anfangskonfiguration werden die ersten
Nachrichten verschickt.
Und dann werden Nachrichten durch den Ring weitergegeben.
Und jede Nachricht, die verschickt wird, ist beeinflusst durch
Nachrichten, die man bekommen hat.
Und diese Beeinflussung einer Nachricht, die verschickt wird durch
Nachrichten, die man vorher bekommen hat, wird aufgeführt in einer
Spur.
Das heißt, man merkt sich die Anzahl oder den Namen der Knoten, durch
die eine Nachricht bereits durchgelaufen ist.
Und diese Spuren werden mit jedem Verschicken halt entsprechend
länger.
Und wenn ich mir die Menge dieser Spuren angucke, die ich mindestens
in solchen Algorithmen habe für Leader Election, dann habe ich im
Prinzip genau die Anzahl der Nachrichten.
Also wenn ich die Längen der Spuren, die während eines Leader Election
Algorithmus versandt werden, alle aufsummiere, dann habe ich genau die
Anzahl der Nachrichten, die verschickt wurden während dieses Leader
Election Vorgangs.
Und deswegen ist die Idee, dass man eine untere Schranke findet,
dadurch, dass man die Eigenschaften der Menge aller möglichen Spuren
betrachtet.
Und das muss man sich jetzt ein bisschen genauer angucken.
Da gibt es eine Reihe Definitionen, die ein bisschen aufwendig sind.
Also es wäre gut, wenn Sie das schon mal vor sich angeguckt haben,
weil das etwas schwierig ist, das wirklich mitzubekommen.
Ich versuche das gut zu erklären, aber es ist nicht immer einfach.
Lassen Sie mich das hier trotzdem schon ganz zeigen.
Also, das erste ist, wir betrachten eine Menge D.
Das ist die Menge aller Folgen von Prozessnummern ohne Wiederholungen.
Alle Folgen von Prozessnummern ohne Wiederholungen.
Sie müssen sich überlegen, wir haben einen Ring.
Nachrichten laufen durch diesen Ring durch.
Und diese Nachrichten laufen maximal einmal rum.
Das heißt, es werden in den Spuren, die hier bei den Nachrichten
auftauchen, die immer länger werden, werden keine Wiederholungen von
Knotennamen auftauchen.
Die laufen ja hier nur rum.
Es kann sein, dass sie hier irgendwie ein gewisses Stück rumlaufen und
dann vielleicht gar nicht weitergeschickt werden, wo man feststellt,
die Nummer, die da verschickt wird, wird nicht der Anführer sein.
Ich werde da nichts weiter rausschicken.
Kann ja auch passieren.
Also es werden maximal die Länge N sein.
Also Prozessnummern ohne Wiederholungen.
Alle Folgen.
Beliebige Länge.
Und diese Prozessnummern sind jetzt diese SI in dem Fall.
Und jetzt betrachtet man eine Menge CS.
Das sind die zyklischen Verschiebungen.
Also CS von S.
S ist irgend so eine Spur.
Und jetzt betrachtet man die Menge aller zyklischen Verschiebungen von
S.
Also die Reihenfolge der einzelnen Identitäten ist da völlig egal.
Ich muss ja für beliebige Anordnungen meiner Identitäten Aussagen zur
minimalen Anzahl von Nachrichten machen können.
Das heißt, wir haben jetzt hier irgend so eine Spur.
Das ist eine Folge von Prozessnummern.
Und jetzt betrachte ich einfach alle zyklischen Verschiebungen.
Das heißt, ich mache daraus einen Ring.
Und jetzt betrachte ich im Prinzip beliebige Schnittpunkte.
Hier habt ihr praktisch immer zyklische Verschiebungen dieser Spur.
Das heißt, das ist eine Menge von Spuren oder von Folgen von
Prozessnummern, die aus dem S entstanden sind, dadurch dass ich hier
eben einen Teil S' nach vorne geschoben habe.
Dann habe ich also genau eine zyklische Verschiebung dessen, was ich
vorher gemacht habe.
Und dann brauchen wir noch eine weitere Menge.
Das ist eine Menge E aus der Menge aller dieser Folgen von
Prozessnummern.
Die nennen wir erschöpfend.
Das heißt, die ist in einem gewissen Sinne eine vollständige
Information, die man braucht.
Wenn sie Präfix abgeschlossen ist, das heißt, mit jeder Folge von
Nummern ist auch jeder Präfix da mit drin.
Und das ist natürlich klar, wenn ich eine Spur betrachte, das ist ja
immer der Hintergrund einer bestimmten Länge, dann muss natürlich
jedes Anfangsstück auch eine Spur gewesen sein.
Weil sie ja in der Länge nur entstanden sein kann dadurch, dass vorher
Nachrichten verschickt wurden.
Und das heißt, sie haben sukzessive das aufgebaut von dem ersten
Eintrag an.
Also das müsste Präfix abgeschlossen sein.
Also wenn hier ein T, da ein T und das hier ein U ist, dann ist halt
das T auch aus E.
Und das andere ist, dass das diese Menge D zyklisch überdeckt.
Das heißt, in der Menge E sind nicht alle Mengen von Prozessnummern
ohne Wiederholungen drin, sondern es sind gerade solche drin, sodass
ich durch zyklische Verschiebungen dieser Spuren aus E das D
vollständig bekomme.
Das heißt, wenn ich irgendeine Spur mir hernehme oder irgendeine Folge
von Prozessnummern und betrachte alle zyklischen Verschiebungen von S,
von dieser Folge von Prozessnummern oder von Identitäten, dann ist
mindestens eine dieser zyklischen Verschiebungen in der Menge E drin.
Das heißt, ich kann durch zyklische Verschiebungen der Elemente von E
alle Mengen aus D bekommen.
So, und jetzt kommt eben nochmal die Definition, die wir vorher
eigentlich schon gemacht haben.
Wir haben eine Nachricht von Prozess P und die Spur ist halt definiert
so, dass diese Spur gerade die Nummer von P ist oder der Name von P.
Falls P noch keine Nachricht erhalten hat, dann wäre P ein Initiator
mit dieser Nachricht.
Oder es wird an die Spur, die die Nachricht M, die zuletzt erhaltene
Nachricht hatte, einfach das P noch dran gehängt.
Dann haben wir da das SP.
Und wenn also eine Nachricht eine gewisse Spur hat, dann ist das eine
S -Nachricht.
Das heißt, das, was hier an so einer Nachricht dran hängt als Spur,
dann sagen wir, das ist eine S-Nachricht.
Das heißt, das ist eine Nachricht, die von all den Prozessen innerhalb
dieser Spur beeinflusst wurde.
Und wenn wir uns diesen Ring insgesamt angucken, dann haben wir
natürlich eine Folge aller Prozessnummern im Ring, in dieser
Reihenfolge.
Und einen solchen Ring nennen wir dann einen S-Ring.
Wir haben also für jede Zuordnung von Identitäten in einem Ring einen
entsprechenden S-Ring, der die Reihenfolge betrachtet.
Und natürlich ist es so, dass wir hier irgendeinen Prozess als
Anfangsprozess nehmen.
Und alle zyklischen Verschiebungen von S charakterisieren natürlich
den gleichen Ring.
Wenn das die Folge der Prozessnummern ist, dann ist das ein S-Ring.
Und alle zyklischen Verschiebungen von S sind natürlich auch
entsprechend Charakterisierung dieses Rings.
Jetzt haben wir noch ein paar weitere Definitionen.
P von S und E, da geht es um Präfixe.
Also wir haben S, das ist eine Spur oder eine Folge von
Prozessnummern.
Und E, irgendeine Teilmenge von D.
Dann ist dieses P von S und E die Menge aller Elemente von E, sodass T
ein Präfix ist einer zyklischen Verschiebung von S.
So, wir haben hier also irgendeinen Ring.
Wir haben also eine Spur, das hier sei jetzt ein S-Ring.
Wir haben eine Menge E.
Und da sind irgendwelche Elemente drin.
Das sind diese T-Elemente, das ist hier unsere Menge E.
Und wir haben irgendeinen T aus E.
Wenn das Präfix einer zyklischen Verschiebung von S ist, dann heißt
das, wenn wir uns dieses Stück hier angucken zum Beispiel, dann taucht
das irgendwo dort auf.
Wenn das hier T ist, dann taucht dieses T dort auf, in diesem Ring, an
irgendeiner Stelle.
Das ist also irgendein Teil von dieser Folge S.
Und es ist ein Präfix einer zyklischen Verschiebung.
Ich könnte ja diesen Ring auch dadurch charakterisieren, dass ich
sage, das hier ist der Start meines Ringes.
Ich gehe dort so rum, das wäre eine zyklische Verschiebung.
Jetzt habe ich also ein Präfix, also alle in diesem P von SE, die
Menge aller Elemente von E, die Präfixe einer zyklischen Verschiebung
von S sind.
Und jetzt wird das noch etwas mehr eingeschränkt.
Jetzt betrachten wir nur diejenigen, bei denen die Länge gleich K ist.
Also nur solche Spuren der Länge K aus E, die Präfixe einer zyklischen
Verschiebung von S sind.
Jetzt haben wir ziemlich viel Formalismus.
Und darüber müssen wir dann kommen auf diese untere Schranke NlogN,
dass also insgesamt mindestens NlogN Nachrichten verschickt werden
müssen, im Mittel- und im schlechtesten Fall.
Und das EA, also für einen beliebigen Leader Election Algorithmus, ist
jetzt das EA, die Menge aller Folgen S, für die bei Ausführung von A
auf einem S-Ring eine S-Nachricht versandt wird.
Also, das heißt, ich habe einen S-Ring, das heißt, nochmal ein Ring,
irgendwo geht das los, von da an startet das Ding.
Jetzt hätte ich also hier einen S-Ring.
Und es wird der Algorithmus A auf diesem Ring ausgeführt.
Das ist ein Leader Election Algorithmus.
Und wir sagen, es wird auf diesem S-Ring eine S-Nachricht versandt.
Das heißt, es muss eine Nachricht geben, die einmal ganz rumgelaufen
ist.
Und wir wissen, welche Nachrichten das sind.
Und ganz rumlaufen kann eigentlich nur eine Nachricht, die sich
bezieht auf den minimalen Knoten.
Deswegen ist das hier relevant, sich anzugucken, welches sind die
Folgen oder die Ringe, bei denen eine Nachricht ganz rumgeschickt
wird.
Denn das ist im Prinzip, das wissen wir ja von dem Algorithmus, das
ist dann eigentlich der Prozess, der gerade zum Anführer gewählt wird.
Weil nur zu ihm die Nachricht einmal ganz rumgelaufen sein kann.
Alle anderen Nachrichten, die werden nicht weiterlaufen.
Also es muss mindestens eine solche S-Nachricht dort verschickt
werden, dann ist das hier der Anführer.
So, und jetzt haben wir hier ein Lemma.
Hier habe ich ein Bild.
Also erstmal, was steht in diesem Lemma drin?
Wir haben S, T und U, Folgen von Prozessnummern.
Und S ist ein Teilwort von T und von U.
Also S taucht dort auf und taucht auch hier auf, in beiden Spuren T
und U.
Und wenn jetzt bei Ausführung des Algorithmus A, also beliebiger
Algorithmus, auf einem T-Ring, das hier ist ein T-Ring, eine S
-Nachricht verschickt wird,
dann wird auch bei Ausführung von A auf einem U-Ring, das ist der U
-Ring hier oben, eine S-Nachricht verschickt.
Also warum wird hier eine S-Nachricht verschickt?
Weil der Prozess angefangen hat, ohne dass er eine Nachricht bekommen
hatte, eine Nachricht rauszuschicken und die ist dann so weit
gelaufen.
Das heißt, dass der hier angefangen hat, war unabhängig davon, was
davor gewesen ist.
Und die Nachricht war nicht beeinflusst, weil es eine S-Nachricht ist,
war sie nicht beeinflusst durch irgendwelche anderen Nachrichten.
Dann wird die aber, diese S-Nachricht wird auch auf dem U-Ring
verschickt werden, weil das ja unabhängig davon ist, was vorher
gewesen ist.
Und das heißt, die wird genauso weit laufen.
Es werden also die gleichen Nachrichten verschickt werden.
Das heißt, dass wir eine S-Nachricht haben in einem T-Ring, ist
unabhängig davon, was außerhalb von diesem Teil S an Informationen
liegt.
Sondern das hängt nur davon ab, was in dieser S-Spur vorhanden ist.
Und das wird jetzt hier bewiesen.
Wir haben also diese S1 bis SK.
Der Versand einer S-Nachricht durch Prozess SK im T-Ring, das ist
genau das, was ich gerade gesagt habe, kann nur von den
Anfangszuständen der Prozesse S1, SK sowie von diesen verschickten
Nachrichten abhängen.
Und da diese Anfangszustände im T-Ring und im U-Ring gleich sind, wird
auch im U-Ring eine S-Nachricht verschickt.
Also die Nachrichten, die anschließend von den Prozessoren empfangen
werden, die beeinflussen nicht die Nachricht, die hier rausgeschickt
wurde von dem Prozess in dem Ring und in dem Ring.
Die anderen Prozessoren schicken natürlich gleichzeitig auch
irgendwelche Nachrichten raus, eventuell, die dann weiterlaufen.
Aber diese Nachricht, die wird dort genauso durchlaufen wie in diesem
Ring.
Also da die Anfangszustände gleich sind, ist auch alles, was auf
diesem Stück passiert, identisch in dem T-Ring und im U-Ring.
Das heißt, dass eine S-Nachricht verschickt wird, ist von dem Kontext
im Prinzip unabhängig.
Und die Behauptung ist, dieses EA ist eine erschöpfende Teilmenge von
D.
Okay, da müssen wir nochmal zurückgucken.
Was war eine erschöpfende Teilmenge?
Eine erschöpfende Teilmenge von D, das war hier auf der Folie davor.
Erschöpfende Teilmenge heißt, Präfix abgeschlossen.
Das muss ja so sein, dass alle Nachrichten, die verschickt werden,
jeder Präfix muss auch drin sein.
Weil der Präfix einer Spur auch eine Spur sein muss.
Und es ist tatsächlich jede mögliche Folge von Prozessnummern ohne
Wiederholungen in einer zyklischen Verschiebung dort mit enthalten.
Also das ist das, was hier steht.
Eine erschöpfende Teilmenge.
Präfix abgeschlossen, das ist die einfache Überlegung.
Wenn ich auf dem S-Ring eine S-Nachricht habe, muss der Algorithmus
auch für jeden Präfix von S eine T-Nachricht schicken.
Das haben wir uns schon überlegt.
Also wenn das unser Ring ist, da habe ich hier noch Bilder drauf.
Da habe ich genau das Bild.
Ich habe die Spur.
Es wird natürlich das, was zu Beginn dort gemacht wurde, muss in der
Spur S mit enthalten sein.
Das ist eigentlich nach Definition so.
Und jetzt kommt diese zyklische Überdeckung.
Ich betrachte für beliebige S, also für eine beliebige Folge von
Prozessnummern, eine Ausführung des Algorithmus A auf einem S-Ring.
Also genau das ist jetzt hier der S-Ring, der hier rumläuft.
Und mindestens ein Prozess stellt fest, wer der Leiter wird.
Das ist genau das, was ich vorher schon angedeutet habe.
Dazu muss er natürlich mindestens eine Nachricht M erhalten haben,
deren Länge gerade die Länge von S ist.
Du musst einmal rumgelaufen sein.
Und deswegen ist die Spur von M, irgendein Prozess da drin, ist dann
eine zyklische Verschiebung unserer Folge S.
Und dies ist eine der Spuren, die in der Menge aller Spuren des
Algorithmus A bei Ausführung des Algorithmus A entstehen.
Also das ist eigentlich genau das, was ich Ihnen vorher schon erzählt
habe.
Es muss mindestens eine Nachricht geben, die einmal rumgelaufen ist.
Die hat eine Spur genau der Länge dieses Ringes und ansonsten kann
kein Anführer gewählt worden sein.
Deswegen ist das eine erschöpfende Teilmenge von D.
Noch eine Überlegung.
Bei Ausführung von A auf einem S-Ring verschickt A mindestens P von S
E A Nachrichten.
Was war P von S E A?
Das waren alle Präfixe.
Gehe ich auch nochmal zurück.
E A war die Menge aller Folgen S für die weit das war das.
Und jetzt nochmal zu dem, also dieses P S E A.
Können wir nochmal kurz zurückgehen.
P S E A, das ist die Menge aller Spuren aus dieser Menge E, die Präfix
einer zyklischen Verschiebung von S sind.
Also es werden mindestens, und jetzt nochmal zurück.
Habe ich das hier richtig drin?
Genau.
Dieses P ist nicht die Menge dieser Präfixe, sondern die Anzahl der
Spuren in E, die Präfix eines solchen sind.
Das ist also nicht die Menge, sondern die Größe dieser Menge.
Und das P K von S E ist die Anzahl der Spuren der Länge K, die Präfix,
also in E die Präfixe einer zyklischen Verschiebung von S sind.
So, das ist also jetzt die Aussage, wir verschicken mindestens so
viele Nachrichten.
Also das E A ist eine erschöpfende Menge, das ist die Menge aller
Spuren, die auftreten bei Ausführung des Algorithmus A.
Und wir sagen, dass also mindestens so viele Nachrichten verschickt
werden, wie Präfixe der Spur S oder Präfixe von zyklischen
Verschiebungen der Spur S in E A enthalten sind.
Also Menge aller Folgen S, für die bei Ausführung auf dem A eine S
-Nachricht versandt wird, das war das E A und alle Präfixe davon.
Also, da das alle Nachrichten sind, also nochmal, das E A ist die
Menge aller Folgen, für die eine Nachricht versandt wird.
Wir haben jetzt einen beliebigen Algorithmus genommen, wenn wir sagen
können, diese Menge muss mindestens so und so viele Elemente
enthalten, dann haben wir eine untere Schranke für einen beliebigen
Algorithmus.
So, jetzt müssen wir das beweisen.
Wir haben also eine beliebige Spur und eine beliebige Folge D und
dieses S soll ein S-Ring sein.
Wir haben ein Präfix einer zyklischen Verschiebung R von S.
Achso, das habe ich auch noch drin.
T ist Präfix eines R aus CS von S, also wir haben unseren Ring.
Und wir haben ein T.
T ist Präfix einer zyklischen Verschiebung von S.
Nach Definition von E A sendet A auf dem T-Ring eine T-Nachricht, also
auch auf dem R-Ring.
Also R ist ja die zyklische Verschiebung, also sendet der Algorithmus
auch auf dem R-Ring eine solche T-Nachricht.
Wobei das natürlich der gleiche Ring ist, nur mit einem anderen
Prozess wird als Beginn ausgewählt.
Also dann gehen wir halt von dort los.
Von dort los wäre es ein R-Ring, von irgendeiner Stelle hier war es
ursprünglich ein S-Ring und wir haben dann jetzt einen R-Ring.
Also wird für jedes solche T mindestens eine T-Nachricht auf dem S
-Ring verschickt.
Und das heißt, die Zahl der Nachrichten ist mindestens dieses P von S
E A.
Das ist, das habe ich Ihnen eigentlich die ganze Zeit erzählt, wir
haben dort genau die Nachrichten drin, die verschickt werden.
Die mindestens verschickt werden müssen.
Und jetzt ist Idee eine endliche Menge von Prozessidentitäten, also
von Nummern, eigentlich genau das, was wir uns vorher überlegt haben.
Und die Menge aller Permutationen von Ideen, also die Menge aller
Permutationen, das heißt wir haben alle beliebigen Abbildungen, alle
beliebigen Reihenfolgen dieser Nummern.
Und das sind jetzt genau diese Reihenfolgen von Identitäten, die wir
betrachten müssen bei der Wahl des Anführers.
Und das ist eben der Satz, den wir gleich zeigen müssen, dass die
mittlere Anzahl der Nachrichten für die Leader Election auf einem
gerichteten Ring in der Größe N, Omega von N log N ist.
Und dafür nutzen wir diese Lämmertat, die wir gerade überlegt haben.
Lämmer 3 war, dass mindestens so viele Nachrichten verschickt werden.
Also, es werden für eine, also die hier steht, die mittlere Zahl der
Nachrichten, was ist die mittlere Zahl der Nachrichten bei Leader
Election auf einem Ring, bei dem die Nummern oder die Namen in der
Menge Ideen drin sind, in irgendeiner beliebigen Reihenfolge.
Es gibt in Fakultät verschiedene Reihenfolgen, in Fakultät
verschiedenen Permutationen.
Also muss ich für jede solche Permutation S, das ist ja gerade eine
solche Folge, mir ansehen, wie viele Nachrichten werden verschickt.
Das ist das P von S, E, A.
Mindestens so viele werden verschickt, das hatte Lämmer 3 gesagt.
Und dann nehme ich halt die mittlere Zahl, das ist also durch Anzahl
der Permutationen geteilt.
Das ist hier diese Summe, das P von S, E, A war ja die Anzahl aller
Spuren in E, A, die Präfix von dem S sind.
Jetzt betrachte ich das Ganze aufgeteilt auf die verschiedenen Längen
dieser Spuren.
Das war das PK von S, E, A, das waren nur alle Spuren der Länge K.
Da muss ich natürlich alle betrachten von Länge 1 bis Länge N.
Und jetzt habe ich also hier die Summe über alle Permutationen.
Und dieses P von S, E, A, die Anzahl der Nachrichten, die verschickt
werden, ist natürlich die Anzahl der Nachrichten in Länge 1, 2 und so
weiter.
Das heißt, kann ich so aufteilen.
Dann kann ich diese Summe nach draußen ziehen.
Ich habe dann Summe K gleich 1 bis N.
Jetzt habe ich hier eine Summe von Nachrichten der Länge oder von
Spuren, die Anzahl der Spuren der Länge K, die bei Ausführung des
Algorithmus A auf einem S-Ring versandt werden.
Also für jede Permutation, alle nur der Länge K.
Und das muss ich für K gleich 1 bis N machen.
Und wenn ich mir das jetzt anschaue, für ein festes K gibt es für
jedes S, für jeden Ring, den ich betrachten könnte,
ich habe einen solchen Ring S.
Jetzt gucke ich mir an, wie viele Präfixe der Länge K von zyklischen
Verschiebungen von S kann es geben.
Präfix der Länge K von zyklischen Verschiebungen.
Ich habe hier ein Präfix der Länge K, das sind jetzt hier gerade K
-Elemente.
Das kann ich natürlich einmal rumschieben.
Das sind genau N verschiedene Präfixe der Länge K von zyklischen
Verschiebungen von S.
Also ob ich da anfange oder ob ich hier anfange, jedes Mal habe ich
ein Präfix der Länge K.
Und das sind genau N verschiedene solche Präfixe.
Also habe ich insgesamt, wenn ich alle Permutationen betrachte, N
Fakultät mal N Präfixe.
Also hier habe ich für jedes S aus N verschiedene Präfixe.
Aber ich habe natürlich nicht alle, die sind natürlich nicht alle
verschieden.
Und zum Beispiel für K gleich 1, alle Präfixe der Länge 1.
Das können nur die N verschiedenen Nummern sein.
Das heißt, sie treten jeweils N Fakultät mal auf.
Und von diesen N Fakultät mal N Vorkommen von Präfixen werden in
dieser Summe alle diejenigen gezählt, die auch in dem Ea drin sind.
Das ist hier dieses Ea, die auch tatsächlich eben verschickt werden.
Und diese Menge Ea überdeckt die Menge D zyklisch.
Also enthält das Ea für jeden Präfix der Länge K, also für jeden
Präfix, der für jede Spur verschickt wurde, mindestens ein Element aus
der Menge der zyklischen Verschiebungen von dem T.
Wir hatten gesehen, das Ea ist eine zyklische Überdeckung der Menge D,
also ist dort jeweils ein solcher Präfix drin.
Und deswegen ist diese Menge, die wir hier drin haben, diese Summe K
gleich 1, das war hier nochmal die vorige Summe, das war das hier, wir
hatten uns überlegt, es tauchen die auf, das war hier diese Summe S
aus PK, für alle Permutationen von der Menge aller Prozessnummern, die
Anzahl der Spuren der Länge K, die alle aufaddiert, das waren N
Fakultät mal N durch K dividiert.
Und wenn wir uns diese Summe anschauen, können wir das N Fakultät hier
rausziehen und dann steht hier, da taucht das N Fakultät oben nochmal
auf, und dann ist das Ganze größer gleich N mal Summe 1 durch K.
Und Summe N mal Summe 1 durch K ist gerade N mal harmonische Zahl N.
Und davon wissen wir, dass das gerade in Log N liegt, dass das O von
Log N ist, das hatten wir ziemlich zu Anfang der Vorlesung, nicht zu
Anfang, aber bei der Überlegung, wie die mittlere Zahl der Vergleiche
ist bei Quicksort, da hatten wir diese Formel schon mal gehabt.
So, und damit kommen wir auf die N Log N Nachrichten.
Das ist kein einfacher Beweis gewesen, muss man sich genau überlegen,
wie die einzelnen Schritte dort sind,
aber das ist also der Nachweis, dass wir mindestens N Log N
Nachrichten brauchen, die müssen mindestens verschickt werden, und
damit haben wir dann, dass wir in einem beliebigen Ring im Mittel so
viele Nachrichten brauchen und damit auch im schlechtesten Fall.
Man kann diesen Beweis erweitern, auch für einen bidirektionalen Ring,
man kann das erweitern dafür, dass die Größe des Ringes bekannt ist,
und kann dann sogar auch die gleiche untere Schranke beweisen.
Das nur, um Ihnen zu zeigen, welche Art von Überlegungen man bei
solchen verteilten Algorithmen macht, um etwas zu zeigen über die
Anzahl der Nachrichten, die dort verschickt werden.
Wenn ich jetzt ein beliebiges Verbindungsnetz hernehme, also nicht
mehr ein Ring, sondern ein beliebiges Netz, wie sieht das denn da aus
mit der Wahl eines Anführers?
Wie kann ich das dort machen?
Jetzt ist hier die Idee, einen Echo-Algorithmus zu verwenden.
Was ist ein Echo-Algorithmus?
Der wird jetzt hier erläutert.
Ich habe also ein beliebiges System mit N-Knoten und M-Kanten,
irgendein beliebiges Verbindungsnetz.
Jeder Knoten kann im Prinzip eine Nachricht rausschicken.
Also ein beliebiges Netz, und es kann jeder Knoten eine Nachricht
rausschicken.
Und er schickt sie in der Regel an alle seine Nachbarn.
Zum Beispiel, wenn das seine Nachbarn sind.
Und der Initiator schickt eine Nachricht, da steht meinetwegen drin,
Wake Up und P, seine eigene Prozessnummer.
Und diese Nachricht wird dann weitergeschickt.
Also,
jeder Knoten, der eine Nachricht bekommen hat, schickt diese Nachricht
weiter an alle seine Nachbarn, von denen er die Nachricht nicht
bekommen hatte.
Und die schicken das wieder weiter an alle Nachbarn, von denen sie
diese Nachricht nicht bekommen hatten.
Und die auch wieder an alle ihre Nachbarn, von denen sie die nicht
bekommen hatten.
Jetzt kann es natürlich sein, dass ein Knoten eine Nachricht schon
noch einmal bekommt.
Und es kann auch sein, dass dieser die schon vorher dorthin geschickt
hatte.
Also es werden diese Nachrichten über jede Kante einmal rausgeschickt.
Und beim Echo, wenn also jetzt ein Knoten diese Nachricht schon von
allen anderen bekommen hat, dann schickt er die Nachricht...
Also, was habe ich gesagt?
Beim Echo wird jeweils die aktuell kleinste Prozessnummer
mitgeschickt.
Das heißt, die kleinste Nummer aus allen empfangenen Echos und der
eigenen Nummer.
Ein Echo wird verschickt, wenn ich also nicht mehr Nachbarn habe, die
die Nachricht noch nicht bekommen haben.
Und dann schickt man die Nachricht zurück an denjenigen, von denen man
die bekommen hat, mit seiner eigenen Nummer.
Also der hat eine Nachricht bekommen, schickt diese Nachricht als
Echonachricht zurück und schickt dabei das Minimum aus der eigenen
Nummer und die, die in der Nachricht drin steht.
Der hat die Nachricht von dem bekommen, schickt wieder das Minimum
zurück und bekommt dann hier dieser Knoten, der Initiator.
Eine Nachricht und in der Nachricht steht drin die kleinste
Prozessnummer, die auf dem Weg von dem Rand bis dorthin gewesen ist.
Und er bekommt von allen seinen Nachbarn jeweils ein Echo zurück, in
dem jetzt die kleinste Prozessnummer drin steht.
Das heißt, der Initiator, der ursprünglich die Nachrichten an seine
Nachbarn geschickt hatte, braucht dann nur das Minimum der
Prozessnummern zu nehmen, die er als Echo bekommen hat.
Und damit kann der Initiator den Leiter bestimmen.
Er bekommt also über alle Wege, über die er rausgeschickt hatte,
bekommt er jeweils die Information über die kleinste Prozessnummer,
die in dem Bereich gewesen ist, die dort gesehen wurde.
Und er kann dann über die Minimierung aller dieser Echos, über die
Minimierung der Prozessnummern in diesen ganzen Echos, kann er den
Leiter bestimmen und er kann anschließend die Nummer des Leiters
nochmal an alle anderen Prozesse rausschieben.
Weil natürlich der, der hier am sogenannten Rand des Grafen war und
der das Echo zurückgeschickt hat, der weiß natürlich nicht, welche
anderen Prozessoren dort bereits oder wie die Nummer der anderen
Prozessoren sind.
Das kann ja sein, dass der Anführer dann irgendwo hier hinten gesessen
hat und das muss eben erst hier durch den Initiator ermittelt werden
und der schickt dann die Nummer des Anführers an alle anderen.
Solche Echo-Algorithmen, also dieser Begriff Echo-Algorithmus ist ein
standardalgorithmischer Ansatz in verteilten Algorithmen, dass ein
Prozessor etwas rausschickt, im Prinzip ein Broadcast macht und die
Prozesse, die dann von allen ihren Nachbarn schon die Nachricht
bekommen hatten, die schicken dann ein Echo zurück an denjenigen, von
dem sie die Nachricht als erstes bekommen hatten.
Und dadurch habe ich dann eine Rückmeldung, die dann wieder
zurückläuft bis zu dem Initiator.
Der Aufwand in dem Fall ist 2n mal 2m, also die Anzahl der
Nachrichten.
Es ist so, es läuft eine Nachricht erstmal raus und irgendwann läuft
das Echo zurück.
Damit ein Prozess feststellt, dass er ein Echo zurückschicken soll,
hat er eine Nachricht bekommen und stellt fest, ich habe diese
Nachricht schon von allen anderen bekommen.
Wenn ich sie schon von allen anderen bekommen habe, ist also von allen
anderen schon eine Nachricht darüber gelaufen und jetzt schickt er die
Nachricht zurück an denjenigen.
Das heißt, es wird im Prinzip über jede Kante in dem Knoten oder in
dem Grafen, über jede Kante werden genau zwei Nachrichten verschickt.
Einmal bei dem Broadcast raus und einmal über die Echos zurück.
Das sind also diese 2m Nachrichten.
Und das Ganze kann von jedem Knoten auslaufen.
Das Ganze muss zweimal laufen, einmal raus, um den Leiter zu
bestimmen.
Und dann muss es an alle verschickt werden, dann habe ich 2n mal 2m
Nachrichten, weil eben jeder Knoten potenzieller Initiator sein kann.
Wenn man das ein bisschen verbessern will, also hier war die Annahme,
es ist so, dass jeder das machen kann.
Wenn ich das ein bisschen verbessern will, dann bekomme ich zum
Beispiel einen Prozess, diese Nachricht Wake Up oder Echo.
Und wenn er feststellt, dass die Prozessornummer, die da mitgeschickt
wird, größer ist als das ihm bekannte Minimum, was zu Anfang aus
seinem eigenen Namen gesetzt wird, dann ignoriert er die Nachricht,
die er bekommt.
Das ist das, was wir auch bei den Leader Elections im Ring gemacht
hatten.
Ignoriert die Nachricht, stößt also dann selbst ein Echo-Algorithmus
an, falls er das nicht schon gemacht hatte.
Seine wären ja kleiner.
Und für den anderen Fall, dass die Nachricht, die er bekommt, kleiner
ist als sein bisher bekanntes Minimum, dann beteiligt er sich am Echo
-Algorithmus von Q und setzt sein lokales Minimum auf Q.
Und das heißt, auf diese Art und Weise werden alle diese eventuell
angestoßenen Leader Election Algorithmen über diesen Echo-Algorithmus,
die größere Nachrichten oder größere Identitäten haben, die von
größeren Initiatoren kommen, die werden irgendwann beendet sein.
Und nur derjenige, der die minimale Identität hat, dessen Echo
-Algorithmus wird tatsächlich am Ende einmal durchgelaufen sein.
Und wenn also das Q gleich Min ist, dann bekommt er ja eine, also er
kann nicht eine, unter der Annahme, dass alle Prozessnummern
verschieden sind, kann er nicht eine Wake-up-Nachricht bekommen haben
von einem anderen,
sondern wenn etwas wieder zu ihm zurückkommt, dann erhöht er die
Anzahl der Min-Nachrichten.
Denn dann weiß er, es ist eine Nachricht von diesem aktuellen
minimalen Echo-Algorithmus bei ihm wieder angekommen.
Und wenn er von allen Nachbarn Min-Nachrichten erhalten hat, dann
schickt er dieses Echo Min an seinen Vorgänger.
Und das heißt, das ist genau diese Überlegung, dann weiß er, er hat
von allen diese Nachrichten bekommen, die müssen ja, das war diese
Überlegung, wann wird ein Echo erzeugt.
Wenn ich von allen Nachbarn diese Min-Nachrichten habe, dann schickt
er das Echo Min an den Vorgänger und der Vorgänger ist derjenige, von
dem er als erstes diese Min-Nachricht erhalten hatte.
Dann ist insgesamt die Anzahl der Nachrichten reduziert, aber es
bleiben trotzdem immer noch Omega von N mal M im schlechtesten Fall.
Weil eventuell eben alle das anstoßen könnten und es sind halt dann
immer noch Omega von N mal M Nachrichten da, aber es wird schon
reduziert.
Das also zu dieser Überlegung und jetzt haben wir noch eine andere
Überlegung für beliebige Netze.
Wenn wir ein beliebiges Netz haben, das ist jetzt eine relativ
einfache untere Schranke, wenn ich N Knoten und M Kanten habe, brauche
ich mindestens Omega von M Nachrichten.
Also für jede Kante in meinem Netz brauche ich mindestens eine
Nachricht.
Und wenn das Netz einen Ring enthält, wissen wir, wir brauchen
mindestens N Log N Nachrichten.
Also ist die untere Schranke, es braucht also mindestens für jede
Kante eine Nachricht bzw.
Anzahl der Knoten mal Log Anzahl der Knoten Nachrichten.
Und die Idee dafür ist, also erstmal mit dem Ring, das ist trivial,
als Folgerung aus unserem Satz.
Und die andere Idee ist folgende, da nimmt man an, es gäbe einen
Algorithmus, der mit weniger als M Nachrichten auskommt.
So, wir haben jetzt M Kanten in unserem Knoten, in unserem Graphen, in
unserem Netz.
Wir haben M Kanten und behaupten, wir könnten weniger als M
Nachrichten dort verwenden.
Weniger als M Nachrichten heißt, über mindestens eine Kante wird keine
Nachricht verschickt.
Das heißt, über irgend so eine Kante UV wird keine Nachricht
geschickt.
Dann erzeugen wir einen Graphen oder ein Netz, in dem dieser
Algorithmus nicht mehr einen Anführer bestimmen kann.
Wir erzeugen einen neuen Graphen G' aus einfach zwei Kopien, die durch
eine Kante zwischen Knoten W und W' verbunden sind,
das sind jeweils neue Knoten, die einfach zwischen U und V geschoben
wurden.
Alles andere ist identisch.
Das sind die beiden Kopien, im Prinzip zweimal unser G.
Der Algorithmus läuft dann ja auch auf diesem großen Graphen, auf
diesem hier.
Und da über die Kante UV keine Nachricht verschickt worden ist, bei
der Wahl des Anführers in dem Graphen G, wird auch in dem großen
Graphen über diese Kante keine Nachricht laufen.
Das heißt, der Algorithmus zur Wahl des Anführers wird nicht
beeinflusst durch diesen neuen Knoten, der zwischen U und V eingebaut
wurde.
Und das heißt, dass dann auf einmal die beiden Kopien meinen, dass sie
zwei verschiedene, also jede meint, sie hätte einen Anführer gefunden,
aber ist eben nicht eindeutig.
Das heißt, der kann so nicht funktionieren.
Das heißt, es muss über jede Kante in so einem Graphen mindestens eine
Nachricht geschickt werden, weil ansonsten Informationen von
irgendwelchen Knoten, die dort noch sein könnten, nicht verwendet
werden in einer solchen Konstruktion.
Also das führt dann zu einem Graphen, der halt keinen Anführer wählen
kann und damit kann diese Annahme nicht stimmen, dass man mit weniger
als M Nachrichten auskommt.
Und damit sind wir schon...
Okay, hier steht sogar noch, das ist genau das, was ich gerade eben
gesagt habe, da der in beiden Kopien laufen kann und dann eben jeweils
dort die Anführer in jeder Kopie gestimmt werden, haben wir zwei
Knoten als Leiter und das kann natürlich nicht sein.
Man kann sogar einen Algorithmus erreichen, der genau diese Schranke
erreicht, der also diese Schranke von dem Satz genau M bzw.
N log N Nachrichten braucht, aber den stelle ich Ihnen nicht vor.
Das ist eines der Bücher, die ich Ihnen in der Literatur gegeben habe.
Da steht eine lange Beschreibung für diesen Algorithmus drin.
Damit sind wir durch die Teile hier durch, die sich mit verteilten
Algorithmen beschäftigen.
Und ich will natürlich hier das beibehalten.
Jetzt stelle ich gerade fest, ich habe vergessen, das Abschlusskapitel
vorzubereiten.
Das macht aber nichts.
Dann gehen wir einfach mal auf das Abschlusskapitel aus 2014.
Das ist ja eigentlich kein großes Problem.
Wo habe ich das Abschließendes?
Dann gehen wir doch mal hier rauf.
Da habe ich tatsächlich versäumt, dass mir das noch nie passiert, dass
ich ein Kapitel nicht vorbereitet hatte.
Wir kommen damit zu den abschließenden Bemerkungen.
Aber da ich diese Vorlesung nicht zum ersten Mal halte, ist es kein
Problem, auf die Informationen vom letzten Jahr zurückzugreifen.
Das Einzige, was anders ist, ist das, was hier steht.
Hier stimmen die Daten nicht.
Die Klausur ist nicht am 23.07., sondern am 22.07.
Also am 22.07.
nicht von 11 bis 12, sondern von 14 bis 15 Uhr.
Und auch nicht im Benz Hörsaal.
Auch das stimmt nicht.
Sondern ist, Sie sagten, im Gerzenhörsaal.
Und die Nummern der Plätze, das können Sie sich raussuchen.
Fragestunde steht jetzt hier drin.
Da bin ich im Augenblick überfragt.
Ich nehme aber an, dass Herr Braun am Freitag wieder da sein wird.
Und die Übermacht ist im Augenblick in Madrid bei einer Tagung.
Er stellt dort eine schöne Arbeit vor.
Und jetzt am Freitag, das wäre der 17.11.30, das stimmt
wahrscheinlich.
Nehme ich mal an.
Also, Klausur.
Ich hoffe, dass Sie dort alle gut vorbereitet sind und alle gute
Leistungen abliefern werden.
Dazu nochmal jetzt ein paar Bemerkungen.
Was ist das Anliegen dieser Vorlesung?
Es ist sicherlich so, dass die Verfahren, mit denen wir
Informationsverarbeitung machen, eigentlich das zentrale Gebiet der
Informatik sind.
Nur so wissen wir, wie wir die Systeme sinnvoll einsetzen können.
Wir brauchen Algorithmen selbstverständlich überall.
Die Rechner sind nie schnell genug.
Ich habe einmal bei einer Veranstaltung, hat tatsächlich ein Kollege
gesagt, bei Verfahren, die beschäftigten sich mit Problemen der
künstlichen Intelligenz.
Und das waren Probleme, oder die Verfahren hatten exponentielle
Laufzeit.
Und er sagte, um schnellere Algorithmen bräuchte man sich nicht zu
kümmern.
Die Rechner werden so schnell, werden die schneller.
Das bringt gar nichts, sich um schnellere Algorithmen zu kümmern.
Das ist also eine starke Ignoranz dessen, was hier eigentlich möglich
ist.
Weil Sie wissen, wenn man einen exponentiellen Algorithmus hat, da
bringt eine lineare Verbesserung gar nichts, sondern da muss ich halt
asymptotisch etwas machen.
Also es lohnt sich immer, nach effizienten Lösungen zu suchen.
Speicher sind auch nicht groß genug, das ist klar, Ressourceneffizienz
ist was Wichtiges.
Und wenn man das macht, muss man halt genau gucken, wie sind die
Randbedingungen.
Das ist eigentlich mein wesentlicher Ansatz in dieser Vorlesung, dass
ich sage, man muss auch genau gucken, was sind eigentlich die zugrunde
liegenden Rechnerinfrastrukturen.
Habe ich einen normalen oder einen Einfachprozessor, habe ich einen
Mehrfachprozessor, kann ich direkt Hardware implementieren, kann ich
also Algorithmen wirklich schnell machen.
Das hängt ganz stark davon ab, welche Berechnungsmöglichkeiten ich
habe.
Heutzutage sind alle unsere Rechner Parallelrechner.
Es war neulich Werbung für das, glaube ich, der Samsung S6 mit einem
Achtfachprozessor drin.
Also selbst ein Smartphone hat schon beachtenswerte
Parallelitätsmöglichkeiten.
Das ist die Standardart, wie man Algorithmen heutzutage eigentlich
entwerfen muss.
Die einfache Art ist natürlich einfach, auf mehrere Prozessoren
einfach unabhängige Tasks zu setzen und die dann so nebenläufig
ausführen zu lassen.
Aber wenn man das noch besser machen will und insbesondere, wenn man
einen Manicore Prozessor hat mit zukünftig Hunderten von Kernen, da
macht es sehr viel Sinn, sinnvoll zu parallelisieren, also effektiv zu
parallelisieren, die Algorithmen zu beschleunigen.
Datenstrukturen spielen auch eine Rolle.
Das habe ich relativ wenig betont, haben wir uns ein bisschen
angeguckt.
Datenstrukturen bei den Suchstrukturen, da haben wir die Rot-Schwarz
-Bäume betrachtet.
Aber das ist eben auch wichtig, ist aber mehr oder weniger Standard.
Kennen Sie auch aus Anfängervorlesungen.
Was ich gerade eben gesagt habe zum Berechnungsmodell, bezog sich
natürlich auch insbesondere auf die Rechnerstrukturen.
Also beim Berechnungsmodell hatte ich darauf hingewiesen, dass man
angucken muss, wie groß sind unsere Argumente.
Spielt die Größe der Zahlen, mit denen wir umgehen, eine Rolle bei den
Kosten, die wir haben?
Und Rechnerstrukturen ist klar.
Parallele Algorithmen, das hatte ich jetzt schon wirklich oft genug
betont, erhalten halt zunehmende Bedeutung und deswegen macht es Sinn,
sich damit zu beschäftigen.
Ich habe Ihnen keinen praktischen Algorithmus vorgestellt, der auf
einem Multicore- oder Minicore-Rechner läuft.
Wir haben keine Parallelenalgorithmen tatsächlich entworfen, die wir
programmiersprachlich entworfen haben und dann auf Parallelrechner
ausgeführt haben.
Wir haben das mehr auf der etwas abstrakteren Ebene betrachtet, aber
das sind genau die Grundlagen, um dann das auch umzusetzen in
Parallelisierung.
Ich habe das an verschiedenen Themen betrachtet.
Ich habe die Algebraischen Probleme betrachtet, die in technisch
-wissenschaftlichen Anwendungen eine große Rolle spielen.
Matrixmultiplikation ist in der Regel ein Benchmark für die
Leistungsfähigkeit eines Superrechners.
Wir haben Polynome und FFT betrachtet.
Wir haben Graph-Probleme betrachtet, relativ kurz.
Da habe ich im Wesentlichen darauf abgehoben, dass man bestimmte
gleichartige algorithmische Strukturen hat.
Das war dieser Warschall-Ansatz und der Matrixmultiplikations-Ansatz.
Auf den ersten Blick sehr ähnliche algorithmische Strukturen, dreifach
geschachtete Schleifen.
Wir haben gesehen, dass diese Struktur bei verschiedenen Problemen,
die man in Graphen lösen muss, wieder auftaucht.
Und wir haben uns auch damit beschäftigt, wie man das gut
parallelisieren kann.
Das waren die Wavefront Arrays oder die befehlsystolischen Felder, die
dort eine Rolle spielen.
Wir haben die klassischen Such- und Sortierverfahren natürlich auch
betrachtet.
Sortieren war klar, insbesondere parallele Sortierverfahren.
Wir haben untere Schranken betrachtet auf zweidimensionalen Feldern.
Ich habe Ihnen die Medianbestimmung vorgestellt in linearer Zeit.
Im Prinzip eine intelligente Variante von Quick-Select, bei der wir
dafür sorgen, dass wir tatsächlich bei jedem rekursiven Schritt immer
einen ausreichend großen Anteil der Menge, in der wir nach Median
suchen, rauswerfen können.
Wir haben uns die Suchverfahren angeguckt mit den Rot-Schwarz-Bäumen.
Und wir haben dann noch die algorithmische Geometrie betrachtet.
Noch wieder eine andere Art von algorithmischen Ansätzen.
Da hatten wir das Sweep-Line-Verfahren und das Verfahren für die
konvexe Hülle.
Mit diesem einen Algorithmus, wo man so einen Wegwerf-Algorithmus hat,
dass man erstmal sich über den Daumen überlegt, wo können eigentlich
die interessanten Punkte sein und dann alles andere oder dann eben
ganz viel wegwerfen kann.
Und dieses Wegwerf-Prinzip ist eigentlich das Prinzip, was man an ganz
vielen Stellen verwendet.
Man versucht, Informationen, die man über ein Problem hat, bestmöglich
auszunutzen, um dadurch den Aufwand für die Lösung des Restproblems zu
minimieren.
Das sind divide-and-conquer-Algorithmen, branch-and-bound-Algorithmen,
die machen alle genau das.
In dem Augenblick, wo ich Informationen habe über das Restproblem, das
noch zu lösen ist, werfe ich möglichst viel weg von dem, was ich
garantiert nicht mehr betrachten muss.
Und damit habe ich dann insgesamt die Möglichkeit, meinen Algorithmus
effizienter zu gestalten.
Und jetzt am Ende nochmal die Leader Election mit einem vielleicht
bisschen trockenen Beweis einer unteren Schranke.
Bisschen kompliziert.
Ich hoffe, dass Sie das trotzdem nachvollziehen konnten.
Die Prinzipien, die ich vorgestellt habe, sind eben durchaus
verschiedene Datenstrukturen, aber dann vor allen Dingen diese
verschiedenen Rechnerstrukturen, sequentielle, parallele Verfahren,
Hardware -Algorithmen, verteilte Algorithmen.
Ich hoffe, dass Sie das mitnehmen aus der Vorlesung, dass es Sinn
macht, einen Algorithmus anzupassen an die verfügbaren
Rechnerstrukturen.
Und dass es durchaus sein kann, dass ein algorithmischer Ansatz, der
für eine Rechnerstruktur schlecht ist, für eine andere auch immer sehr
gut ist.
Da war das Beispiel von Bubble Sort und dem odd-even-transposition
Sort, das auf einmal auf dem linearen Feld optimal ist.
Und Bubble Sort natürlich ein schlechtes sequentielles Verfahren.
Ich habe Ihnen ein bisschen was über untere Schranken erzählt.
Relativ wenig.
An wenigen Stellen beim Suchen haben wir es gemacht, bei den Polynomen
und jetzt nochmal bei der Leader Election.
Dadurch haben Sie gesehen, was man dort im Prinzip machen kann.
Was ich wenig gemacht habe, was eigentlich fehlt, das sind so die
Sachen, die zu tun haben mit Randomisierung.
Das wäre noch ein ganz anderes Thema, auch ein ganz wichtiges Thema
des Algorithmen Engineering, dass ich mit Randomisierungsstrukturen
oder mit Randomisierung von Algorithmen schwierige Probleme besser
lösen kann.
Ich habe Ihnen etwas erzählt über systematischen Entwurf paralleler
Verfahren, den Mapping-Ansatz.
Auch eine wichtige Technik, dass man sich ein Problem spezifiziert in
einer gewissen einfachen Art und Weise über diese
Rekurrenzgleichungen.
Und wenn man dort jetzt gewisse einfache Strukturen hat, im Sinne
dieser uniformen Rekurrenzgleichungssysteme, bei denen die
Datenabhängigkeiten alle gleichartig sind, also an den verschiedenen
Punkten, an denen etwas berechnet werden muss, dann konnte man ja sehr
systematisch über mathematische Transformationen parallele Algorithmen
erzeugen.
Und das ist etwas, was auch wirklich eingesetzt wird, um also Teile
von Algorithmen automatisch zu erzeugen, aus einer im Prinzip
mathematischen Beschreibung des Problems, was dann zu garantiert
korrekten Algorithmen führt, weil die eben automatisiert entworfen
werden.
Da sind also Fehlerquellen, die man beim manuellen Entwurf hätte, halt
damit ausgeschaltet.
Die Weidenkonker kennen Sie alle, die Ansätze.
Das ganze Sweepline-Verfahren war bei der algorithmischen Geometrie
ein wichtiges Verfahren, dass ich eben sage, ich löse ein n
-dimensionales Problem nicht direkt, sondern ich transformiere das auf
ein n-1-dimensionales Problem und muss dann aber eine Reihe von
solchen n-1-dimensionalen Problemen lösen.
Das war bei der Bestimmung der Schnittpunkte von Geraden so, dass wir
die Haltepunkte, die Endpunkte der einzelnen Linien uns angucken
mussten.
Das waren die verschiedenen Haltepunkte für diese n-1-dimensionalen
Probleme.
Das sind also die Prinzipien.
Ich hoffe, dass Sie damit etwas gelernt haben, was Sie vielfältig
verwenden können.
Das sind einfach grundlegende Ansätze und mein Anliegen ist, Ihnen
diese grundsätzlichen Ansätze für den Entwurf von Algorithmen zu
vermitteln.
Die einzelnen Algorithmen sind gar nicht so wichtig.
Das ist alles nett, wenn man die kennt, wenn man die vergisst, guckt
man im Buch nach und findet sie wieder.
Aber die Prinzipien, wie man vorgeht, dass man eben versucht, die
Informationen, die man hat, bestmöglich auszunutzen und dann
Informationen über die Art des Problems, über die Art der
Rechnerstrukturen und dann die verfügbaren Ressourcen bestmöglich
auszunutzen.
Das ist einfach das Wesentliche, was ich Ihnen vermitteln wollte in
der Vorlesung.
Jetzt gibt es noch viele andere Dinge bei uns am AEFB, wobei das hätte
ich jetzt wirklich ergänzen müssen.
Das ist aber eben, das galt im vorigen Jahr, das gilt dieses Jahr
nicht mehr.
Dieses gibt es nicht mehr.
Das gibt es nicht mehr.
Herr Seese scheidet Ende dieses Semesters aus.
Herr Tay, da steht auch NN, auch das Gebiet Ökonomie und Technologie
der E-Organisation, das war im Wesentlichen das Service-Oriented
Computing, das wird so nicht wieder besetzt.
Dort kommt jetzt hin eine Professur für angewandte technisch-kognitive
Systeme.
Da haben wir gerade die Berufungsliste fertig gemacht.
Wir hoffen, dass da zum Wintersemester oder spätestens zum
Sommersemester dann konkret die Stelle besetzt ist.
Und da wird es gehen um alle möglichen kognitiven Systeme in der
Mobilität, autonomes Fahren und solche Dinge spielen eine Rolle oder
auch Roboteranwendungen.
Ich denke, das ist eine Thematik der angewandten Informatik, die sehr
gut hier bei uns in das Institut reinpasst.
Herr Seese scheidet jetzt aus.
Seine Stelle wird im Winter ausgeschrieben und wird vermutlich
zunächst mal gehen Richtung Energieinformatik.
Und wenn die Stelle besetzt wird, ist das im Prinzip zunächst mal mein
vorgezogener Nachfolger, sofern wir das schnell hinbekommen.
Also das tut sich ein bei uns in unserem Institut.
Und wir haben hier noch einen weiteren, und dann wird irgendwann die
Stelle von Herrn Seese auch wieder besetzt werden, und wir haben noch
einen weiteren Kasten hier drin, das ist ein Kasten für Webscience.
Webscience, das ist Herr Sure Vetter, der seit 1.
Juni am Institut ist.
Das heißt, Webscience hängt sehr stark mit dem zusammen, was Herr
Studer macht.
Herr Sure Vetter ist im Prinzip der vorgezogene Nachfolger von Herrn
Studer.
Und das gibt halt altersgemäß ein paar Veränderungen im Institut.
Und entsprechend verändert sich auch das Lehrangebot.
Also ich werde noch zwei Jahre da sein, das heißt, diese Vorlesung
halte ich noch mindestens einmal im nächsten Jahr.
Ob ich die in meinem letzten Semester nochmal halte, 2017 habe ich
noch nicht entschieden.
Aber die anderen Bereiche, also bei Herrn Oberweiß ist das relativ
stabil, und das andere, da verändert sich einiges im Augenblick.
Was gibt es in meinem Bereich für Vorlesungen?
Die werden alle noch angeboten im Augenblick.
Also die Effizienten Algorithmen, mindestens nochmal im nächsten
Sommer.
Organic Computing, immer im Sommersemester.
Algorithms for Internet Applications, im Wintersemester, werden auch
im Winter wieder angeboten.
Die naturinspirierten Optimierungsverfahren von Herrn Schukla kommen
im Sommersemester.
Und dann die Computational Economics, nicht von Herrn Keighton,
sondern nur von Herrn Schukla, jetzt im Wintersemester.
Und meine Vorlesung Smart Energy Distribution auf Englisch, auch im
Sommersemester.
Also das ist das Vorlesungsangebot im Augenblick an meiner
Arbeitsgruppe.
Und da können Sie sich noch alles mögliche aussuchen, sofern Sie
Interesse weiterhin haben an diesem Bereich, was ich natürlich hoffe.
Und dann haben wir hier noch Seminare, aktuelle Spezialthemen, das ist
fast richtig, aber nicht ganz.
Machen wir hier noch einen Punkt dazu.
Jetzt im Wintersemester werden das Modellierung und Simulation in
Smart Grid.
Das ist also Wintersemester 15-16.
Wenn Sie also Interesse daran haben, wie man die Systeme im
Energiebereich sinnvoll modelliert und simuliert, können Sie da ein
Seminar mitmachen.
Und dann gibt es ein Praktikum im Wintersemester.
Das war also Wintersemester 14-15.
In diesem Wintersemester gibt es eins über Security im Prinzip Smart
Energy.
Das ist also jetzt Wintersemester 15-16.
Also wenn Sie Interesse haben, ein Praktikum zu machen, da ist ein
Sicherheitsseminar.
Das hat das Ding zu tun mit unserem Kompetenztrendum für angewandte
Sicherheitstechnologien Castell, in dem wir mit einer Reihe von
anderen Lehrstühlen kooperieren.
Deswegen ist das etwas, was wir in Kooperation mit einer Reihe anderer
Lehrstühle machen.
Genauso dieses Seminar hier im Wintersemester ist eine Kooperation mit
Frau Wagner in der Informatik und Herrn Hagenmeier, der auch in der
Informatik und im Campus Nord sitzt.
Gut, das habe ich hier noch dazu.
Abschlussarbeiten gibt es beliebig.
Im Wesentlichen mittlerweile ist das also der Bereich
Energieinformatik.
An Themen, die wir jetzt vergeben, die Teile hier Evolutionäre
Verteilte Optimierung.
Auch da wird noch einiges gemacht, macht vor allen Dingen Herr
Schukler.
Organic Computing haben wir eigentlich ein bisschen in den Hintergrund
laufen lassen.
Wobei das, was dort gemacht wird, eigentlich mittlerweile hier
einfließt in unsere Überlegungen zur Energieinformatik.
Sie dürfen gerne bei uns mitwirken in Forschungsprojekten, auch im
FZI, Forschungszentrum Informatik.
Und dann gibt es hier das Diplomandenseminar, wobei das eigentlich
nicht mehr so heißen dürfte, weil es keine Diplomanden mehr gibt.
Aber das ist halt der alte Begriff.
Das ist das Seminar für Abschlussarbeiter, Bachelor oder Master, wo
man halt vorträgt, was man gerade in seiner Abschlussarbeit macht.
Und solche Arbeiten sollte man möglichst früh in seinem Studium oder
sich überlegen, wo man die Arbeit schreiben will, damit man dann eben
auch sein Studium entsprechend ausrichten kann.
Also, das so an Randbemerkungen.
Abschließendes, das gilt auch jedes Jahr wieder.
Ich hoffe, dass Sie den Wert der Inhalte für Ihren beruflichen Weg
erkennen und viele neue Einsichten gewinnen konnten.
Geben Sie mir Rückmeldung zu dem, was Sie an Gedanken haben dazu.
Ich wünsche Ihnen viel Erfolg in der Klausur.
Ich habe Sie gar nicht gefragt, ob Sie noch Fragen haben.
Das mache ich jetzt.
Haben Sie noch irgendwelche Wünsche, irgendwelche Fragen, die wir
jetzt kurz klären sollten?
Oder war das heute zu erschlagend mit diesem Beweis?
Keine Rückmeldung, keine Fragen.
Gut, dann wünsche ich Ihnen viel Erfolg in der Klausur.
Dann war es das für dieses Semester.