TU Wien:Distributed Algorithms VU (Schmid)

From VoWi
Jump to navigation Jump to search

Daten[edit]

Lecturers Ulrich Schmid
ECTS 6
Alias Distributed Algorithms (en)
Department Computer Engineering
When summer semester
Last iteration 2021SS
Language English
Links tiss:182702, Homepage
Zuordnungen
Master Logic and Computation Wahlmodul Algorithmics and Complexity
Master Visual Computing Wahlmodul Methoden für Visual Computing
Master Software Engineering & Internet Computing Wahlmodul Algorithmik
Master Technische Informatik Wahlmodul Verteilte Algorithmen
Master Informatikdidaktik Wahlmodul Algorithmik

Mattermost: Channel "distributed-algorithms"RegisterMattermost-Infos

Inhalt[edit]

(aus TUWIS++):

Grundlagen: Execution runs, safety and liveness properties, causality and time; Modelle: Message passing vs. shared memory, synchronous vs. asynchronous, failure models; Algorithmen: Leader election, mutual exclusion, clock synchronization, consensus, distributed snapshots;

Beweistechniken: Impossibility proofs, lower bounds, simulation, indistinguishability, bivalence.

Ablauf[edit]

Vorlesung mit Anwesenheitspflicht und 4 Homeworks[+ HW5 optional]

Empfehlenswerte Vorkenntnisse[edit]

Algorithmen und Datenstrukturen 1, Mathematik für Informatiker 1/2, vor allem aber Diskrete Mathematik für Informatiker und Formale Methoden der Informatik

Vortrag[edit]

Prof. Schmid ist durchaus bemüht den Stoff verständlich und mit viel Einsatz zu erklären und diesen mit Tafelbildern zu visualisiern. Aufgrund der Komplexität einiger Teilabschnitte(die laut Prof. ja eigentlich nicht vorhanden ist, weil der VALG Stoff ohnehin eher trivial und einfach ist), speziell Lowerbounds gelingt dies jedoch nicht immer.

Prof. Schmid ist der beste Vortragende den ich je erlebt hatte. Er schafft es wirklich komplexere Beweise verständlich vorzutragen. Er ist extrem hilfsbereit, man kann ich wegen jeder Frage zu einer Homework oder zu den Quizzes in seinem Büro besuchen. Ich habe bis dato alles von ihm erklärte gut verstanden, wobei ich aus dem Buch davor nicht schlau wurde.

Übungen[edit]

bis jetzt 4 Homeworks, ein optionales HW5. Diese sind gegliedert in eine first-version (muss nicht vollständig korrekt sein, sollte sie aber. Sie wird nicht so stark bewertet wie die final version. Sie dient dazu falsche Ansätze frühzeitig - bei der presentation - aufzudecken), einen peer-review (man muss die first-version von zwei kollegen reviewen und bewerten), final-version (sollte möglichst korrekt sein, zählt am meisten) und shepherding-review (bei welchem die zwei homeworks der kollegen, diesmal die final version, bewertet werden sollen).

was die first-version wichtig macht ist die presentation: zwar ist es schwierig bei der Präsentation eine schlechte Note zu bekommen (ist generell eine 1 wenn man den eigenen Ansatz verstanden hat und erklaeren kann), jedoch sind die Einbußen durch schlechte Presentation sehr stark: eine Note < 1 verringert die erreichbaren Punkte auf die Homeworks, d.h. wenn man im Schnitt nicht eine 1 hat (was wirklich nicht weiter schwierig ist) dann wird ein Prozentsatz der Punkte der Homeworks (welche ca 45% der Endnote ausmachen) abgezogen.

Generell sollte man sich sehr viel Zeit fuer die Homeworks nehmen (eine Woche mindestens pro Homework, first version). Vor allem das erste HW erscheint anfangs extrem aufwaendig, aber bereits beim HW2 geht es um einiges schneller und der Aufwand wird ueberschaubar.

SS2021: Again five homeworks with the grading scheme of best 4 out of 5. In the end, no one of this semester did the fifth homework. Homework 1 was definitely the most elaborate one. If HW1 was the baseline, I would say HW2 was 50%, HW3 70%, HW4 65% of the work (a very subjective measure).

Prüfung, Benotung[edit]

5 Tests während des Semesters - der Schlechteste wird gestrichen (zählen 40%)

5 Homeworks - das Letzte ist optional und kann ein Schlechtes ersetzen (zählen 45%)

Abschlusstest (zählt 15%)

Nur wer entweder auf den ersten oder zweiten Test mindestens 60% der Punkte erreicht darf weiter machen.

Für eine positive Note müssen mindestens 60% der Punkte erreicht werden.

Dauer der Zeugnisausstellung[edit]

die Ergebnisse der Quizzes sind meistens schon am Tag danach einzusehen, die Endnote weiss man bereits 2-3 Wochen nach dem Final Exam.

Zeitaufwand[edit]

SS2021: I invested almost 200 hours, and I guess with less than 150 hours, it's nearly impossible to get positive. We were five students in the course, and there's (limited) empirical evidence for this hypothesis.

Unterlagen[edit]

  • Folien (siehe Homepage)
  • Textbook: Hagit Attiya and Jennifer Welch: "Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd ed.)", Wiley, 2004 (ISBN 0-471-45324-2)

Tipps[edit]

Die Aufgaben sehr genau ausarbeiten. Im Vordergrund der Aufgaben steht hauptsächlich das Erlernen und Übern von Beweistechniken und das rigorose Ausarbeiten.

Verbesserungsvorschläge / Kritik[edit]

SS2021: After doing my SE Bachelor and almost completing all my lectures of the SE Master, this course was the pinnacle of my studies regarding the intellectual challenge. It was an emotional rollercoaster for me, and especially in the beginning, I often considered aborting it. However, in the end, I am happy I didn't because there's probably no lecture at TU Vienna where you get a similar degree of mentorship from a professor. Moreover, I have the feeling as if my "algorithmic thinking" significantly improved due to the course.

However, this comes at the (understandable) cost of Prof. Schmid trying to "filter out" students at the beginning of the course. After starting with over 20 students, we were only 5 students who did both entrance tests, completed the first homework, and then remained in the course. The two entrance tests examine mathematical skills that are supposedly required for the completion of the course. In my opinion, however, they test a higher level of mathematics than required. For the assigned exercises, no advanced skills in combinatorics and complexity analysis (Big O notation) are necessary, and it does not make sense to check them in a closed-book limited-time setting (except you would like to filter out some students).

Additionally, although the grading scheme is well-defined, it is quite complicated and challenging. For example, each homework is given a grade from 1 to 5, where a 1 is difficult to achieve (in the first HW, we had one 4, three 3, and one 2). The grades are mapped to percentages in the form 1 => 100, 2 => 80, 3 => 60, etc. However, the scheme of the final grade is rather strict (>90 => 1, >80 => 2, etc.). This means, even if you think you are positive by having an average grade of 3 over all exercises, you can get a negative grade in the end if your reviews have an average grade worse than 3 (in our case, we got to know the grades of the reviews only after writing all of them, which makes it even more uncomfortable).