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

Dozent: Prof. Dr. Christian Scheideler

Übungsgruppenleiter: Christina Kolb

Modulinformation

  • Modul II.2.1 (MuA)
  • V2+Ü1 SWS
  • 4 ECTS Credits

Zeit und Ort

  • V: Mi, 11-13 Uhr, F0.530
  • Ü: Mi, 13-14 Uhr, F0.530

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 Abgabe des Softwareprojekts muss spätestens am 30. 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: 8. bis 12. August (final!)
  • Prüfungsblock 2: 4. bis 7. Oktober

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 verteilte Datenstrukturen aufbauend auf Java und Subject.java implementieren. Einige Beispiele sind:

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 System) und Search
  • Selbststablisierende Clique mit dem deterministischen Build-Clique Protokoll basierend auf der sortierten Liste und den Operationen Join, einfachem Leave und Search
  • Selbststabilisierender de Bruijn Graph in der Variante auf Folie 171 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 ansprechender GUI
  • Selbststabilisierender Multiskip+-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 (Variante 1) mit den Operationen Join, Leave, Enqueue und Dequeue
  • Verteilter Stack auf Skip+-Graph (Variante 1) mit den Operationen Join, Leave, Push und Pop

Themen für vier Personen:

  • Wie die Themen für drei Personen, aber mit ansprechendem GUI
  • Erweiterungen oder komplexere Varianten zu den Themen für drei Personen (z.B. komplexeres Leave, beschleunigte Selbststabilisierung, Berücksichtigung korrumpierter IDs, Erfüllung der monotonen Suchbarkeit oder lokalen Konsistenz)
Sie interessieren sich für:

Wei­te­re In­for­ma­ti­o­nen

Kontakt: Prof. Dr. Christian Scheideler
Email:

scheideler@upb.de

Büro: F2.326