Ver­teil­te Al­go­rith­men und Da­ten­struk­tu­ren

Dozent: Prof. Dr. Christian Scheideler

Modulinformation

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

Zeit und Ort

  • V: Mi, 16-19 Uhr, F1.110
  • Ü: Di,  16-18 Uhr, F1.110

Schein

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 Ende September erfolgen. Terminanfragen für die mündliche Prüfung sowie einen Termin zur Vorstellung des Softwareprojects 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: 22.07.-26.07.2019
  • Prüfungsblock 2: 23.09.-27.09.2019

Die mündliche Prüfung dauert 30 Minuten. Vorstellungen der Software können auch außerhalb dieser Prüfungsblöcke durchgeführt werden und dauern in der Regel 15-20 Minuten. Für die Teilnehmer, die nur die 4 ECTS-Version des Kurses bestehen möchten, sind nur die Inhalte der Veranstaltung bis zum 12. Juni relevant.

Inhalt

Die Vorlesung wird eine Einführung in die Grundlagen der verteilten Algorithmen und Datenstrukturen geben. Einige dieser Verfahren werden mithilfe einer speziellen Erweiterung von Java implementiert werden. Die Folien werden hier zur Verfügung gestellt.

Übungsblätter

Die Abgabe der Übungsblätter kann in Gruppen bis zu 3 Personen geschehen. Einen Bonus von 0,3 Punkten auf die Gesamtnote erhält derjenige, der eine Lösung in der Übungsgruppe vorstellt. Die Bonuspunkte werden jedoch nur angewendet, wenn die mündliche Prüfung und das Softwareprojekt bestanden wurden.

Programmierumgebung

Wir werden diesmal eine neue Entwicklungsumgebung namens NetSimLan verwenden. Sie können diese unter https://netsimlan.org/download herunterladen. Darunter finden sich auch Beispiele.

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 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)

 

Sie interessieren sich für: