Ver­teilte Al­gorith­men und Daten­struk­turen

Dozent: Prof. Dr. Christian Scheideler

Modulinformation

  • Modul II.2.1 (MuA)
  • V3+Ü2 SWS
  • 6 ECTS Credits

Zeit und Ort

  • V: Mi, 8:15-10:45 Uhr, F1.110
  • Ü: Fr, 11:15-12:45 Uhr, F1.110

Die Vorlesung startet am Mittwoch, den 5. April. Die Übungen starten am Mittwoch, den 14. April.

Schein

Voraussetzung zum Erwerb des Scheins ist, dass mindestens einmal eine Lösung in einer Übungsgruppe vorgestellt worden ist.

Die Note des Scheins setzt sich zur Hälfte aus der mündlichen Prüfung und einem Softwareprojekt zusammen. Notwendig für das Bestehen des Kurses ist das Bestehen beider Hälften. Das Thema des Softwareprojekts kann aus einer Auswahl an Themen des Dozenten gewählt werden oder von der Gruppe in Absprache mit dem Dozenten festgelegt werden. Maximal 4 Personen können an einem Softwareprojekt arbeiten. Die Vorstellung und Abgabe des Softwareprojekts muss spätestens am 30. September 2023 erfolgen. Terminanfragen für die mündliche Prüfung sowie einen Termin zur Vorstellung des Softwareprojekts bitte per Email an Frau Hucke (marion.hucke@upb.de). Nähere Angaben zur mündlichen Prüfung und zum Softwareprojekt finden Sie unten.

Für die mündlichen Prüfungen gibt es die folgenden zwei Prüfungsblöcke:

  • Prüfungsblock 1: 7.-11. August
  • Prüfungsblock 2: 11.-15. September

Softwarevorstellungen können auch außerhalb dieser Prüfungsblöcke durchgeführt werden. Für die Teilnehmer, die nur die 4 ECTS-Version des Kurses bestehen möchten, sind nur die Inhalte der Veranstaltung bis zum Ende von Kapitel 5 (Prozessorientierte Datenstrukturen) relevant.

Inhalt

Die Vorlesung wird eine Einführung in die Grundlagen der verteilten Algorithmen und Datenstrukturen geben. Als Programmierumgebung werden wir eine Umgebung namens NetSimLan verwenden. Die Folien werden in PANDA zur Verfügung gestellt.

  • Einleitung
  • Netzwerktheorie
  • Designprinzipien für verteilte Algorithmen und Datenstrukturen
  • Einführung in verteilte Programmierung
  • Prozessorientierte Datenstrukturen
    - (zyklische) Listen
    - de Bruijn Graphen
    - Skip Graphen
    - Delaunay Graphen
  • Informationsorientierte Datenstrukturen
    - Verteiltes Hashing
    - Verteilte Queue
    - Verteilter Stack
    - Verteilter Heap

Übungsblätter

Übungsblätter werden in PANDA bekannt gegeben werden. Die Übungsblätter werden jeweils am Mittwoch veröffentlicht und müssen am darauffolgenden Mittwoch bis Mitternacht eingereicht werden, um korrigiert zu werden. Übungsblätter können in Gruppen von bis zu 3 Personen bearbeitet werden. Die Anzahl der gelösten Aufgaben ist nicht relevant für die Zulassung zu den Prüfungen, aber jeder Teilnehmer muss mindestens einmal eine Lösung in der Übungsgruppe vorgestellt haben, um zu den Prüfungen zugelassen zu werden.

Programmierumgebung

Wir werden NetSimLan verwenden. Weitere Informationen dazu sind in PANDA zu finden.

Literatur

Die Vorlesung basiert auf Originalliteratur, die in den einzelnen Kapiteln referenziert wird.

Hinweise zur mündlichen Prüfung

Die mündliche Prüfung dauert 30 Minuten und erstreckt sich über sämtliche Themen der Vorlesung. Dabei geht es im wesentlichen um Verständnisfragen, d.h. man muss in der Lage sein, die in der Vorlesung vorgestellten Definitionen, Aussagen, Verfahren und Beweise korrekt und ohne viel Zeit zu verschwenden wiederzugeben. (Die Note ergibt sich aus der Leistung in der Prüfung, und die Leistung ist bekanntlich definiert als Arbeit pro Zeit.)

Hinweise zum Softwareprojekt

Die Benotung des Softwareprojekts folgt den folgenden Kriterien:

  • sehr gut: Das Programm läuft fehlerlos und erfüllt alle Vorgaben des Themas. Weiterhin ist entweder eine originelle Erweiterung eingebaut worden oder es werden Simulationsergebnisse präsentiert, die die Skalierbarkeit oder Robustheit des Systems demonstrieren.
  • gut: Das Programm läuft fehlerlos und erfüllt alle Vorgaben des Themas.
  • befriedigend: Das Programm läuft bis auf Kleinigkeiten fehlerlos, oder das Programm erfüllt größtenteils die Vorgaben des Themas.
  • ausreichend: Das Programm läuft, hat aber größere Fehler, oder nur ein kleiner Teil der Vorgaben konnte erfüllt werden.
  • mangelhaft: Das Programm läuft nicht oder hat die Vorgaben klar verfehlt.

Im Folgenden sind einige Beispielthemen für verschiedene Gruppengrößen aufgelistet. Gruppen können aber auch ihre eigenen Themen vorschlagen. In jedem Fall sollte die Gruppe zunächst vom Dozenten ihre Wahl bestätigen lassen, bevor diese mit den Implementierungen startet.

Themen für eine Person:

  • Selbststabilisierende d-fache Liste mit d=c*log n für eine beliebige aber feste Konstante c mit den Operationen Join, einfachem Leave (Knoten verlässt einfach das System) und Search
  • Selbststabilisierender de Bruijn Graph in der Variante auf Folie 160 von Kapitel 5 mit den Operationen Join, einfaches Leave und Search
  • Selbststabilisierender Skip+-Graph mit den Operationen Join, einfaches Leave und Search
  • Selbststabilisierende verteilte Hashtabelle (bestehend aus konsistentem Hashing auf einer sortierten Liste) mit den Operationen Join, einfaches Leave, Insert, Delete und Search
  • Server-basiertes SHARE mit den Operationen Join, Leave, Insert, Delete und Search

Themen für zwei Personen:

  • Wie die Themen oben, aber mit verteilter Anwendung über dem Overlaynetz
  • Selbststabilisierender Delaunay Graph
  • Selbststabilisierender Brück Skip+-Graph mit den Operationen Join, einfaches Leave und Search
  • Selbststabilisierende verteilte Hashtabelle (bestehend aus konsistentem Hashing auf dem Skip+-Graphen) mit den Operationen Join, einfaches Leave, Insert, Delete und Search

Themen für drei Personen:

  • Selbststabilisierende Hashtabelle (bestehend aus konsistentem Hashing auf dem Skip+-Graphen) mit combine&split und den Operationen Join, einfaches Leave, Insert, Delete und Search
  • Verteilte Queue auf Skip+-Graph mit den Operationen Join, Leave, Enqueue und Dequeue
  • Verteilter Stack auf Skip+-Graph mit den Operationen Join, Leave, Push und Pop

Themen für vier Personen:

  • Wie die Themen für drei Personen, aber mit verteilter Anwendung über dem Overlaynetz
  • Erweiterungen oder komplexere Varianten zu den Themen für drei Personen (z.B. selbststabilisierendes Leave, beschleunigte Selbststabilisierung, Berücksichtigung korrumpierter IDs, Erfüllung der monotonen Suchbarkeit oder sequentiellen Konsistenz)