TU Wien:Distributed Algorithms VU (Schmid)
Daten[Bearbeiten | Quelltext bearbeiten]
| Vortragende | Ulrich Schmid |
|---|---|
| ECTS | 6,0 |
| Letzte Abhaltung | 2024S |
| Sprache | English |
| Mattermost | distributed-algorithms • Register • Mattermost-Infos |
| Links | tiss:182702 , Homepage |
Inhalt[Bearbeiten | Quelltext bearbeiten]
(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.
Prof. Schmid insists on doing rigorous and detailed proofs, so when you finish the course you will be able to structure a proof well, which may be even more important than all the other skills taught here.
Ablauf[Bearbeiten | Quelltext bearbeiten]
Vorlesung mit Anwesenheitspflicht und 4 Homeworks[+ HW5 optional]
Empfehlenswerte Vorkenntnisse[Bearbeiten | Quelltext bearbeiten]
Algorithmen und Datenstrukturen 1, Mathematik für Informatiker 1/2, vor allem aber Diskrete Mathematik für Informatiker und Formale Methoden der Informatik
Vortrag[Bearbeiten | Quelltext bearbeiten]
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.
In my honest opinion there is no other course at TU Wien with a lecturer that has even half the dedication. Prof. Schmid is an excellent lecturer and is able to convey the proofs/knowledge well, further he is very willing to discuss and re-explain. For some exercises I handed in 20+ pages of dense latex-written proofs and Prof. Schmid found all mistakes that one could imagine, even typos in subscripts. Additionally the homework was covered with well-meant tips on how to improve (but Prof. Schmid did not insist on this guidance, it was just a hint). So it really helped me to improve (a) my mathematical writing skills, (b) the ability to structure proofs and (c) to find creative proofs and tackle unknown problems.
Übungen[Bearbeiten | Quelltext bearbeiten]
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[Bearbeiten | Quelltext bearbeiten]
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[Bearbeiten | Quelltext bearbeiten]
die Ergebnisse der Quizzes sind meistens schon am Tag danach einzusehen, die Endnote weiss man bereits 2-3 Wochen nach dem Final Exam.
Zeitaufwand[Bearbeiten | Quelltext bearbeiten]
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.
SS2021 (2nd perspective): This was probably the most time-intensive course I've every had, investing well over 200 hours overall. It certainly helps having done FMI and Discrete Maths prior to this course, not because the content is important but rather the ideas and techniques for proofs in these lectures certainly help in this course. Since I hadn't done either of the preceding courses, my time spent was probably more than usual, but I agree with the other comment that investing less than 150 hours overall for a positive grade is very difficult...
SS2022: I spent quite some time in the lecture and with the exercises, even though the peer-reviewing part was dropping since I was the only survivor. I would say I invested 5-7 ECTS, if peer-reviewing had been included, that would easily be another 1-2 ECTS. In my opinion, the most time-consuming part were the exercises, since in comparison to all other lectures one needs to be quite creative when doing the proofs and find the right approach to the problem. Do not underestimate how hard the exercises are, I wasted full days for some proofs.
Unterlagen[Bearbeiten | Quelltext bearbeiten]
- 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)
- (Supplementary) Textbook (sometimes useful for exercises and getting a different perspective on the problems): Nancy Lynch: "Distributed Algorithms" (https://dl.acm.org/doi/book/10.5555/2821576)
- Nancy Lynch's Distributed Algorithms course at MIT (https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-852j-distributed-algorithms-fall-2009/)
Tipps[Bearbeiten | Quelltext bearbeiten]
Die Aufgaben sehr genau ausarbeiten. Im Vordergrund der Aufgaben steht hauptsächlich das Erlernen und Übern von Beweistechniken und das rigorose Ausarbeiten.
Highlights / Lob[Bearbeiten | Quelltext bearbeiten]
noch offen
Verbesserungsvorschläge / Kritik[Bearbeiten | Quelltext bearbeiten]
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).
SS2021 (second perspective): I generally agree with the other comment. Regarding the grading scheme however, note that there are 10% bonus points given by the lecturer that can be obtained by actively participating in the course that can (afaik) also contribute to getting a positive grade. Although mathematically possible, the case with average grade 3 over all exercises and getting a negative grade is thus quite unlikely in my opinion since Prof. Schmid is aware of how demanding the lecture is.