WEBVTT 00:00.000 --> 00:02.300 Ich möchte jetzt zu einem Problem kommen, das wir uns genauer 00:02.300 --> 00:02.700 angucken. 00:04.360 --> 00:08.200 Das ist das, was ich hier mir raussuche für diese wenige Zeit, die ich 00:08.200 --> 00:10.220 noch habe, heute und nächste Woche. 00:11.280 --> 00:13.500 Leader Election, Wahl eines Anführers. 00:15.720 --> 00:18.460 Und ich kann auch sagen, Konsensprobleme. 00:19.400 --> 00:22.200 Wahl eines Anführers ist ein typisches, einfaches Konsensproblem. 00:22.400 --> 00:25.020 Und Sie werden sehen, man kann dort eine Reihe von interessanten 00:25.020 --> 00:27.740 Erkenntnissen gewinnen, wenn man sich dieses Problem anschaut. 00:28.260 --> 00:31.440 Und es ist die Frage, was habe ich eigentlich für Anforderungen, wenn 00:31.440 --> 00:33.900 ich ein Konsensproblem bearbeiten muss oder so ein Leader Election 00:33.900 --> 00:34.240 Problem. 00:35.500 --> 00:40.020 Und es gibt so eine Reihe von Annahmen bei verteilten Algorithmen, 00:40.100 --> 00:44.160 dass man sagt, etwas ist verteilt, das soll symmetrisch sein. 00:44.280 --> 00:47.760 Ich habe hier also symmetrisch, vollständig verteilt. 00:48.160 --> 00:52.180 Das heißt, ich habe gleichberechtigte Prozesse, die alle die gleichen 00:52.180 --> 00:56.160 Eigenschaften haben, die alle gleich vorgehen sollen. 00:56.280 --> 00:59.940 Sie kennen das Philosophenproblem aus Grundlagen Informatik 2 00:59.940 --> 01:00.720 vielleicht noch. 01:01.520 --> 01:03.840 Philosophenproblem ist ein typisches Problem der verteilten 01:03.840 --> 01:04.440 Berechnungen. 01:05.780 --> 01:08.340 Und sie sind alle gleichberechtigt. 01:08.800 --> 01:12.460 Und jetzt brauchen die einen Koordinator oder einen Anführer oder eine 01:12.460 --> 01:12.980 Zentrale. 01:13.120 --> 01:17.460 Sie erinnern sich bei dem Philosophenproblem, da haben wir die vielen 01:17.460 --> 01:21.020 Philosophen, die um einen Tisch herum sitzen und alle hier ihre Teller 01:21.020 --> 01:22.000 vor sich stehen haben. 01:22.000 --> 01:25.440 Und das Problem ist, dass die jeweils nur eine Gabel dazwischen liegen 01:25.440 --> 01:25.660 haben. 01:25.780 --> 01:28.680 Sie brauchen aber, um zu essen, halt zwei Gabeln und müssen sich 01:28.680 --> 01:30.980 einigen, wer jetzt eine Gabel nehmen darf und wer nicht. 01:31.500 --> 01:35.300 Wenn Sie da einen Anführer wählen, kann der sagen, wer jetzt essen 01:35.300 --> 01:36.120 darf und wer nicht. 01:36.360 --> 01:41.300 Also typisches Problem bei Philosophen in einer verallgemeinerten 01:41.300 --> 01:41.660 Form. 01:42.400 --> 01:45.900 Und Sie wollen jetzt bei solchen gleichberechtigten Prozessen einen 01:45.900 --> 01:46.880 neuen Anführer wählen. 01:47.560 --> 01:52.500 Und die Anforderungen sind, dass das symmetrisch gleichverteilt ist. 01:53.320 --> 01:58.480 Das heißt, wenn das symmetrisch ist, sind alle gleichartig beteiligt. 01:58.980 --> 02:03.580 Eine typische Annahme ist, ich darf nicht jemanden wählen aufgrund 02:03.580 --> 02:08.020 seiner Identität, also aufgrund seines Namens. 02:09.260 --> 02:12.360 Ich muss andere Dinge wählen. 02:12.360 --> 02:15.720 Sonst könnte man ja einfach den mit der kleinsten Nummer auswählen. 02:16.240 --> 02:18.500 Tatsächlich macht man das so, wenn man sagt, das kommt nicht darauf 02:18.500 --> 02:18.840 an. 02:21.640 --> 02:24.360 Aber zunächst einmal sagt man, eigentlich soll jeder die gleiche 02:24.360 --> 02:28.200 Möglichkeit haben, Leiter zu werden, dann darf ich ihn nicht nach dem 02:28.200 --> 02:30.340 Namen auswählen, nach dem Alphabet. 02:30.700 --> 02:31.020 Geht nicht. 02:32.320 --> 02:34.620 Alle Beteiligten sollen in gleicher Weise mitwirken. 02:36.060 --> 02:36.500 Symmetrisch. 02:36.620 --> 02:38.860 Alle in der gleichen Art und Weise, sonst wären sie ja nicht 02:38.860 --> 02:39.700 gleichberechtigt. 02:40.180 --> 02:44.080 Hat was ähnliches wie allgemeine gleiche freie Wahlen und so weiter. 02:45.000 --> 02:49.300 Und am Ende der Wahl des Leiters müssen alle Beteiligten die gleiche 02:49.300 --> 02:51.580 Information über die Identität des Leiters haben. 02:52.060 --> 02:53.820 Alle müssen wissen, wen sie gewählt haben. 02:54.260 --> 02:56.060 Der Leiter muss wissen, dass er gewählt wurde. 02:56.400 --> 02:58.740 Und alle anderen müssen wissen, dass er der Leiter ist. 03:01.320 --> 03:02.600 Ganz einfaches Problem. 03:03.000 --> 03:05.220 Sie sehen, man hat hier schon eine Reihe Anforderungen, die man hier 03:05.220 --> 03:05.540 stellt. 03:06.450 --> 03:12.940 Und das, was hier also gefordert ist, heißt, ich brauche in den Termen 03:12.940 --> 03:16.300 der verteilten Algorithmen einen vollständig verteilten symmetrischen 03:16.300 --> 03:17.020 Algorithmus. 03:17.580 --> 03:20.960 Alle entscheiden lokal mit identischem Algorithmus. 03:22.380 --> 03:25.860 Und wenn man sich das genauer anschaut, jetzt nehmen wir noch an, 03:26.320 --> 03:28.900 Topologie, welche Kommunikationsstruktur haben wir. 03:29.460 --> 03:33.000 Wir nehmen an, dass die über einen Ring miteinander verbunden sind. 03:33.000 --> 03:36.780 Das heißt, jeder kann von seinem Vorgänger Informationen bekommen, 03:37.320 --> 03:38.540 über irgendeine Nachricht. 03:40.200 --> 03:43.560 Und dadurch, dass hier Nachrichten sukzessive rumgeschickt werden, 03:44.420 --> 03:45.580 kann ich also kommunizieren. 03:47.420 --> 03:53.120 Und es gibt schon einen alten Satz, 34 Jahre alt. 03:53.860 --> 03:57.040 In einem Ring identischer Prozessoren kann es keinen 03:57.040 --> 03:59.760 deterministischen, vollständig verteilten und symmetrischen 03:59.760 --> 04:02.020 Algorithmus zur Wahl eines Leiters geben. 04:03.280 --> 04:06.540 Also wenn alle genau die gleichen Entscheidungen treffen, Sie dürfen 04:06.540 --> 04:10.180 nicht die Identität verwenden, die die einzelnen Prozessoren haben. 04:10.320 --> 04:13.200 Also die werden ja durchnummeriert sein, vielleicht irgendwie mit 04:13.200 --> 04:14.160 irgendwelchen Zahlen. 04:17.520 --> 04:19.100 Irgendwelche Zahlen können die haben. 04:19.840 --> 04:21.300 Ich kann nicht diese Zahlen verwenden. 04:22.780 --> 04:25.980 Und da kann man zeigen, und das geht ähnlich wie bei den 04:25.980 --> 04:29.080 Philosophenproblemen, wenn Sie alle die gleiche Entscheidung treffen. 04:29.080 --> 04:32.880 Beim Philosophenproblem ist es so, nur um Ihnen das nochmal zu zeigen, 04:34.180 --> 04:37.880 wenn alle die gleichen Entscheidungen treffen, würde zum Beispiel ein 04:37.880 --> 04:42.340 Algorithmus, der sagt, ich greife mir zunächst die rechte Gabel, wenn 04:42.340 --> 04:43.160 sie frei ist. 04:43.840 --> 04:47.440 Dann würden alle, wenn die rechte Gabel frei ist, die rechte Gabel 04:47.440 --> 04:47.840 greifen. 04:49.600 --> 04:53.540 Und dann greifen Sie als nächste Entscheidung, ich behalte also diese 04:53.540 --> 04:56.620 Gabel in der Hand und wähle die linke Gabel, sobald sie frei ist. 04:57.080 --> 04:58.000 Und das ist ein Deadlock. 04:59.320 --> 05:04.260 Das ist ein typisches Verhalten eines symmetrischen Algorithmus, alle 05:04.260 --> 05:05.500 treffen die gleiche Entscheidung. 05:06.980 --> 05:10.740 Und Sie können in dem Fall bei den Philosophenproblemen nur zu einer 05:10.740 --> 05:14.420 Lösung kommen, wenn Sie unterschiedliche Entscheidungen treffen. 05:15.540 --> 05:18.040 Das funktioniert halt nicht unter diesen Annahmen, die ich hier hatte. 05:18.620 --> 05:21.220 Ähnlich kann man das für diesen Ring identischer Prozessoren zeigen, 05:21.320 --> 05:25.780 dass die also nicht in der Lage sind, unter diesen Annahmen, mit einem 05:25.780 --> 05:28.820 deterministischen, vollständig verteilten, symmetrischen Algorithmus, 05:29.540 --> 05:31.580 einen Leiter zu wählen. 05:32.320 --> 05:34.720 Ich gehe auf den Beweis nicht weiter ein, ich habe viele andere Dinge, 05:34.840 --> 05:35.800 die ich Ihnen auch erzählen möchte. 05:36.760 --> 05:39.060 Und ich möchte Ihnen zeigen, wie man jetzt, wenn man sagt, okay, das 05:39.060 --> 05:41.300 geht so nicht, machen wir das doch anders. 05:41.860 --> 05:44.400 Wir erlauben die Ausnutzung der Identität. 05:45.360 --> 05:47.480 Wir haben unseren Ring von Prozessoren. 05:49.800 --> 05:53.060 Und ich habe also hier einen Ring von Prozessoren. 05:53.060 --> 05:57.040 Und jetzt wird folgenden Algorithmus ausgeführt. 05:57.540 --> 05:59.260 Ich sende meine Identität. 05:59.380 --> 06:00.940 Jeder hat also eine Identität. 06:02.160 --> 06:04.280 Irgendeinen Namen, eine Zahl. 06:05.820 --> 06:08.280 Der Einfachheit halber nehmen wir an, wir haben N Prozessoren. 06:09.520 --> 06:11.040 Jeder Prozessor hat eine Zahl. 06:12.000 --> 06:16.240 Und der sendet also seine Identität, seine Zahl zum Nachbarn. 06:16.840 --> 06:19.340 Sendet also die hier rüber zu seinem Nachbarn. 06:20.020 --> 06:26.320 Der Nachbar oder jeder Prozessor wartet darauf, dass er, nachdem er 06:26.320 --> 06:28.320 etwas rausgeschickt hat, dass er etwas bekommt. 06:30.440 --> 06:33.700 Der möchte also gerne von seinem, also Next ist immer der Nachfolger 06:33.700 --> 06:36.660 in diesem Ring, Previous ist der Vorgänger in dem Ring. 06:37.900 --> 06:41.480 Er wartet darauf, bis er etwas bekommt, das ist Receive X, from 06:41.480 --> 06:42.000 Previous. 06:43.140 --> 06:46.760 Und wenn das, was er bekommt, er hat ja seine eigene Identität hier, 06:46.760 --> 06:52.600 wenn das, was er bekommt, kleiner ist als seine eigene Identität, dann 06:52.600 --> 06:58.180 sendet er dieses Paket hier weiter zu seinem Nachbarn. 07:00.320 --> 07:08.640 Wenn er als Nachricht von seinem Nachbarn eine Nachricht bekommt, die 07:08.640 --> 07:14.280 genau seine eigene Identität ist, heißt das unter der Annahme, alle 07:14.280 --> 07:18.500 Prozessoren haben unterschiedliche Identitäten, dass die Nachricht 07:18.500 --> 07:21.460 einmal rumgelaufen ist und wieder zurückkommt. 07:22.840 --> 07:27.500 Es kann aber eine Nachricht nur dann rumlaufen und wieder zu ihm 07:27.500 --> 07:33.620 zurückkommen, wenn es immer eine Nachricht war, die kleiner war als 07:33.620 --> 07:36.060 die Identität der Prozessoren, wo sie durchgelaufen ist. 07:36.060 --> 07:43.140 Denn wenn sie größer wäre, dann würde man ja gar nichts machen, dann 07:43.140 --> 07:44.480 würde man die Nachricht ja nicht weiterschicken. 07:45.820 --> 07:49.140 Derjenige, der jetzt die Nachricht wieder bekommen hat, der schickt 07:49.140 --> 07:55.180 jetzt den negativen Wert seiner Identität weiter an den Nachbarn. 07:56.240 --> 07:58.620 Wir gehen davon aus, alle Identitäten sind positiv. 07:59.520 --> 08:01.120 Jetzt schicke ich einen negativen Wert rum. 08:03.140 --> 08:08.560 Dadurch, dass ich das minus x rumschicke, also danach ist er übrigens 08:08.560 --> 08:13.720 fertig, until x gleich id, also dieser, der das gemacht hat, hört 08:13.720 --> 08:15.760 anschließend hier mit dieser Repeat-Schleife auf. 08:17.440 --> 08:20.320 Kann man auch als while formulieren, ich habe es ja als repeat 08:20.320 --> 08:20.920 formuliert. 08:22.460 --> 08:27.880 Oder wenn das x kleiner als 0 ist, dann hört er auch auf. 08:27.880 --> 08:33.580 Dann hat er also hier vom Nachbarn einen negativen Wert erhalten. 08:34.100 --> 08:38.100 Wenn er einen negativen Wert vom Nachbarn erhält, heißt das, dieses 08:38.100 --> 08:43.260 minus x ist ja nur geschickt worden, weil eine Nachricht ganz 08:43.260 --> 08:44.440 rumgelaufen ist. 08:45.240 --> 08:49.680 Dieser Prozessor hat festgestellt, die Nachricht kam hier auch an und 08:49.680 --> 08:51.100 das war genau diese Identität. 08:51.200 --> 08:55.300 Das heißt, das muss die kleinste Identität sein in diesem Ring. 08:56.440 --> 08:59.740 Wenn das aber die kleinste ist, dann ist das, was ich gerade unter 08:59.740 --> 09:03.640 Ausnutzung der Identität feststellen wollte, ich wähle denjenigen, der 09:03.640 --> 09:05.420 die kleinste Identität hat. 09:06.040 --> 09:09.920 Und dadurch, dass ich diesen Wert x bekommen habe oder minus x 09:09.920 --> 09:13.140 bekommen habe, weiß ich auch, wie der heißt, nämlich x. 09:15.560 --> 09:19.120 Also hier steht x kleiner 0, also jetzt natürlich x Absolutwert, davon 09:19.120 --> 09:23.100 ist jetzt der Name meines, dadurch, dass ich das minus x rumschicke, 09:23.100 --> 09:26.020 habe ich gleichzeitig den Namen des Leiters mit rumgeschickt. 09:26.360 --> 09:31.280 Das heißt, alle wissen, wenn sie hier rausgelaufen sind, wer der 09:31.280 --> 09:32.060 Anführer ist. 09:33.620 --> 09:36.900 Es weiß derjenige, der gewählt wurde, weil das genau die Nachricht, 09:36.980 --> 09:38.840 die er bekommen hatte, seine eigene Identität war. 09:39.740 --> 09:43.160 Und alle anderen wissen, wer gewählt wurde. 09:44.200 --> 09:51.220 Und sie wissen auch, dass man fertig ist, weil das Erhalten einer 09:51.220 --> 09:54.280 negativen Nachricht heißt, es hat jemand festgestellt, dass er gewählt 09:54.280 --> 09:54.940 worden ist. 09:55.300 --> 09:58.080 Und wenn ich das jetzt bekommen habe, diese Nachricht, dann weiß ich, 09:58.120 --> 10:01.700 ich kann jetzt auch praktisch wieder einschlafen oder was anderes tun, 10:02.100 --> 10:03.260 ich weiß, wer der Anführer ist. 10:05.380 --> 10:12.560 Und derjenige, der jetzt das minus x rausgeschickt hatte, der wartet 10:12.560 --> 10:18.180 noch darauf, dass er von seinem Vorgänger diese Nachricht noch einmal 10:18.180 --> 10:18.700 bekommt. 10:19.980 --> 10:22.080 Oder eine Nachricht bekommt. 10:23.780 --> 10:27.480 Eine Nachricht, die rausgeschickt wurde, muss auch empfangen werden. 10:28.180 --> 10:31.840 Und der direkte Vorgänger muss ja dieses minus x, was der hier 10:31.840 --> 10:34.760 rausgeschickt hat, dann auch nochmal wieder weiterschicken. 10:35.140 --> 10:37.520 Das muss also noch einmal akzeptiert werden. 10:38.500 --> 10:42.300 Und dann ist man fertig. 10:43.720 --> 10:47.200 Also über diese Bedingung x kleiner id, das gilt ja auch, wenn das x 10:47.200 --> 10:48.160 kleiner als 0 ist. 10:49.080 --> 10:52.080 Deswegen wird das minus x, also dieser negative Wert, auch ganz 10:52.080 --> 10:52.660 rumgeschickt. 10:53.380 --> 10:58.080 Und das heißt, dieses Verfahren ist eindeutig dafür geeignet, um 10:58.080 --> 11:04.180 festzustellen, welches ist der kleinste Wert der Identitäten in diesem 11:04.180 --> 11:04.420 Ring. 11:05.340 --> 11:06.680 Sehr einfaches Verfahren. 11:07.660 --> 11:12.100 Oh, Sie sehen, ich habe das hier sogar aufgemalt. 11:13.920 --> 11:16.120 Da ist also jetzt das angedeutet. 11:16.840 --> 11:19.860 Und wenn die jetzt alle ihre Nachrichten verschicken, das ist die 11:19.860 --> 11:20.540 Anfangssituation. 11:21.500 --> 11:22.760 Ich habe hier einen solchen Ring. 11:23.480 --> 11:25.360 Alle schicken ihre Identitäten nach rechts. 11:26.800 --> 11:28.600 An welchen Stellen haben wir jetzt diese Situation? 11:29.440 --> 11:30.560 Eins wird weitergeschickt. 11:31.160 --> 11:34.920 Hier müsste weitergeschickt werden, weil eins kleiner als sechs ist. 11:34.920 --> 11:36.800 Sechs ist größer als fünf. 11:37.680 --> 11:39.660 Der wird die sechs nicht weiterschicken. 11:40.580 --> 11:42.220 Fünf ist kleiner als neun. 11:43.340 --> 11:46.080 Das hier wird weitergeschickt an der Stelle. 11:47.040 --> 11:49.100 Neun ist größer als zwei, da wird nichts weitergeschickt. 11:49.720 --> 11:51.000 Zwei ist kleiner als acht. 11:51.520 --> 11:53.600 An dieser Stelle wird etwas weitergeschickt werden. 11:55.180 --> 11:57.220 Acht ist größer als vier, da passiert nichts. 11:57.340 --> 11:59.040 Vier ist größer als drei, passiert auch nichts. 11:59.160 --> 12:01.220 Drei ist größer als eins, passiert auch nichts. 12:01.220 --> 12:06.120 Und das waren alle, die hier in dem Fall rausgeschickt werden. 12:06.260 --> 12:12.520 Also im nächsten Schritt werden nur noch diese eins, zwei, drei 12:12.520 --> 12:13.660 Nachrichten verschickt. 12:14.780 --> 12:16.260 An diesen drei Stellen. 12:17.060 --> 12:18.860 Erstmal haben alle etwas verschickt. 12:19.300 --> 12:22.840 Da kann man sich fragen, wie erreiche ich denn, dass alle gleichzeitig 12:22.840 --> 12:24.480 ihre Identitäten verschicken. 12:24.560 --> 12:27.380 Dazu müssen sie ja wissen, dass sie das jetzt so machen sollen. 12:29.160 --> 12:31.480 Das muss nicht unbedingt alles gleichzeitig passieren. 12:31.620 --> 12:35.800 Die müssen nur angestoßen werden, dass sie die Nachricht rausschicken. 12:37.380 --> 12:40.840 Sie müssen zunächst einmal ihre eigene Nachricht rausschicken, müssen 12:40.840 --> 12:42.140 dafür angestoßen werden. 12:42.580 --> 12:45.100 Das kann irgendeine Anstoßnachricht sein, die hier rumläuft. 12:45.840 --> 12:48.980 Und dann geht es darum, was wird in der nächsten Runde jetzt 12:48.980 --> 12:49.340 verschickt. 12:49.820 --> 12:52.800 Und Sie sehen, hier werden nur noch drei Nachrichten verschickt. 12:54.140 --> 12:56.920 Und jetzt trifft also hier die Eins auf die Fünf. 12:57.040 --> 12:59.740 Dann wird jetzt an dieser Stelle was rausgeschickt. 13:00.820 --> 13:04.300 Und ansonsten, die Fünf trifft auf eine Zwei, da passiert nichts. 13:04.800 --> 13:08.300 Die Zwei trifft auf eine Vier, dann wird hier noch was rausgeschickt. 13:08.840 --> 13:09.540 Und das ist es. 13:09.920 --> 13:12.860 Also an diesen beiden Stellen, die Eins und die Zwei wandern weiter. 13:12.960 --> 13:14.320 Die Zwei ist kleiner als drei. 13:14.900 --> 13:17.480 Auch das wird weiterlaufen, die Eins läuft natürlich weiter rum. 13:18.000 --> 13:20.820 Die Zwei ist größer als die Eins und damit fällt sie weg. 13:20.820 --> 13:24.840 Und jetzt läuft die Eins hier noch weiter an den einzelnen Positionen 13:24.840 --> 13:25.200 vorbei. 13:25.740 --> 13:28.780 Trifft in diesem Fall auf die Eins. 13:29.340 --> 13:32.500 Und damit weiß derjenige Prozessor, dass er fertig ist. 13:32.900 --> 13:38.280 Das heißt, es dauert genau, wenn ich N Prozessoren habe, genau N 13:38.280 --> 13:40.240 Takte, bis das einmal rumgelaufen ist. 13:40.320 --> 13:43.360 Die Eins läuft ja von vorne, also von dem Kleinsten läuft das Ding 13:43.360 --> 13:45.080 natürlich in jeder Runde einmal Eins weiter. 13:47.060 --> 13:50.560 Und dann geht anschließend der negative Wert rum. 13:50.960 --> 13:54.380 Der weiß, dass er gewählt wurde, hat seine Farbe verändert. 13:55.200 --> 13:58.500 Und er schickt die Minus Eins an den Nachbarn. 13:59.020 --> 14:02.540 Der weiß dadurch, dass die Eins gewählt wurde und ist fertig. 14:02.900 --> 14:04.060 Jetzt läuft das entsprechend rum. 14:04.880 --> 14:09.820 Und sukzessive wissen sie alle, dass die Eins gewählt wurde, weil die 14:09.820 --> 14:11.060 Minus Eins hier rumläuft. 14:12.340 --> 14:16.320 Und anschließend müsste ich eigentlich sogar den nochmal anders 14:16.320 --> 14:17.080 markieren. 14:17.360 --> 14:18.840 Er weiß, dass er gewählt wurde. 14:18.900 --> 14:22.380 Und er weiß jetzt auch, dass alle anderen wissen, dass er gewählt 14:22.380 --> 14:24.920 wurde, weil er diese Nachricht wiederbekommen hat. 14:26.420 --> 14:28.840 Das sind so die Probleme, die man alle dabei beachten muss. 14:29.500 --> 14:30.380 Wie ist der Aufwand? 14:31.080 --> 14:33.680 Wenn wir nur die Nachrichten zählen, also innen drin mussten sie ja 14:33.680 --> 14:35.980 nicht viel tun, das ist ja trivial, was sie da machen mussten. 14:37.500 --> 14:38.800 Wie viele Nachrichten habe ich? 14:40.200 --> 14:44.960 Ich habe zunächst mal N Nachrichten, weil jeder seine Nachricht 14:44.960 --> 14:45.420 verschickt. 14:45.780 --> 14:48.100 Sie fragen, wie viele Nachrichten werden danach noch weitergeschickt? 14:51.400 --> 14:54.120 Also wir hatten gesehen, da wurden nur drei Nachrichten 14:54.120 --> 14:54.800 weitergeschickt. 14:55.540 --> 14:56.360 Danach noch weniger. 14:57.140 --> 14:58.760 Wenn ich Pech habe, Sie haben eine Frage? 15:04.190 --> 15:08.830 Genau, es kann immer eins weniger werden, aber ich bekomme auf die Art 15:08.830 --> 15:12.170 und Weise quadratische Anzahl von Nachrichten, im schlechtesten Fall. 15:12.910 --> 15:13.730 Kann ich nicht vermeiden. 15:13.830 --> 15:16.530 Wenn die ungünstig verteilt sind, die Identitäten, habe ich halt 15:16.530 --> 15:17.750 quadratische Anzahl. 15:18.970 --> 15:20.190 Das kann ich verbessern. 15:20.750 --> 15:23.290 Ich kann die Anzahl der Nachrichten auf N log N reduzieren. 15:23.370 --> 15:24.650 Das werden wir später sehen, wie das geht. 15:25.330 --> 15:28.070 Das ist ganz interessant, wie man sich überlegen kann, wie man 15:28.070 --> 15:30.110 Kommunikationsaufwand reduzieren kann. 15:30.210 --> 15:33.170 Was muss ich eigentlich kommunizieren, um eine Information 15:33.170 --> 15:34.130 weiterzugeben? 15:34.130 --> 15:36.350 Ich muss ja nur eine Information weitergeben. 15:36.410 --> 15:37.730 Wie kodiere ich meine Information? 15:38.030 --> 15:39.030 Das ist die Frage dabei. 15:39.810 --> 15:42.230 Muss ich da wirklich die Zahl, die Identitäten weiterschicken? 15:42.570 --> 15:44.330 Oder kann ich irgendwas anderes weiterschicken? 15:45.310 --> 15:46.950 Und das werden wir gleich noch sehen, wie man das macht. 15:47.210 --> 15:50.530 Im besten Fall habe ich 3N-1 Nachrichten. 15:51.510 --> 15:56.410 Im besten Fall läuft nur die kleinste Nachricht ganz rum. 15:57.550 --> 15:59.850 Die negative Nachricht läuft nochmal ganz rum. 16:00.850 --> 16:06.870 Und jeder, das sind 2N-1 Nachrichten, und jeder hat zu Anfang einmal 16:06.870 --> 16:08.990 eine Nachricht verschickt, das sind 3N-1 Nachrichten. 16:09.630 --> 16:13.370 Das wäre also der beste Fall, nur 3N-1 Nachrichten. 16:15.630 --> 16:18.250 Gut, das war der eine Ausweg. 16:18.330 --> 16:21.710 Wir gehen später noch daran, das zu reduzieren auf N log N. 16:23.050 --> 16:27.070 Anderer Ausweg ist, ich kann das ja auch probabilistisch machen. 16:27.590 --> 16:29.110 Warum muss ich das deterministisch machen? 16:29.110 --> 16:30.250 Ich kann es ja probabilistisch machen. 16:30.310 --> 16:31.870 Dann machen die nicht unbedingt alle das Gleiche. 16:32.930 --> 16:36.150 Und hier ist die Idee, alle Prozessoren sind nach wie vor identisch. 16:38.070 --> 16:43.010 Jeder Prozess, ist jetzt erstmal eine Annahme, kennt die Gesamtzahl 16:43.010 --> 16:44.630 aller beteiligten Prozesse. 16:44.730 --> 16:46.930 Das war bei dem anderen Verfahren nicht notwendig. 16:48.570 --> 16:52.710 Bei dem ersten Ausweg brauchten wir nicht zu wissen, wie viele da 16:52.710 --> 16:53.070 sind. 16:53.930 --> 16:56.710 Wir mussten nur wissen, die sind über einen Ring verbunden. 16:56.850 --> 16:58.570 Jeder kennt seinen Vorgänger und Nachfolger. 16:59.770 --> 17:01.210 Und mehr müssen die nicht wissen. 17:02.230 --> 17:03.990 Die müssen nur darauf warten, dass eine Nachricht, die sie 17:03.990 --> 17:06.410 rausgeschickt haben, irgendwann dazu führt, dass eine Nachricht wieder 17:06.410 --> 17:06.950 reinkommt. 17:08.770 --> 17:12.010 Also wenn ich jetzt aber sage, ich kenne die Anzahl der Prozesse, kann 17:12.010 --> 17:13.770 ich ein bisschen mehr machen, ich habe mehr Informationen. 17:15.550 --> 17:21.550 Und jeder Prozess besitzt einen unabhängigen Zufallszahlengenerator. 17:22.510 --> 17:26.930 Damit habe ich natürlich nicht ein symmetrisches Verfahren. 17:26.930 --> 17:30.410 Sie arbeiten nicht alle gleich, sondern sie haben unabhängige 17:30.410 --> 17:30.930 Zufallszahlengeneratoren. 17:31.650 --> 17:35.910 Das ist eine kleine Abweichung, dass sie eventuell in der Lage sind, 17:36.070 --> 17:38.030 unterschiedliche Zufallszahlen zu erzeugen. 17:38.130 --> 17:39.150 Das nutze ich jetzt aus. 17:39.270 --> 17:44.710 Unterschiedliche Seeds für Pseudo-Zufallszahlengeneratoren, die 17:44.710 --> 17:46.610 brauchen irgendeinen Startwert. 17:47.350 --> 17:50.310 Und die kann sein, dass ich da unterschiedliche Startwerte habe. 17:53.810 --> 17:56.570 Die Reihenfolge der Nachrichten bleibt im Ring erhalten. 17:56.570 --> 18:00.510 Auch das nehme ich an, dass man die in der gleichen Reihenfolge 18:00.510 --> 18:04.130 erhält, wie sie verschickt wurden. 18:04.370 --> 18:06.810 Wenn ich einen Ring habe, sollte das aber eigentlich kein Problem 18:06.810 --> 18:07.230 sein. 18:08.450 --> 18:11.210 Der Algorithmus sieht jetzt so aus, ganz ähnlich wie vorher. 18:12.170 --> 18:13.030 Das stimmt nicht ganz. 18:13.510 --> 18:14.330 Entschuldigung, anders. 18:15.590 --> 18:17.650 Hier habe ich jetzt folgendes Verfahren. 18:19.910 --> 18:29.810 Ich nehme an, dass meine Prozesse irgendwie Werte von 1 bis K haben 18:29.810 --> 18:36.350 und ich habe eine Liste von irgendwelchen Zahlen aus dem Bereich 1 bis 18:36.350 --> 18:38.710 K, wobei K irgendeine große Zahl ist. 18:40.390 --> 18:42.550 Und diese Liste ist zu Anfang leer. 18:43.230 --> 18:46.050 In der Liste will ich jetzt Folgendes aufsammeln. 18:46.050 --> 18:51.330 Jeder Prozess wählt zufällig eine Zahl zwischen 1 und K. 18:53.170 --> 18:56.930 Da nutze ich meinen Zufallszahlengenerator aus. 18:57.810 --> 19:01.050 Es macht jeder die gleiche Operation, aber das Ergebnis wird 19:01.050 --> 19:04.270 unterschiedlich sein, weil ich davon ausgehe, dass die unabhängig sind 19:04.270 --> 19:08.950 voneinander und dass sie unterschiedliche Zahlen wählen können, dass 19:08.950 --> 19:10.370 sie unterschiedliche Seeds haben. 19:11.470 --> 19:15.550 Wenn die natürlich alle genau identisch sind, würde es nicht 19:15.550 --> 19:16.050 funktionieren. 19:16.150 --> 19:19.190 Also hier nehme ich an, dass sie nicht ganz gleich sind, sondern dass 19:19.190 --> 19:22.250 die gewisse Informationen haben können, die unterschiedlich sind. 19:23.130 --> 19:25.070 Und dann mache ich Folgendes. 19:26.150 --> 19:32.150 Ich füge den Namen, den ich lokal erzeugt habe, in meine Liste ein. 19:33.550 --> 19:40.190 Dann sende ich den Namen, also ich habe hier den Namen lokal erzeugt, 19:40.210 --> 19:44.650 ich sende den Namen zu meinem Nachfolger, das macht jeder, und 19:44.650 --> 19:49.130 empfange von meinem Nachbarn, also ich schicke erst etwas rüber, der 19:49.130 --> 19:53.370 hier empfängt natürlich dann eine Nachricht. 19:54.150 --> 20:02.070 Und jetzt habe ich also diese variablen Name, oder Name, überschrieben 20:02.070 --> 20:05.310 mit dem Namen, den mein Vorgänger erzeugt hatte. 20:06.070 --> 20:10.010 Und diesen Namen, das geht jetzt hier wieder rein, trage ich in die 20:10.010 --> 20:15.350 Liste ein und so habe ich dann eine Liste von Namen, das sind jetzt 20:15.350 --> 20:22.450 irgendwelche Zahlen, N1, N2, N3, und so weiter, bis N, in dem Fall 20:22.450 --> 20:25.230 muss ich NN sagen, weil ich annahme, ich habe N Prozessoren. 20:26.270 --> 20:33.650 Eine Liste der Länge N, und das wird N-mal gemacht. 20:34.390 --> 20:37.910 Wenn ich es N-mal mache, ich weiß, ich habe N Prozessoren, hat jeder 20:37.910 --> 20:39.330 einen Namen eingetragen. 20:39.330 --> 20:45.610 Und dann schaue ich nach, ob es einen Namen gibt dabei, der nur einmal 20:45.610 --> 20:46.350 auftaucht. 20:48.570 --> 20:52.930 Es kann ja sein, dass mehrere den gleichen zufälligen Namen gefunden 20:52.930 --> 20:54.330 haben oder erzeugt haben. 20:54.950 --> 20:58.070 Ich suche nur einen Namen, der nur einmal auftaucht. 20:59.790 --> 21:03.430 Und dann nehme ich den, hier ist jetzt gesagt worden, der maximale 21:03.430 --> 21:05.930 eindeutige Name in S. 21:08.670 --> 21:13.750 Und jeder Prozessor hat lokal in seine Liste, die er hier führt, 21:14.690 --> 21:17.850 jeweils die ganzen Namen, die an ihm vorbeigelaufen sind, in die Liste 21:17.850 --> 21:18.490 eingetragen. 21:18.570 --> 21:25.410 Das heißt, jeder Prozessor hat diese Liste S mit den Namen N1 bis NN 21:25.410 --> 21:27.630 in unterschiedlichen Reihenfolgen, aber darauf kommt es gar nicht an. 21:28.090 --> 21:32.350 Ich muss ja nur feststellen, gibt es einen Namen, der nur einmal 21:32.350 --> 21:33.130 auftaucht? 21:33.130 --> 21:36.910 Wenn es mehrere Namen gibt, die eindeutig sind, die nur einmal 21:36.910 --> 21:40.530 auftauchen, nehme ich davon das Maximum, könnte auch sein das Minimum, 21:41.490 --> 21:42.610 ist also völlig egal. 21:43.510 --> 21:45.810 Und jeder kann diese Operation durchführen. 21:46.710 --> 21:54.270 Anschließend weiß jeder, welcher Name gewählt wurde. 21:55.410 --> 22:00.170 Wieso weiß jetzt der Prozessor oder ein Prozessor, dass er gewählt 22:00.170 --> 22:00.530 wurde? 22:01.290 --> 22:04.330 Naja, jeder hat einen Namen ausgewählt. 22:05.970 --> 22:11.850 So, jetzt wird der Name rumgeschickt und er überschreibt den durch den 22:11.850 --> 22:13.770 Namen, den er bekommen hat vom Nachbarn. 22:15.870 --> 22:17.690 Und das Ganze wird N-mal gemacht. 22:19.130 --> 22:27.070 Das heißt, als letztes empfängt er den Namen, den er selber verschickt 22:27.070 --> 22:27.370 hat. 22:28.270 --> 22:33.210 Das heißt, der Name, den er als letztes bekommen hat, ist der Name, 22:33.350 --> 22:35.070 den er selbst gewählt hat. 22:36.210 --> 22:40.650 Und wenn er jetzt feststellt, der Name, also die variablen Name oder 22:40.650 --> 22:48.190 Name, hat am Ende genau den Wert wie der maximale eindeutige Name in 22:48.190 --> 22:50.290 S, dann ist er selbst gewählt. 22:51.090 --> 22:56.510 Alle anderen wissen, wen sie jetzt anschreiben müssen, wer also 22:56.510 --> 22:58.570 gewählt wurde zum Anführer. 22:58.670 --> 23:03.470 Der hat dann diesen Namen, der der maximale eindeutige Name in dieser 23:03.470 --> 23:04.050 Liste ist. 23:04.710 --> 23:08.550 Und damit, jeder weiß also, welchen Namen er hier zufällig für sich 23:08.550 --> 23:09.190 gewählt hat. 23:09.830 --> 23:13.530 Das ist nach diesem Durchlauf, nach Ausführung dieser Schleife 23:13.530 --> 23:14.610 erledigt. 23:15.490 --> 23:18.610 Da werden natürlich viele Nachrichten verschickt, quadratischer 23:18.610 --> 23:20.950 Aufwand in der Anzahl der Nachrichten. 23:21.650 --> 23:26.470 Aber ich habe jetzt nicht die Namen verwendet, die ursprünglich die 23:26.470 --> 23:30.710 einzelnen Prozessoren als Identitäten haben, sondern ich nehme solche 23:30.710 --> 23:32.030 zufällig erzeugten Namen. 23:32.650 --> 23:37.170 Das heißt, jeder hatte die gleiche Chance gewählt zu werden, abhängig 23:37.170 --> 23:42.450 davon, welche zufällige Namen er im Prinzip gewählt hat. 23:42.450 --> 23:46.130 Das heißt, hier entscheidet im Prinzip der Zufallszahlengenerator 23:46.130 --> 23:49.970 darüber, wer am Ende dann ausgewählt wird. 23:51.130 --> 23:55.590 Das ist ein populistischer Algorithmus, um dieses Problem zu lösen. 23:56.430 --> 24:05.730 Ein verteilter Algorithmus, der einen Anführer wählt im Ring, ohne 24:05.730 --> 24:07.790 dass man Identitäten tatsächlich ausnutzt. 24:07.790 --> 24:13.570 Aber es ist eben nicht ganz symmetrisch, weil ich annehmen muss, dass 24:13.570 --> 24:16.050 die Zufallszahlengeneratoren tatsächlich unabhängig voneinander 24:16.050 --> 24:19.310 arbeiten und unterschiedliche Werte erzeugen können. 24:21.150 --> 24:22.930 Analyse ist hier nochmal angegeben. 24:23.710 --> 24:28.670 Das Ding ist natürlich vollständig verteilt und symmetrisch, bis eben 24:28.670 --> 24:30.230 auf diesen Zufallszahlengenerator. 24:30.290 --> 24:33.530 Alle Prozesse sind in gleicher Weise beteiligt, haben die gleiche 24:33.530 --> 24:41.270 Chance gewählt zu werden und sie wissen am Ende, wer der Anführer ist, 24:41.350 --> 24:44.010 weil sie alle die gleiche lokale Liste haben, in unterschiedlichen 24:44.010 --> 24:50.450 Reihenfolgen, alle um eins zyklisch verschoben, aber sie haben also im 24:50.450 --> 24:51.510 Prinzip die gleiche Liste. 24:52.590 --> 24:56.390 Und da sie selber am Ende wieder den Namen bekommen, den sie selbst 24:56.390 --> 24:59.950 verschickt haben, wissen sie sofort, ob sie selbst ausgewählt wurden 24:59.950 --> 25:00.490 oder nicht. 25:00.490 --> 25:03.670 Damit ist das also auch einfach festzustellen. 25:04.390 --> 25:06.630 Und die Frage ist, wann terminiert das Ganze? 25:07.250 --> 25:13.230 Es war ja eine Bedingung drin, hier steht, until Mindesteseinnahme nur 25:13.230 --> 25:14.490 einmal vorhanden. 25:15.150 --> 25:17.450 Jetzt ist die Frage, wie sieht das damit aus? 25:18.630 --> 25:23.030 Also wir müssen einfach eine Wahrscheinlichkeit annehmen, dass 25:23.030 --> 25:27.070 Mindesteseinnahme oder ein Prozess einen eindeutigen Namen wählt. 25:27.070 --> 25:30.850 Das hängt natürlich davon ab, wie groß unser K ist, wie viele Namen 25:30.850 --> 25:34.410 habe ich zur Verfügung, wie groß ist die Anzahl der Prozesse, die 25:34.410 --> 25:37.850 jetzt Namen auswählen, was für die Zufallszahlengeneratoren habe ich 25:37.850 --> 25:42.190 hier drin und das bestimmt die Wahrscheinlichkeit, mit der ich jetzt 25:42.190 --> 25:44.790 tatsächlich einen eindeutigen Namen dabei finden kann. 25:45.610 --> 25:49.090 Dann ist die Wahrscheinlichkeit, dass ich nach I Runden nicht fertig 25:49.090 --> 25:50.590 bin, 1 minus p hoch i. 25:51.290 --> 25:55.230 Die Wahrscheinlichkeit dafür, dass ich nach genau I Runden fertig bin, 25:56.110 --> 25:59.230 ist 1 minus 1 minus p hoch i. 26:00.830 --> 26:06.010 Und die Wahrscheinlichkeit, wenn ich das jetzt lang genug mache, ist 26:06.010 --> 26:09.330 also die Wahrscheinlichkeit, dass das nicht terminiert, gleich 0, weil 26:09.330 --> 26:12.890 ich das eben hier durch Anzahl der Runden beliebig klein kriegen kann, 26:12.990 --> 26:16.610 solange die Wahrscheinlichkeit dafür, dass mindestens ein Prozess 26:16.610 --> 26:19.010 einen eindeutigen Namen wählt, größer als 0 ist. 26:19.810 --> 26:23.670 Also damit wird dieser Algorithmus garantiert irgendwann terminieren. 26:24.270 --> 26:28.310 Ich kann nicht genau sagen, wann er terminiert, aber er wird 26:28.310 --> 26:28.810 terminieren. 26:29.430 --> 26:33.510 Also das ist eine Alternative zu dem deterministischen Verfahren. 26:34.910 --> 26:39.970 Typischer Ausweg aus solchen Unmöglichkeitsbeweisen, dass ein 26:39.970 --> 26:45.450 deterministischer Algorithmus nicht die Aufgabe erfüllen kann, wie bei 26:45.450 --> 26:48.310 den Philosophenproblemen oder was wir gerade gesehen haben bei dem 26:48.310 --> 26:52.670 Satz von Angloin, typischer Ausweg ist, das randomisiert zu machen. 26:55.010 --> 26:57.750 Insgesamt n Quadratnachrichten pro Wahlvorgang, das ist auch klar, 26:58.290 --> 27:02.830 weil ja jeder in jedem Schritt dort Nachrichten verschickt, n mal n 27:02.830 --> 27:04.930 Nachrichten und dann bin ich fertig. 27:05.530 --> 27:07.450 Da habe ich keine Möglichkeit, das zu reduzieren. 27:09.510 --> 27:14.090 Ohne Kenntnis der Zahl der beteiligten Prozessoren habe ich natürlich 27:14.090 --> 27:20.490 keine Möglichkeit zu wissen, wann ich alle zufällig gewählten Namen 27:20.490 --> 27:21.290 erhalten habe. 27:22.630 --> 27:26.230 Also ich kann nicht dadurch, dass ein Name nochmal geschickt wird, 27:26.310 --> 27:28.970 annehmen, jetzt sind alle Nachrichten verschickt worden. 27:29.990 --> 27:33.730 Jetzt könnten ja die gleichen Namen oder Prozessoren die gleichen 27:33.730 --> 27:34.430 Namen haben. 27:35.270 --> 27:39.270 Also ich muss irgendwas wissen, wie viele Prozesse sind eigentlich 27:39.270 --> 27:39.770 beteiligt. 27:39.850 --> 27:43.950 Ich muss ne Information haben, um festzustellen, ich habe jetzt alle 27:43.950 --> 27:48.750 Namen von allen Prozessen tatsächlich bekommen, alle diese zufällig 27:48.750 --> 27:49.510 gewählten Namen. 27:51.910 --> 27:55.790 Und ich könnte aber, also das ist, ich glaube ich brauche irgendeine 27:55.790 --> 27:56.250 Information. 27:58.070 --> 28:00.190 Jetzt kann ich aber auch ein bisschen anders vorgehen, das habe ich 28:00.190 --> 28:01.130 hier nochmal angedeutet. 28:01.130 --> 28:06.770 Ich könnte sagen, wenn die Prozesse oder Prozessoren eindeutige Namen 28:06.770 --> 28:07.230 haben. 28:07.870 --> 28:09.610 Wir nehmen mal an, die sind durchnummeriert irgendwie. 28:09.750 --> 28:12.650 Ich darf nur die Identität verwenden für die Auswahl des Leiters. 28:13.610 --> 28:19.170 Aber ich könnte ja die Information verwenden, um festzustellen, ob ich 28:19.170 --> 28:20.630 bereits einmal rumgelaufen bin. 28:22.350 --> 28:26.570 Das heißt, man kann dann einen modifizierten Algorithmus angeben, der 28:26.570 --> 28:29.870 nach dem Prinzip vorgeht, wie hier in dem probabilistischen 28:29.870 --> 28:30.890 Algorithmus angegeben. 28:32.110 --> 28:35.830 Aber dann brauche ich die Anzahl der Prozesse nicht zu kennen. 28:38.130 --> 28:43.970 Und ich werde dabei diese Namen oder die Identitäten der Prozessoren 28:43.970 --> 28:46.770 nicht bei der Wahl des Anführers verwenden. 28:47.410 --> 28:49.410 Die beeinflussen nicht, wer ausgewählt wird. 28:49.510 --> 28:55.030 Die beeinflussen nur, dass ich weiß, jetzt bin ich einmal rum und kann 28:55.030 --> 28:55.710 weitermachen. 28:55.710 --> 28:57.790 Da können Sie sich leicht überlegen, wie man das macht. 28:57.850 --> 28:59.370 Hat einer eine Idee, wie man das machen könnte? 29:00.750 --> 29:00.830 Ja? 29:02.510 --> 29:02.690 Bitte? 29:06.930 --> 29:08.630 Genau, ganz einfache Idee. 29:08.990 --> 29:11.650 Ich schicke praktisch zwei Informationen rum, nicht eine Information. 29:12.210 --> 29:17.690 Ich habe dann immer Paare von Eat und Name und damit habe ich es 29:17.690 --> 29:17.890 schon. 29:18.870 --> 29:19.830 Ganz einfach zu machen. 29:20.030 --> 29:24.430 Also diese Annahme mit der Kenntnis der Zahl, das kann man auch 29:24.430 --> 29:24.910 weglassen. 29:24.910 --> 29:27.750 Dann muss ich allerdings etwas mehr Informationen verschicken. 29:28.750 --> 29:30.750 Okay, das dazu. 29:31.410 --> 29:34.850 Und jetzt kommen wir in den letzten Minuten von heute noch dazu, wie 29:34.850 --> 29:38.130 man die Zahl der auszutauschenden Nachrichten reduzieren kann. 29:38.230 --> 29:39.690 Oder die Kommunikationsaufwand. 29:39.750 --> 29:43.590 Ich hätte gesagt, wir wollen von n² irgendwie runter auf n log n. 29:45.790 --> 29:52.250 Und wir nehmen jetzt nochmal an, dass jeder eine eindeutige Identität 29:52.250 --> 29:54.810 hat, wie bei dem Verfahren, das ich als ersten Ausdruck dargestellt 29:54.810 --> 29:55.230 habe. 29:55.850 --> 30:02.250 Ich möchte einen beliebigen, Quatsch, ich möchte einen Prozess 30:02.250 --> 30:03.670 kleinster Identität auswählen. 30:04.550 --> 30:07.690 Und irgendeiner stößt den Prozess an. 30:08.310 --> 30:11.090 Könnte auch von Beliebigen, von allen angestoßen werden. 30:11.150 --> 30:12.130 Das ist ziemlich egal. 30:12.710 --> 30:16.070 Die müssen nur irgendwann dazu aufgefordert werden, dass sie ihre 30:16.070 --> 30:18.990 Nachricht rausschicken, sie aufgeweckt werden können. 30:19.870 --> 30:22.650 Und ich nehme an, dass die als Ring verbunden sind. 30:23.190 --> 30:24.530 Ganz einfache Topologie. 30:25.770 --> 30:28.570 Man kann das alles auch betrachten für andere Strukturen. 30:29.710 --> 30:32.290 Beliebige Verbindungsstrukturen, für Bäume, für Gitter, für was immer 30:32.290 --> 30:33.050 Sie haben wollen. 30:34.050 --> 30:37.550 Ringe sind eine sehr einfache Struktur und nur für die will ich es 30:37.550 --> 30:38.150 hier betrachten. 30:38.690 --> 30:41.670 Aber wie gesagt, man kann das auch übertragen auf andere Situationen. 30:42.050 --> 30:47.110 Da muss man nur ein bisschen andere Algorithmen erzeugen, die leichte 30:47.110 --> 30:49.190 Modifikationen sind von dem, was ich hier mache. 30:50.070 --> 30:52.510 Und jetzt habe ich also hier meinen Algorithmus, den ich Ihnen vorher 30:52.510 --> 30:53.410 schon gezeigt habe. 30:55.650 --> 31:01.770 Ich schicke einfach meine Identität rum und wann immer ich einen 31:01.770 --> 31:05.130 kleineren Namen bekomme oder es geschickt bekomme, als meine eigene 31:05.130 --> 31:07.890 Identität ist, schicke ich die weiter, ansonsten vergesse ich die 31:07.890 --> 31:08.290 Nachricht. 31:10.770 --> 31:13.870 Und man kann sofort sich ein paar Dinge überlegen, wie man das 31:13.870 --> 31:14.530 verbessern kann. 31:15.460 --> 31:20.150 Also die erste Verbesserung wäre, dass ich Folgendes mache. 31:21.570 --> 31:30.110 Ich vergleiche nicht nur mit der eigenen Identität, sondern mit der 31:30.110 --> 31:32.070 kleinsten bisher erhaltenen Nachricht. 31:45.160 --> 31:48.980 Das war einfach zu machen. 31:49.540 --> 31:52.300 Hier würde ich eben nicht vergleichen mit der eigenen Identität, 31:52.460 --> 31:56.460 sondern ich würde vergleichen mit der letzten Nachricht, die ich habe, 31:56.800 --> 32:03.340 immer wieder mir merken, das aktuelle Minimum, das ich lokal gesehen 32:03.340 --> 32:04.840 habe, mit dem vergleiche ich. 32:05.600 --> 32:09.620 Dadurch könnte ich schon die Anzahl der Nachrichten reduzieren, weil 32:09.620 --> 32:13.740 ich dann mit einem kleineren Wert vergleiche. 32:14.340 --> 32:17.800 Das würde die mittlere Zahl ein bisschen verbessern, aber kaum den 32:17.800 --> 32:18.600 schlechtesten Fall. 32:19.920 --> 32:22.700 Die Frage ist, kann man sich auf einen einzigen Initiator beschränken? 32:22.820 --> 32:26.180 Das wäre ein bisschen schwierig, denn dann hätte man keinen 32:26.180 --> 32:27.520 symmetrischen Algorithmus. 32:29.940 --> 32:33.240 Also müssen ja im Prinzip alle gleichmäßig anfangen können. 32:35.200 --> 32:38.940 Wenn man sich beschränken könnte auf einen Initiator in einem solchen 32:38.940 --> 32:42.320 verteilten Algorithmus auf einem Ring, dann hätte man ja schon einen 32:42.320 --> 32:42.900 Anführer. 32:43.980 --> 32:46.260 Derjenige, der beginnt, der wird einfach der Anführer. 32:46.760 --> 32:47.880 Und dann wäre man schon fertig. 32:48.760 --> 32:53.220 Also wir müssen davon ausgehen, das sind alles beliebige Prozessoren. 32:53.220 --> 32:57.640 Also wenn ich nur einen hätte, der das anstößt, dann würde ja nur eine 32:57.640 --> 32:59.520 Nachricht praktisch da einmal rumlaufen. 32:59.740 --> 33:02.900 Alle könnten sofort kontrollieren, ist das eine kleinere als die 33:02.900 --> 33:06.540 eigene und würden ihre eigene Nachricht nur dann weiterschicken, wenn 33:06.540 --> 33:10.040 das, was kommt, größer ist als die eigene Nachricht. 33:11.560 --> 33:17.000 Insofern könnte man das deutlich reduzieren, aber wir können das so 33:17.000 --> 33:17.600 nicht annehmen. 33:19.040 --> 33:24.240 Das wäre aber durchaus eine Verbesserung oder eine Möglichkeit, wenn 33:24.240 --> 33:27.060 die eben nicht alle gleichzeitig anfangen, sondern wenn es wenige 33:27.060 --> 33:29.980 gibt, die jetzt das anstoßen, dann werden die durch die 33:29.980 --> 33:32.660 Anstoßnachricht bekommen sie schon die Identität desjenigen, den es 33:32.660 --> 33:37.960 angestoßen hat und sie geben dann nur die Nachricht weiter, die 33:37.960 --> 33:40.860 Identität weiter, wenn sie kleiner ist, ansonsten geben sie die eigene 33:40.860 --> 33:41.680 Identität weiter. 33:43.900 --> 33:47.320 So, weitere Annahme, was nehmen wir noch an? 33:48.260 --> 33:53.160 Das verteilte System arbeitet synchron, das heißt, die Prozesse 33:53.160 --> 33:54.800 arbeiten in Kommunikationsrunden. 33:54.860 --> 33:56.260 Das ist eine starke Annahme. 33:57.320 --> 34:01.440 Bisher haben wir nämlich nicht angenommen, dass die tatsächlich alle 34:01.440 --> 34:02.340 gleichzeitig arbeiten. 34:02.440 --> 34:05.300 Ich habe das so dargestellt in der Animation, als wenn das alles 34:05.300 --> 34:08.440 gleichzeitig passiert, aber jetzt muss das nicht mehr so sein. 34:09.400 --> 34:16.280 Wenn die nicht gleichzeitig arbeiten würden, wäre das ein anderer 34:16.280 --> 34:16.620 Fall. 34:16.960 --> 34:19.520 Wir nehmen an, die arbeiten in Kommunikationsrunden. 34:20.480 --> 34:26.020 Sie wissen alle, sie haben eine globale Zeit und dadurch kann ich 34:26.020 --> 34:27.620 jetzt Folgendes machen. 34:28.500 --> 34:33.660 Ich verzögere den Versand einer Nachricht X um F von X Runden. 34:38.010 --> 34:40.530 Jetzt muss ich mir überlegen, was für eine Funktion F wähle ich dann 34:40.530 --> 34:40.830 dafür. 34:41.070 --> 34:41.930 Das schauen wir uns gleich an. 34:43.870 --> 34:48.010 Voraussetzung ist, dass jeder Prozess eine Nachricht verschicken kann, 34:48.090 --> 34:48.910 er muss aber nicht. 34:49.530 --> 34:50.950 Er kann auch warten damit. 34:51.830 --> 34:54.170 Er muss nicht in jeder Runde eine Nachricht rausschicken. 34:55.090 --> 34:57.750 Wenn ich also keine Nachricht bekomme innerhalb der Zeit für eine 34:57.750 --> 34:59.650 Runde, weiß ich, der hat mir keine Nachricht geschickt. 35:00.970 --> 35:04.210 Ich gehe also davon aus, dass keiner, wenn also eine Nachricht nicht 35:04.210 --> 35:06.630 kommt, gehe ich davon aus, die ist nicht verschickt worden. 35:07.170 --> 35:08.190 Das ist kein Fehlerfall. 35:09.350 --> 35:13.610 In jeder Runde prüft der Prozess, ob Nachrichten angekommen sind. 35:14.610 --> 35:18.710 Ich muss also nicht in jeder Runde von allen Nachbarn, also von dem 35:18.710 --> 35:21.630 einen Nachbarn, man kann das auch auf eine allgemeinere Struktur 35:21.630 --> 35:24.210 übertragen, Nachrichten bekommen haben. 35:25.350 --> 35:27.210 Was heißt das für den Algorithmus? 35:28.010 --> 35:33.230 Die Anzahl der Runden ist die, sagen wir mal T. 35:34.230 --> 35:37.510 M ist die minimale Identität unter allen Identitäten, die da sind. 35:39.030 --> 35:45.550 Ich habe maximal N Runden, ich habe ja N Prozessoren, bis der Prozess 35:45.550 --> 35:47.530 M angestoßen wird. 35:48.690 --> 35:54.490 Also wenn der, ich habe hier meinen Ring, wenn der hier anfängt und 35:54.490 --> 35:57.430 nach rechts rüberschickt, das dauert ja eine Weile, bis der angestoßen 35:57.430 --> 35:58.430 wird, dass er was tun soll. 36:00.750 --> 36:03.910 Also diese Anstoßnachricht, die läuft da einmal rum, das sind N 36:03.910 --> 36:07.410 Runden, bis der Prozess angestoßen wird, dass er seine Nachricht 36:07.410 --> 36:07.890 verschickt. 36:10.270 --> 36:14.410 Dann muss die Nachricht einmal rumlaufen. 36:15.490 --> 36:21.210 Einmal rumlaufen heißt, ich muss N mal F von M Runden abwarten. 36:22.170 --> 36:25.190 F von M war die Anzahl der Runden, die ich warte, bis ich eine 36:25.190 --> 36:25.990 Nachricht verschicke. 36:26.550 --> 36:29.610 Bis die Nachricht M wieder von Prozess M empfangen wird. 36:29.730 --> 36:30.970 Muss einmal rumgelaufen sein. 36:32.710 --> 36:35.990 Und dann brauche ich noch N Runden für die Abschlussnachricht. 36:36.550 --> 36:40.550 Das Minus X, das einmal rumläuft und allen mitteilt, oder das Minus M 36:40.550 --> 36:43.030 in dem Fall, dass der Prozess M gewählt wurde. 36:44.790 --> 36:49.430 Das heißt, meine Zeit insgesamt ist N mal F von M plus 2. 36:49.430 --> 36:54.390 Diese N Runden für das Anstoßen, N Runden für die Abschlussnachricht, 36:54.750 --> 37:01.730 N mal F von M Runden hier für das Durchlaufen der minimalen Nachricht. 37:02.790 --> 37:04.970 Und dann gibt es noch Anzahl Verlierer Nachrichten. 37:05.690 --> 37:08.250 Das sind gerade alle anderen Nachrichten. 37:10.570 --> 37:19.210 Also für alle größeren Nachrichten sind so zu viele Nachrichten, die 37:19.210 --> 37:23.490 verschickt wurden, T durch F von I, das sind die Nachrichten, die in 37:23.490 --> 37:27.810 der Zeit T verschickt worden sein können, für diese größeren Werte. 37:29.670 --> 37:32.450 Die werden verloren gehen. 37:33.530 --> 37:35.830 Und das T ist N mal F von M plus 2. 37:36.350 --> 37:40.310 Das durch F von I und ich stelle fest, wenn ich jetzt das F von X als 37:40.310 --> 37:48.690 2 hoch X wähle, dann ist die Anzahl aller Nachrichten, das ist nach 37:48.690 --> 37:54.210 wie vor ein O von N, und die Anzahl aller Nachrichten-Bits, die ich 37:54.210 --> 38:02.050 schicke, die ist dann in O von N mal Log N. 38:06.030 --> 38:11.070 Ich schicke ja, also die Anzahl der Nachrichten-Bits ist klar, die 38:11.070 --> 38:14.590 Nachrichtenlänge ist gerade Log N, weil ich da nur diese N 38:14.590 --> 38:15.990 verschiedenen Identitäten habe. 38:16.950 --> 38:24.070 Und ich habe insgesamt dann nur noch O von N Nachrichten übrig. 38:24.910 --> 38:30.210 Dadurch, dass ich hier das F von M geeignet gewählt habe, so viele 38:30.210 --> 38:31.670 Nachrichten gehen verloren. 38:32.750 --> 38:36.690 Die eine Nachricht muss einmal rumlaufen und ich habe dann insgesamt 38:36.690 --> 38:41.370 eine lineare Anzahl von Nachrichten hiermit erreicht. 38:41.370 --> 38:42.850 Wir sind damit durch. 38:43.030 --> 38:46.330 Ich werde an der Stelle wieder einsetzen beim nächsten Mal, das 38:46.330 --> 38:50.470 nochmal wieder aufgreifen und dann machen wir noch die restlichen 38:50.470 --> 38:51.310 Folien fertig. 38:52.210 --> 38:54.150 Und es sind noch ein paar Sachen, die ich erzählen möchte, 38:54.190 --> 38:56.570 insbesondere über eine untere Schranke, die wir brauchen, um 38:56.570 --> 39:00.330 tatsächlich in so einem Ring den Anführer zu wählen. 39:05.660 --> 39:09.460 Jetzt kodiere ich einfach den Inhalt einer Nachricht durch die 39:09.460 --> 39:10.340 Übertragungszahl. 39:12.040 --> 39:13.440 Wie kann ich das machen? 39:14.260 --> 39:15.360 Ich arbeite ja in diesen Runden. 39:15.980 --> 39:16.980 Das ist immer noch die Annahme. 39:18.120 --> 39:21.600 Ich sende einfach eine Nachricht X mit der folgenden Prozedur. 39:23.240 --> 39:27.500 Wenn ich also X verschicken will, dann sende ich eine Nachricht Open 39:27.500 --> 39:30.280 an den nächsten Nachbarn. 39:31.960 --> 39:37.340 Und ich setze einen Zähler auf X. 39:37.700 --> 39:39.260 Einen internen Zähler auf X. 39:44.570 --> 39:50.150 Und dann werden in jeder Runde folgende Operationen ausgeführt. 39:50.750 --> 39:54.310 Der Send-Timer wird um 1 reduziert. 39:54.730 --> 39:56.410 In jeder Runde 1 runtergezählt. 39:57.170 --> 40:02.770 Ein Receive-Timer, ein weiterer Zähler, den wir noch nicht gesehen 40:02.770 --> 40:05.790 haben, der wird um 1 erhöht. 40:06.570 --> 40:13.370 Vorgriff, wenn ich die Open-Nachricht irgendwo empfange, ein 40:13.370 --> 40:13.730 Prozess... 40:14.130 --> 40:18.090 Also dieser hier hat das losgeschickt, der hat also hier den Send 40:18.090 --> 40:21.690 -Timer auf X gesetzt. 40:21.690 --> 40:30.810 Dieser hier bekommt die Open-Nachricht, der setzt den Receive-Timer 40:30.810 --> 40:32.910 auf 0. 40:34.570 --> 40:41.950 Und jetzt erhöht jeder den lokalen Wert des Receive-Timers um 1. 40:43.710 --> 40:49.030 Das heißt, wenn ich ein Open bekommen habe, habe ich zunächst mal auf 40:49.030 --> 40:53.350 0 gesetzt und zähle jetzt Runden weiter, erhöhe immer den Receive 40:53.350 --> 40:54.210 -Timer um 1. 40:54.810 --> 40:58.930 Derjenige, der rausgeschickt hat, reduziert den Send-Timer um 1. 40:58.930 --> 41:02.930 Und nach X Runden ist... 41:06.410 --> 41:08.890 Das kommt jetzt noch irgendwann da. 41:09.170 --> 41:15.110 Wenn der Send-Timer gleich 0 ist, dann wird eine Close-Nachricht an 41:15.110 --> 41:15.890 den Nächsten geschickt. 41:17.810 --> 41:21.550 Das heißt, ich habe jetzt das Ganze codiert, dadurch dass ich zu 41:21.550 --> 41:27.570 irgendeinem Zeitpunkt eine Open-Nachricht schicke und irgendwann 41:27.570 --> 41:33.070 später eine Close-Nachricht und diese Zeitspanne hier ist X. 41:35.310 --> 41:38.350 Das heißt, dadurch, dass ich einfach zähle, wie viele Runden es 41:38.350 --> 41:41.990 dauert, bis ich das Close bekomme nach einem Open, weiß ich, welcher 41:41.990 --> 41:43.090 Wert verschickt werden soll. 41:44.310 --> 41:48.130 Ich habe aber nur zwei verschiedene Nachrichten. 41:48.650 --> 41:50.470 Dafür würde ein Bit ausreichen. 41:52.630 --> 41:53.190 Ja? 41:55.910 --> 42:01.310 Wir müssen dann natürlich noch dafür sorgen, dass das Ganze auch 42:01.310 --> 42:02.530 irgendwann beendet wird. 42:03.070 --> 42:05.210 Dafür wird noch eine Stopp-Nachricht verschickt, das ist die dritte 42:05.210 --> 42:05.670 Nachricht. 42:06.410 --> 42:09.090 Ich werde hier insgesamt drei verschiedene Nachrichten verschicken. 42:09.670 --> 42:12.810 Open, Close und Stopp. 42:13.630 --> 42:16.710 Das heißt, ich habe zwei Bits, die ich brauche, um diese drei 42:16.710 --> 42:17.790 Nachrichten zu unterscheiden. 42:18.930 --> 42:24.470 Und auf diese Art und Weise, dass ich zähle, wie lange muss ich warten 42:24.470 --> 42:27.030 nach dem Verschicken einer Open-Nachricht, bis ich die Close-Nachricht 42:27.030 --> 42:32.630 verschicke, beziehungsweise wie lange dauert es beim Empfänger vom 42:32.630 --> 42:37.030 Erhalt der Open-Nachricht, bis die Close-Nachricht kommt, habe ich den 42:37.030 --> 42:39.090 Wert, der verschickt werden sollte, kodiert. 42:39.790 --> 42:44.270 Das ist eine Standardart, wie man den Kommunikationsaufwand reduzieren 42:44.270 --> 42:44.610 kann. 42:44.730 --> 42:47.230 Da wird alles einfach in die Zeit kodiert. 42:49.250 --> 42:55.090 So, und wenn ich das jetzt alles verbessere zu neuem Algorithmus, dann 42:55.090 --> 42:59.270 würde ich also zunächst mal, wenn ich den Prozessor I habe, habe ich 42:59.270 --> 43:03.090 vorhin mal It genannt, nenne ich jetzt nur I, ich setze also die 43:03.090 --> 43:12.670 Variable Min auf I und irgendeiner fängt an und verschickt diese 43:12.670 --> 43:15.910 Nachricht I nach diesem Verfahren mit Open und Close. 43:18.550 --> 43:22.110 Das macht er entweder spontan oder er bekommt eben selber, er wird 43:22.110 --> 43:25.230 angestoßen dadurch, dass eine Nachricht rausgeschickt wurde und 43:25.230 --> 43:28.750 verschickt dann, wenn er angestoßen wurde, zunächst mal seine eigene 43:28.750 --> 43:29.290 Identität. 43:32.810 --> 43:36.310 Dann wartet er ja auch auf andere Nachrichten, also er macht ein 43:36.310 --> 43:43.310 Accept X, vorher hatten wir gesagt Receive, Accept X, muss er sehen, 43:43.670 --> 43:45.770 wie bekomme ich tatsächlich diese Nachricht X. 43:46.510 --> 43:51.350 Wenn also das X, das ist das gleiche wie vorher im Prinzip, wenn das X 43:51.350 --> 43:59.440 kleiner als Min ist, dann setze ich Min auf X, das ist das, was wir 43:59.440 --> 44:03.340 als erste Verbesserung hatten, ich vergleiche immer mit der kleinsten 44:03.340 --> 44:12.740 bisher bekommenen Identität, setze den Election Timer auf F on X, das 44:12.740 --> 44:18.600 heißt, ich habe so viele Runden, die ich warte, bis tatsächlich etwas 44:18.600 --> 44:21.140 verschickt wird, das ist das F on X, 44:24.860 --> 44:32.200 dann, wenn das X gleich I ist, also nicht kleiner als das Minimum, 44:33.420 --> 44:38.080 wenn das X gleich der eigenen Identität ist, dann weiß ich, das Ganze 44:38.080 --> 44:40.380 ist fertig, versende ich diese Stopp-Nachricht. 44:42.320 --> 44:45.540 Und ich merke mir, dass ich ausgewählt wurde. 44:46.840 --> 44:50.100 Diese Stopp-Nachricht wird nicht verzögert, die wird sofort 44:50.100 --> 44:50.780 rausgeschickt. 44:54.200 --> 44:58.460 Die X-Nachricht hier, die wird eben erst nach F on X Runden 44:58.460 --> 44:58.720 rausgeschickt. 44:59.640 --> 45:02.660 Das ist das Ganze, das mache ich, wenn ich also einen Wert X empfangen 45:02.660 --> 45:06.300 habe, dadurch, dass ich Open und Close bekommen habe, dann habe ich 45:06.300 --> 45:08.760 damit das X insgesamt bekommen. 45:10.080 --> 45:15.200 Dann muss ich mir noch anschauen, was passiert, wenn ich da die Stopp 45:15.200 --> 45:16.000 -Nachricht bekomme. 45:17.500 --> 45:31.740 Wenn die eigene Identität größer ist als die minimale Identität, dann 45:31.740 --> 45:34.580 sendet man Stopp an den Nachbarn. 45:35.500 --> 45:41.140 Also hier verschicke ich nicht, wie vorher bei dem Election 45:41.140 --> 45:49.660 -Algorithmus, die negative Identität, sondern ich sage, wenn die 45:49.660 --> 45:57.040 eigene Identität größer ist als die minimale bisher gesehene, dann 45:57.040 --> 46:04.180 weiß ich, ich bin fertig, bin nicht gewählt. 46:04.820 --> 46:08.960 Und das Min, der aktuelle Wert von Min, ist die Identität des 46:08.960 --> 46:10.440 Kleinsten, der gewählt wurde. 46:11.440 --> 46:15.540 Weil ja diese kleinste Identität einmal rumgelaufen sein muss, das 46:15.540 --> 46:22.140 heißt, jeder hat diese kleinste Identität als Min lokal abgespeichert 46:22.140 --> 46:28.060 und damit kennt er die Identität desjenigen, der gewählt wurde. 46:28.700 --> 46:36.600 Er sendet dann Stopp an den Nächsten und ist natürlich nicht 46:36.600 --> 46:37.260 ausgewählt. 46:38.620 --> 46:47.620 Und zu Beginn jeder Runde muss der Election-Timer um eins reduziert 46:47.620 --> 46:52.180 werden, der zählt, wie lange ich warten muss, um überhaupt eine 46:52.180 --> 46:53.140 Nachricht rauszuschicken. 46:53.940 --> 47:00.520 Und wenn dieser Election-Timer Null ist, dann verschicke ich die Min 47:00.520 --> 47:01.040 -Nachricht. 47:01.180 --> 47:09.480 Die Min-Nachricht war hier auf X gesetzt worden, der Wert, der 47:09.480 --> 47:12.760 verschickt werden sollte, weil er kleiner war als das, was ich bisher 47:12.760 --> 47:13.900 als Minimum gesehen hatte. 47:14.760 --> 47:16.760 Das wird verschickt mit Transmit. 47:17.480 --> 47:21.940 Transmit war ja gerade das, dass ich ein Open rausschicke, ein Send 47:21.940 --> 47:28.600 -Timer setze und dann warte, bis der Send-Timer auf Null ist, sodass 47:28.600 --> 47:34.040 ich dann am Ende nach Min-Runden das Close verschicken kann. 47:34.800 --> 47:39.180 Und dann habe ich eigentlich alle Komponenten, die ich brauche, um 47:39.180 --> 47:45.340 diesen Lieder-Election-Algorithmus in dieser verbesserten Form 47:45.340 --> 47:46.140 durchzuführen. 47:46.640 --> 47:49.120 Und jetzt muss man sehen, was hat das für eine Auswirkung auf die 47:49.120 --> 47:52.580 Gesamtzeit meines Verfahrens und auf die Gesamt-Nachrichten 47:52.580 --> 47:53.200 -Komplexität. 47:54.100 --> 47:57.640 Ich habe also nur drei verschiedene Nachrichten, Open, Close, Stop. 47:58.220 --> 48:00.460 Das heißt, es reichen zwei Bit aus. 48:02.820 --> 48:04.560 Das mehr braucht nichts verschicken. 48:05.540 --> 48:09.120 Ich verschicke nur die jeweils kleinste empfangende Identität und 48:09.120 --> 48:10.020 eventuell die eigene. 48:13.390 --> 48:16.930 Also das ist auch klar, die eigene wurde auf jeden Fall immer 48:16.930 --> 48:17.330 verschickt. 48:18.070 --> 48:21.650 Die Korrektheit ergibt sich aus der Korrektheit des ursprünglichen 48:21.650 --> 48:22.470 Algorithmus. 48:24.550 --> 48:27.230 An dem groben Algorithmus habe ich ja gar nichts geändert. 48:27.410 --> 48:31.190 Ich habe nur die Ausführung der einzelnen Operationen etwas verändert. 48:32.110 --> 48:38.070 Dieser Prozess M, der kleinste, verschluckt alle anderen Nachrichten. 48:39.350 --> 48:41.990 Das heißt, der wird sich durchsetzen, alle anderen werden nicht 48:41.990 --> 48:42.350 weitergeschickt. 48:44.770 --> 48:47.270 Da diese Nachrichten X größer sind. 48:48.410 --> 48:53.190 Dieses M wird, nicht sofort, aber wird nach F von M Runden 48:53.190 --> 48:53.990 weitergegeben. 48:57.130 --> 49:00.370 Und der Prozess M geht also irgendwann, bzw. 49:01.790 --> 49:05.590 nachdem es einmal rumgelaufen ist, in den Status Selected über und 49:05.590 --> 49:06.750 versendet die Stopp-Nachrichten. 49:07.650 --> 49:09.730 Das ist also genau das, was wir vorher auch hatten. 49:10.750 --> 49:13.990 Die Ausführungszeit verändert sich jetzt etwas. 49:14.810 --> 49:18.550 Wir haben X plus 1 Runden, um die Nachricht X zu verschicken. 49:18.550 --> 49:24.550 Wir schicken das Open raus, warten X Runden ab und schicken das Close 49:24.550 --> 49:24.930 raus. 49:27.010 --> 49:33.990 Und das heißt, die Gesamtzeit ist jetzt denmal F von M plus, jetzt 49:33.990 --> 49:37.730 nicht einfach 2, sondern wir müssen noch das M mit dazu zählen, weil 49:37.730 --> 49:40.270 wir nicht eine Runde brauchen, um die Nachricht X zu verschicken, 49:40.430 --> 49:41.810 sondern X plus 1 Runden. 49:42.710 --> 49:45.970 Für M, also das M noch obendrauf. 49:45.970 --> 49:52.810 Und die Anzahl der Nachrichten insgesamt ist dann, also für alle 49:52.810 --> 49:58.230 Nachrichten ist es so, dass ich F von I plus I minus 1 Takte brauche 49:58.230 --> 50:01.010 oder Runden brauche, um eine Nachricht tatsächlich verschickt zu 50:01.010 --> 50:03.710 haben, vollständig, inklusive Open, Close. 50:05.330 --> 50:09.790 Ich hatte also hier meine Anfangszahl von Nachrichten, einmal rum, die 50:11.350 --> 50:20.070 Stopp -Nachrichten sind das und das sind alle anderen. 50:21.030 --> 50:23.470 Und dann hatte ich, das ist ja nur die Anzahl der Nachrichten, die 50:23.470 --> 50:23.930 verschickt werden. 50:24.750 --> 50:26.190 Das ist die Zeit jeweils dafür. 50:27.890 --> 50:31.430 Und das gibt eben an, wie viele Nachrichten überhaupt in der Zeit T 50:31.430 --> 50:32.170 verschickt werden. 50:33.040 --> 50:38.990 Und jetzt setze ich eben für das T den Wert hier entsprechend ein. 50:39.870 --> 50:43.250 Und jetzt mache ich noch folgendes, hier steht ja ein Ziehling, also 50:43.250 --> 50:44.710 die nächstgrößere ganze Zahl. 50:45.250 --> 50:50.910 Das schätze ich ab durch diesen Bruch plus 1, das ist größer gleich 50:50.910 --> 50:54.950 Bruch, also die nächstgrößere ganze Zahl. 50:55.930 --> 50:59.450 Und dann habe ich also hier noch einmal N obendrauf zu zählen. 50:59.450 --> 51:03.230 Im schlimmsten Fall bekomme ich diesen Ausdruck. 51:03.350 --> 51:06.850 Und wenn ich mir den Ausdruck anschaue, habe ich genau wie vorher eine 51:06.850 --> 51:12.870 Abschätzung, die mir sagt, also wenn ich jetzt f von x wähle, als in 51:12.870 --> 51:17.770 diesem Fall nicht 2 hoch x, sondern 2 hoch x minus x plus 1. 51:18.590 --> 51:25.170 Dann habe ich genau die gleiche Abschätzung wie vorher. 51:25.170 --> 51:30.470 Und ich komme, also habe ich diese Terme hier drin stehen. 51:30.950 --> 51:32.550 Und das Ganze ist kleiner als 4N. 51:32.650 --> 51:36.490 Habe ich wieder diese Reihe 1 durch 2 um minus i. 51:37.950 --> 51:44.550 Und ich habe damit das mit 2 abgeschätzt, also 2 mal N da drin. 51:45.090 --> 51:48.590 Und habe dann insgesamt 4N Nachrichten. 51:51.340 --> 51:59.360 Das heißt, wir haben jetzt ein Aufwand pro Nachricht, der konstant 51:59.360 --> 51:59.780 ist. 52:00.140 --> 52:05.720 Wir haben also eine lineare Anzahl von Nachrichten insgesamt. 52:07.020 --> 52:13.000 Also in synchronen Ringen sofort, in synchronen Ringen können wir mit 52:13.000 --> 52:17.220 Nachrichtenaufwand von, also mit linearem Nachrichtenaufwand einen 52:17.220 --> 52:18.120 Anführer bestimmen. 52:19.080 --> 52:23.220 Die Anzahl Nachrichtenbits ist linear oder auch gemeinsame 52:23.220 --> 52:23.840 Entscheidungen. 52:24.080 --> 52:24.940 Sie haben eine Frage. 52:34.140 --> 52:37.980 Naja, ich habe hier den Nachrichtenaufwand, ich habe ja hier Runden 52:37.980 --> 52:38.540 gezählt. 52:39.580 --> 52:43.860 Und natürlich, ja, 52:48.140 --> 52:48.400 richtig. 52:50.820 --> 52:52.080 Aber die Zeit habe ich ja hier mit drin. 52:52.080 --> 52:56.340 Die Gesamtzeit, die ich brauche, ist N mal f von M plus M plus 2. 52:57.320 --> 52:58.720 So, das ist die Zeit, die ich warte. 52:58.800 --> 53:01.760 Das f von M setze ich auf 2 hoch x minus x minus 1. 53:02.360 --> 53:09.780 Das heißt, ich habe hier als Gesamtzeit N mal 2 hoch M plus 1. 53:09.880 --> 53:11.120 Das ist der Term hier oben. 53:12.960 --> 53:15.360 Das ist N mal 2 hoch M plus 1. 53:16.360 --> 53:18.020 M ist eine kleine Zahl. 53:19.760 --> 53:20.040 Ja? 53:21.820 --> 53:25.160 1, 2, 3, 4, 5 oder irgendwas, auf jeden Fall eine Konstante. 53:26.240 --> 53:32.780 Das heißt, ich habe hier insgesamt, als Gesamtzeit hier, diese 53:32.780 --> 53:38.860 Gesamtzeit, N mal 2 hoch M plus 1, ist in O von N. 53:39.240 --> 53:42.400 Weil das 2 hoch M eine Konstante ist, die ist zwar relativ groß, kann 53:42.400 --> 53:44.940 relativ groß werden, trotzdem ist die Konstante. 53:45.560 --> 53:50.800 Unabhängig von der Anzahl, nur abhängig von der Größe der kleinsten 53:50.800 --> 53:51.400 Identität. 53:53.820 --> 53:58.860 Und dieser Term hier, das ist die Gesamtzeit, die wir messen, die ist 53:58.860 --> 53:59.780 jetzt linear geworden. 54:04.840 --> 54:09.020 Vorher hatten wir, na die Gesamtzeit war auch linear vorher, war auch 54:09.020 --> 54:09.300 linear. 54:10.280 --> 54:17.220 Die Zeit, die war eventuell sogar etwas kleiner, aber der Gesamt, das 54:17.220 --> 54:21.660 ist richtig, die Gesamtzeit vorher war eventuell etwas kleiner, aber 54:21.660 --> 54:23.560 ich habe deutlich mehr Nachrichten verschicken müssen. 54:24.420 --> 54:25.040 Insgesamt. 54:25.660 --> 54:27.340 Das ist also das, was ich hier verändere. 54:31.720 --> 54:32.040 Richtig? 54:33.920 --> 54:34.280 Ja? 54:39.620 --> 54:39.900 Richtig. 54:41.680 --> 54:43.460 Also, was wird hier minimiert? 54:43.660 --> 54:44.720 Gut, dass Sie diese Frage stellen. 54:44.820 --> 54:48.300 Die Frage, das kann man nicht hören in der Aufzeichnung. 54:48.340 --> 54:51.020 Die Frage ist, wieso ist das eigentlich ein Vorteil? 54:51.120 --> 54:54.440 Vorher war es doch auch linear, also in der Zeit des ganzen 54:54.440 --> 54:57.820 Algorithmus, es wurden nur parallel eine ganze Reihe Nachrichten 54:57.820 --> 54:58.260 verschickt. 54:58.420 --> 55:02.660 Also dieses O von N² für den Aufwand bezog sich auf die Anzahl der 55:02.660 --> 55:07.160 Nachrichten und ich habe über einen gewissen Zeitraum N Nachrichten 55:07.160 --> 55:07.960 parallel verschickt. 55:08.560 --> 55:10.280 Größenordnung N Nachrichten parallel verschickt. 55:10.400 --> 55:12.740 Deswegen kommen wir auf dieses N². 55:14.320 --> 55:17.740 Das heißt aber eben, der Kommunikationsaufwand ist quadratisch. 55:17.780 --> 55:18.680 Ich habe so viele Nachrichten. 55:19.640 --> 55:24.740 Wenn ich jetzt die Last auf dem Kommunikationsnetz verringern möchte, 55:26.180 --> 55:29.340 sage ich, ich möchte also die Anzahl der Nachrichten für die 55:29.340 --> 55:33.260 Kommunikation, nur um diesen Anführer zu wählen, will ich reduzieren, 55:34.320 --> 55:37.320 damit ich Zeit habe für andere Nachrichten, die verschickt werden 55:37.320 --> 55:37.640 sollen. 55:38.780 --> 55:41.080 Das heißt, ich gucke mir einfach an, 55:45.880 --> 55:50.500 wie kann ich die Anzahl der Nachrichtenwits reduzieren, die ich 55:50.500 --> 55:53.700 zwischen den Prozessen insgesamt verschickt haben muss, damit ich 55:53.700 --> 55:54.540 einen Anführer wähle. 55:55.320 --> 55:58.680 Das war vorher im schlechtesten Fall quadratisch, jetzt sind wir 55:58.680 --> 56:00.140 runter auf linear. 56:02.000 --> 56:06.960 Das heißt, wir verschicken im Prinzip nur eine konstante Anzahl von 56:06.960 --> 56:11.180 Wits pro Runde. 56:13.080 --> 56:17.520 Und insofern haben wir hier den Nachrichtenaufwand reduziert, wir 56:17.520 --> 56:21.080 haben nicht unbedingt die Zeit insgesamt reduziert. 56:21.860 --> 56:25.060 Insofern ist das vielleicht ein bisschen ein Widerspruch, aber ich 56:25.060 --> 56:30.040 schaue mir ja hier ein Problem an, das im Prinzip im Hintergrund 56:30.040 --> 56:33.340 liegt, neben vielen anderen Dingen, die im verteilten System gemacht 56:33.340 --> 56:33.660 werden. 56:34.600 --> 56:40.640 Das ist also im Prinzip zunächst mal eine Fragestellung, wenn ich 56:40.640 --> 56:44.200 sage, wie messe ich den Aufwand für verteilte Algorithmen, wenn ich 56:44.200 --> 56:48.200 den messe über den Kommunikationsaufwand, ist es interessant zu sehen, 56:48.320 --> 56:52.800 wie kann ich den Kommunikationsaufwand bei dieser Art der Messung 56:52.800 --> 56:53.440 reduzieren. 56:53.560 --> 56:55.800 Und die Art der Messung war Anzahl der Nachrichtenwits. 56:56.320 --> 56:58.400 Wir haben nicht gesagt, wir messen die Zeit. 57:00.520 --> 57:05.160 Wobei Sie völlig recht haben, wenn ich weiß, ich habe ein Verfahren, 57:05.320 --> 57:09.780 das synchronisiert laufen kann, dann ist es durchaus interessant zu 57:09.780 --> 57:12.280 sagen, wie viele Runden brauche ich eigentlich, bis ich fertig bin. 57:13.240 --> 57:16.340 Und die Anzahl der Runden, die kann sich hier durchaus erhöht haben. 57:18.000 --> 57:19.780 Das haben wir also jetzt so festgestellt. 57:20.260 --> 57:21.840 Gut, dass Sie die Frage gestellt haben. 57:22.380 --> 57:23.200 Das war sehr angemessen. 57:24.920 --> 57:25.520 Also. 57:26.480 --> 57:30.920 Das zu dieser Erfolgerung. 57:31.040 --> 57:35.380 Wir haben in synchronen Ringen jetzt den Nachrichtenaufwand 57:38.920 --> 57:39.520 reduziert. 57:39.980 --> 57:40.700 Auf Linear. 57:42.120 --> 57:45.840 In asynchronen Ringen ist das allerdings nicht so ohne weiteres 57:45.840 --> 57:46.140 möglich. 57:46.320 --> 57:48.340 Da brauche ich den Login nach. 57:50.240 --> 57:54.200 Das ging hier nur, weil wir alle synchron gearbeitet haben. 57:56.640 --> 57:59.980 was man sich jetzt noch fragen kann, was passiert, wenn ich andere 58:00.500 --> 58:03.320 Verbindungsnetze habe, also nicht einen Ring, sondern irgendeinen Baum 58:03.320 --> 58:06.960 oder irgendeine andere Struktur, wie kann ich dort eigentlich einen 58:06.960 --> 58:07.660 Anführer wählen? 58:08.380 --> 58:09.180 Ist das einfacher? 58:09.380 --> 58:10.100 Ist das schwieriger? 58:10.520 --> 58:11.520 Was passiert da? 58:12.540 --> 58:16.180 Oder eine andere Frage ist, wie kann ich überhaupt gewährleisten, dass 58:16.180 --> 58:18.280 ein System synchron arbeitet? 58:19.820 --> 58:22.640 Dazu brauche ich eine gemeinsame Zeit. 58:23.200 --> 58:24.900 Die muss ich erstmal ermitteln. 58:25.500 --> 58:30.300 Das ist ein ziemlicher Aufwand, um eine Uhren-Synchronisation zu 58:30.300 --> 58:30.520 machen. 58:30.960 --> 58:31.720 Kann man aber machen. 58:33.060 --> 58:38.960 Und diese gemeinsame Zeit oder diese Zeitsynchronisation brauche ich 58:38.960 --> 58:40.420 auch für andere Zwecke. 58:40.920 --> 58:43.700 Deswegen ist das nicht unbedingt etwas, was ich nur diesem Algorithmus 58:43.700 --> 58:45.740 draufschlagen muss. 58:46.300 --> 58:48.700 Dann ist die Frage, was geschieht eigentlich, wenn dabei Fehler 58:51.780 --> 58:54.700 auftreten, kann das ja sein, dass Nachrichten gar nicht ankommen. 58:55.840 --> 58:57.040 Dass Prozesse ausfallen. 58:58.220 --> 59:01.880 Kann ich eigentlich, auch wenn Fehler auftreten, wenn ein Prozess 59:01.880 --> 59:06.680 ausfällt oder einer etwas Falsches schickt, kann ich dann immer noch 59:08.080 --> 59:10.580 einen Konsens-Algorithmus laufen lassen? 59:10.700 --> 59:11.800 Kann ich zu einer Entscheidung kommen? 59:13.160 --> 59:15.360 Die Frage werde ich gar nicht weiter eingehen. 59:16.980 --> 59:22.040 Gehe nur nochmal auf die erste Frage ein und stelle die untere 59:22.040 --> 59:23.740 Schranke für asynchrone Ringe ein. 59:26.930 --> 59:33.050 Also das wird jetzt ein bisschen aufwendig. 59:33.890 --> 59:40.930 Ich wollte einfach zeigen, wie man da argumentieren muss, um Aussagen 59:40.930 --> 59:47.530 zu machen über untere Schranken für die Anzahl der Nachrichten, die 59:47.530 --> 59:52.390 ich brauche, um in einem Ring Idelection zu machen. 59:53.630 --> 59:54.590 Der Asynchron ist. 59:55.770 --> 59:57.810 Das heißt, ich kann hier nicht einfach Runden zählen. 59:58.590 --> 01:00:01.870 Ich weiß nicht, wie lange ich warten muss, bis die nächste Runde 01:00:01.870 --> 01:00:02.350 losgeht. 01:00:03.510 --> 01:00:07.430 Ich habe also in dem Fall wieder den Prozess mit kleinster Identität 01:00:07.430 --> 01:00:07.950 zu suchen. 01:00:09.350 --> 01:00:11.230 Der Ring ist asynchron und gerichtet. 01:00:12.990 --> 01:00:15.290 Die Prozesse kennen nicht die Größe des Rings. 01:00:16.530 --> 01:00:19.050 Wir nehmen an, dass die Reihenfolge der Nachrichten erhalten bleibt, 01:00:19.110 --> 01:00:20.310 dass sie sich nicht überholen können. 01:00:23.630 --> 01:00:27.310 Jede Nachricht enthält höchstens eine konstante Anzahl von 01:00:27.310 --> 01:00:28.670 Prozessnummern. 01:00:29.010 --> 01:00:32.910 Das heißt, ich habe nur Größenordnung Log N Bits dort drin. 01:00:33.870 --> 01:00:36.050 Die wird nicht größer. 01:00:40.000 --> 01:00:43.040 Und alle Prozesse sind potenzielle Initiatoren. 01:00:44.400 --> 01:00:47.640 Jeder könnte einen Prozess angestoßen haben. 01:00:48.580 --> 01:00:56.960 Jetzt ist die Behauptung, dass jeder symmetrische Algorithmus zur 01:00:56.960 --> 01:01:01.200 Bestimmung des Leaders des Anführers benötigt in einem Ring der Größe 01:01:01.200 --> 01:01:05.660 N, im schlechtesten Fall und im Mittel mindestens Omega von N log N 01:01:05.660 --> 01:01:06.300 Nachrichten. 01:01:07.960 --> 01:01:12.140 Das heißt, sobald die Synchronität wegfällt, wenn ich nicht mehr 01:01:12.140 --> 01:01:17.380 zählen kann lokal, also die Kommunikationsrunden zählen kann, dann 01:01:17.380 --> 01:01:21.760 brauche ich im schlechtesten Fall und im Mittel, wie beim Sortieren, 01:01:22.720 --> 01:01:25.680 Aufwand N log N, wobei das hier N log N Nachrichten sind. 01:01:27.760 --> 01:01:32.780 Ich habe Größenordnung log N Bits pro Nachricht, also im 01:01:32.780 --> 01:01:36.520 Gesamtnachrichtenaufwand N log Quadrat. 01:01:38.980 --> 01:01:46.180 Die Idee dieses Nachweises, dass es nicht mit weniger als N log N 01:01:46.180 --> 01:01:50.660 tatsächlich geht, läuft so, dass ich mir angucke, ich habe hier ja 01:01:50.660 --> 01:01:51.100 einen Ring. 01:01:53.700 --> 01:01:53.900 So. 01:01:55.860 --> 01:01:56.800 Da sind irgendwelche Nummern drauf. 01:02:06.270 --> 01:02:07.370 Irgend so was. 01:02:08.270 --> 01:02:09.770 Jetzt werden hier Nachrichten verschickt. 01:02:11.530 --> 01:02:18.310 Jede Nachricht wird irgendwo loslaufen und irgendwohin gehen, zu 01:02:18.310 --> 01:02:19.170 irgendeinem anderen. 01:02:21.150 --> 01:02:26.290 Und jetzt merke ich mir einfach die Knoten, über die ich gelaufen bin. 01:02:27.590 --> 01:02:31.630 Also wenn hier die 3 verschickt wird, dann 01:02:36.050 --> 01:02:40.970 die 3 zum Beispiel, die würde verschickt werden und würde loslaufen 01:02:40.970 --> 01:02:41.610 bei der 3. 01:02:42.870 --> 01:02:46.870 Der Nächste, der mit der 7 bekommt diese Nachricht, würde die ja 01:02:46.870 --> 01:02:47.470 weiterschicken. 01:02:48.050 --> 01:02:53.870 Der verschickt also auch die Nachricht 3, aber die ist bei 3 01:02:53.870 --> 01:02:55.950 losgelaufen und danach bei der 7 gewesen. 01:02:57.130 --> 01:03:02.790 5 würde das auch machen, würde also die 3 verschicken und die ist erst 01:03:02.790 --> 01:03:08.430 bei der 3 losgelaufen und danach zur 7 gekommen und dann bei der 5. 01:03:10.330 --> 01:03:14.650 Weiter wird sie nicht verschickt, weil dann bin ich beim Prozess 1 und 01:03:14.650 --> 01:03:18.470 der wird 1 rausgeschickt werden. 01:03:21.680 --> 01:03:21.820 So. 01:03:23.760 --> 01:03:31.620 Und jetzt kann man sich überlegen, was für Nachrichten ich eigentlich 01:03:31.620 --> 01:03:31.980 brauche. 01:03:32.140 --> 01:03:36.980 Also ich verbinde mit jeder Nachricht eine Spur, die beschreibt, von 01:03:36.980 --> 01:03:39.640 welchen Prozessen diese Nachricht beeinflusst worden ist. 01:03:40.760 --> 01:03:44.280 Und dann bestimme ich eine untere Schranke für die Anzahl der 01:03:44.280 --> 01:03:48.820 Nachrichten über Eigenschaften der Menge möglicher Spuren. 01:03:49.740 --> 01:03:56.640 Ich schaue mir also an, diese Spuren der Nachrichten und überlege mir, 01:03:57.600 --> 01:04:05.420 welche Eigenschaften die Menge der Spuren haben muss, bis dieser 01:04:05.420 --> 01:04:11.160 Algorithmus zur Bestimmung eines Anführers zum Ende gekommen ist. 01:04:13.300 --> 01:04:17.240 Wie groß ist dann diese Menge der Spuren mindestens? 01:04:19.440 --> 01:04:22.880 Und darüber kann ich dann etwas aussagen über die Anzahl der 01:04:22.880 --> 01:04:24.480 Nachrichten, die verschickt worden sein müssen. 01:04:25.600 --> 01:04:29.260 Eine lange Spur heißt, ich habe so viele Nachrichten verschickt und 01:04:29.260 --> 01:04:30.040 damit... 01:04:30.040 --> 01:04:35.760 und ich habe so und so viele verschiedene Spuren über eine untere 01:04:35.760 --> 01:04:38.920 Schranke über die Anzahl der Nachrichten insgesamt.