Verteilte Algorithmen und Datenstrukturen

Dozent: Prof. Dr. Christian Scheideler

Übungsgruppenleiter: Alexander Setzer

Modulinformation

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

Zeit und Ort

  • V: Mi, 14-16 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 Vorstellung des Softwareprojekts muss spätestens am 29. 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: 7. bis 11. August 2017
  • Prüfungsblock 2: 26. bis 29. September 2017

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 Übungsblätter enthalten zwei verschiedene Aufgabentypen (Typ A / Typ B). Einen Bonus von 0,3 Punkten auf die Gesamtnote erhält man, indem man entweder mindestens 11 von 13 Aufgaben vom Typ A vollständig bearbeitet oder mindestens 50% der Aufgaben vom Typ B korrekt löst. Die Bonuspunkte werden jedoch nur angewendet, wenn die mündliche Prüfung und das Softwareprojekt bestanden wurden.

Programmierumgebung

Wir werden eine Programmierumgebung aufbauend auf OMNeT++ und Oversim verwenden. Die Umgebung mit allen Tools und Beispielen kann hier runtergeladen werden. Bitte laden Sie die Dateien mit Rechtsklick herunter, sonst wird man aufgefordert, sich einzuloggen.

Programme

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
  • Selbststabilisierender de Bruijn Graph in der Variante auf Folie 156 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 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 ansprechendem GUI
  • Erweiterungen oder komplexere Varianten zu den Themen für drei Personen (z.B. komplexeres Leave, teilweise selbststabilisierend, Berücksichtigung korrumpierter IDs, Erfüllung der monotonen Suchbarkeit oder der lokalen Konsistenz)
Sie interessieren sich für: