Proseminar Verteilte Algorithmen

Dozent: Thorsten Götte (thgoette@mail.upb.de)

Zeit und Ort: 12.04.2022 um 16:00 Uhr in F2.211

Inhalt

Ziel des Proseminars ist es, zu lernen, Algorithmen auf dem Bereich der theoretischen Informatik zu verstehen und diese (für ein fachliches Publikum) verständlich wiederzugeben.

Konkret behandeln wir in diesem Seminar Themen aus der wunderbaren und vielfältigen Welt der verteilten Algorithmen. Diese reicht von Protokollen für sicheren und effiziente Kommunikationsnetze über Algorithmen für die Datenverarbeitung in der Cloud bis hin zu modernen Trendthemen wie Kryptowährungen und Blockchains. Ihr bearbeitet dazu Buchkapitel, Vorlesungsskripte oder ausgewählte Teile von wissenschaftliche Papern. Alle Themen haben dabei einen eher theoretischen Fokus, allerdings sind auch praktischere Arbeiten darunter.

Euer Thema fasst ihr in einem kurzen Bericht (ca. 10-15 Seiten) zusammen. Hier sollt ihr das Problem und den Algorithmus so beschreiben, dass eure Kommilitoninnen und Kommilitonen ihn verstehen können.
Dazu gehört es, einige der Grundideen der formalen Analyse also der Korrekts- und Laufzeitsbeweise auszuarbeiten.

Im letzten Drittel der Vorlesungszeit gibt es eine Peer-Review Phase in der ihr zwei andere Berichte lest und dem Autor bzw. der Autorin Feedback zum aktuellen Stand geben müsst. Die finale Abgabe der Berichte ist im September. Am Ende der Vorlesungszeit haltet in einem Blockseminar am Ende der Vorlesungszeit einen Vortrag. Die genauen Termine für die Abgaben und die Vorträge machen wir dabei von den Klausurterminen abhängig.

Es gibt KEINE wöchtentlichen Treffen in der großen Gruppe, inhaltliche und stilitische Fragen klären wir individuell. 

Schein

Einen Schein bekommt, wer alle schriftlichen Abgaben erfüllt und das Thema im abschließenden Seminar mündlich vorstellt. Die schriftlichen Abgaben bestehen aus einem Abstract (~ 1 Seite), einem vorläufigen Report, einem Review (~ 1-2 Seiten) zu je zwei anderen vorläufigen Reports und der finalen schriftlichen Abgabe (~ 10 Seiten). Die Endnote setzt sich zu 50% aus der mündlichen Präsentation und zu 50% aus der finalen schriftlichen Abgabe zusammen. Der vorläufige Report und die Reviews fließen nicht in die Note ein und dienen dazu früh Feedback zu erhalten.

Übersicht über die Themen

Vertex Coloring, Maximal Inpedendent Set, Peer-2-Peer Netzwerke, Merkle Hash Trees, Proof-of-Work, Byzantine Consensus, Byzantine Broadcast