Distributed Algorithms (VALG  182.702)
[TISSSeite] [TISS Syllabus] [Background info] [Enrolling] [Grading] [SCHEDULE] [HOMEWORK] [Other resources]
News
March 3, 2021: I decided to start streaming my lectures from the library of the ECS Group E19102 (Treitlstrasse 13, 2nd floor), as we have got new equipment that allows me to use ZOOM. Students with TU Wien employee status who want to join me there are kindly requested to send me an email before, so that I can check whether we can meet the Corona restrictions.
February 2021: Unfortunately, like in SS2020, the Corona restrictions do not allow me to teach VALG in the only format that is adequate for advanced academic teaching, namely, interactively in a lecture room: It is absolutely impossible to simulate the level of interaction achievable with presence lectures and classroom homework presentations online, and online quizzes and exams are ineffective and a pain in the ass for everybody. I hence had to significantly change the organization of the course, and apologize in advance for the inevitable degradation of quality. More specifically, all homework presentations, Quiz 35 and the final exam have been dropped; only Quiz 1 and 2, which are the basis for the entrance requirement, will take place online. To encourage you to also master the material taught in the lectures, however, students presentations have been added.
Note that I will do live streaming of my lecture (that will take place exactly as given in the schedule below) either from HS17 via LectureTube Live or, preferably, from an alternative room like the library of the ECS Group E19102 that allows me to use ZOOM. Unfortunately, I am not allowed to allow "ordinary" students to join me in the lecture room :), as only TU Wien employees are allowed to enter and use our facilities.
Online participation details
About:
 Some successes of former VALG participants
 Result of the course evaluation (using this questionaire): SS09 SS10 SS11 SS12 SS13 SS14 SS15 SS16 SS17 SS19
 Ein Benchmark VALG vs. einschlägige LVAs an international renommierten Universitäten [in German]
Aim
Faulttolerant distributed algorithms are at the heart of any distributed system for critical applications and implement lowlevel services like clock synchronization, group membership and consensus. Suitable algorithms must work as specified in the presence of the inherent uncertainty in network or sharedmemory coupled distributed systems, which is caused by varying/unknown communication delays and computing speeds and, in particular, subsystem failures. Due to combinatorial explosion, it is often impossible to verify the correct operation of such algorithms by means of model checking (or exhaustive testing). Correctness proofs based on formalmathematical modelling are the only feasible alternative here. This theoretical graduatelevel basic course provides an introduction to distributed algorithms and their formalmathematical analysis. Apart from developing formalmathematical skills in general, this course shall allow its attendees to: (1) become familiar with fundamental models, problems, algorithms, lower bound and impossibility results, and proof techniques in distributed computing, (2) be able to apply lower bounds and impossibility results learned to new situations where appropriate, (3) be able to design new distributed algorithms for new situations, using the algorithms and techniques learned as building blocks, and (4) find new lower bounds and impossibility results.
The course is organized in the "angloamerican style", which is based on continuous engagement during the whole semester: Several quizzes and homework assignments ensure (1) that the topics taught in the lecture are efficiently acquired, and (2) that the individual formalmathematical problemsolving skills are trained. The homework assignments are treated in "mini conferences" (LaTeX solutions, reviewing, presentation in class), such that (3) these scientific soft skills are trained "handson" as well.
In order to participate, you need to enrol in the corresponding TUWEL course first, where the link for online participation will be announced. Detailed instructions and mandatory prerequisites can be found in the course home page.
ECTS breakdown (6 ECTS = 150 hours):
33h Lecture time
1.5h 2 Quizzes
12h 4 Student presentations
22h Preparation time for quizzes and student presentations
85.5h Preparation time for 4 HomeworkAssignments (35 exercises each): First and final version (in LaTeX); reviewing.
Subject
Faulttolerant distributed algorithms are at the heart of any distributed system for critical applications and implement lowlevel services like clock synchronization, group membership and consensus. Suitable algorithms must work as specified in the presence of the inherent uncertainty in network or sharedmemory coupled distributed systems, which is caused by varying/unknown communication delays and computing speeds and, in particular, subsystem failures. Due to combinatorial explosion, it is often impossible to verify the correct operation of such algorithms by means of model checking (or exhaustive testing). Correctness proofs based on formalmathematical modelling are the only feasible alternative here.
This theoretical graduatelevel basic course provides an introduction to distributed algorithms and their formalmathematical analysis and has the following content:
 Basics: Execution runs, safety and liveness properties, causality and time;
 Models: Message passing vs. shared memory, synchronous vs. asynchronous, failure models;
 Algorithms: Leader election, mutual exclusion, clock synchronization, consensus, distributed snapshots;
 Proof techniques: Impossibility proofs, lower bounds, simulation, indistinguishability, bivalence.
Lecturer
Prof. Ulrich Schmid
Homepage
https://ti.tuwien.ac.at/ecs/teaching/courses/valg
BACKGROUND INFO
This is a graduatelevel theoretical course on distributed algorithms based on the textbook Hagit Attiya and Jennifer Welch: Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd ed.), Wiley, 2004 (ISBN 0471453242). Its main emphasis is on developing skills for proving the correctness of distributed algorithms and proving impossibility results and lower bounds on message and time complexity.
Prerequisites are familiarity with the complexity analysis of sequential algorithms (level of 186.866 Algorithms and Datastructures) and discrete mathematics (level of 104.265 Algebra and Discrete Mathematics + 104.261 Analysis for Computer Science + 104.271 Discrete Mathematics). In particular, you must be familiar with basic mathematical methods like asymptotics ("Onotation"), elementary combinatorics, graph theory and probabilities, and should be reasonably skilled in doing elementary mathematical proofs (induction, indirect proofs). Moreover, the course expects familiarity with the basics of scientific working (LaTeX, reviewing, at the level of 193.052 Scientific Working). Since these prerequisites are mandatory for passing the course within reasonable time, they will be checked (along with preliminary knowledge of Chapter 2 of the textbook) in the first quiz. A sample quiz may be found here. Note that you must achieve 60% of the total points (1 point for every correct multiple choice answer, and usually 2 or 3 points for the other questions) to pass any quiz. Please make sure that you are properly prepared when you participate in the first quiz  experience tells that most people who "accidentially" passed the first quiz drop out of the course, thereby totally wasting all the (huge) efforts spent so far.
The syllabus can be found above, and here are my slides. Note that my slides also provide a lot of material not found in the textbook, and define the actual content of the course. The textbook is sufficient for the advance reading, though (see below).
Aims & scope and requirements are different from the undergraduate courses you are probably most familiar with. It has a clear focus on scientific education, in particular, on developing formal/mathematical skills. In sharp contrast to undergraduate courses where knowledge acquisition is more or less "pushbased", VALG is very much "pullbased": You cannot expect to get all the information required for mastering a course in a conveniently madeup form. Rather, you have to make sure that your prerequisite knowledge allows you to stay caught up in class, and it is your responsibility to use all available sources of information (textbook, lecture, papers, etc.) for solving problems and developing a coherent and indepth understanding of the subject.
Please do advance reading of the relevant chapters of the textbook (note that the Lehrbuchsammlung of our TU Bibliothek provides some copies that you can borrow). In fact, it is difficult to really benefit from the lecture without any advance knowledge. Although this does of course not mean that you have to know the details from this advance reading, you should nevertheless have gathered enough information to understand those details when presented in class. Some additional questions in the first two quizzes (at the beginning of Chapter 2 and 3) shall encourage you to do this reading and thereby prove its value.
Presence in the online classes is mandatory. Unusual circumstances must be discussed in advance with me, and all excused absences (which may require a certification) must be cleared with me as well.
Collaborations: Discussion of concepts/solutions for homework assignments is encouraged, but all work must be done on your own and written up in your own words. If you use any source other than the textbook or my slides, reference it/him/her, whether it be a person, a book, a solution set, a web page or whatever. Nonadherence to this rule, as well as collaboration and cheating in quizzes, will not be tolerated at all!
[To understand the rationale of the above, it is very instructive to see how rigidly good US universities handle the issue of academic integrity, plagiarism, etc. Consult the Texas A&M University Code of Honors for an example.]
ENROLLING
The class size is limited to at most 18 for didactic reasons, which is compliant with the official regulations. If really necessary, there will be two classes in parallel, with a common lecture class. The following admission requirements will be enforced: You must (1) already be studying in one of the Master programs [those where VALG is a mandatory course have priority] and (2) attend and achieve at least 60% in the first quiz or attend and fail in the first quiz but achieve at least 60% in the second quiz. I will not issue negative certificates for those who fail in the first quiz but do not participate in the second quiz, but I do issue negative certificates (and deny further participation) for those who fail in both quizzes.
There is no need to explicitly enroll to the first and second quiz  everybody who complies to (1) is eligible here. To be able to join the online lecture and the quizzes, however, you must enrol to the course in TISS, as this will automatically add you to the TUWEL course VALG2021S that provides all the required links.
Nevertheless, everybody who finally passed the course admission criterion stated above must also enroll via myTI.
GRADING
Grading will be based on the following components:
 Homework assignments (60%): There will be 5 paper exercises (the 5th one is optional), one per chapter, to be worked out in LaTeX (50%) and reviewed by other participants (10%); the details can be found below. Late assignments will not be graded!
 Quizzes (20%): There will be 2 short online quizzes (3040 min.), consisting of a few simple questions (for example, short answer, truefalse, or multiple choice). Quiz 1 covers advance reading of Chapter 2 of the textbook and mathematical prerequisites. Quiz 2 covers advance reading of Chapter 3 of the textbook and detailed knowledge of the basics (up to but excluding Leader Election) according to my slides. Note that you must achieve 60% of the total points (1 point for every correct multiple choice answer, and usually 2 or 3 points for the other questions) to pass a quiz, and that passing at least one of the two quizzes is an entrance requirement for further participation (see above). Note that there are no makeup quizzes!
 Presentations (20%): For each of the Chapters 3 (Leader Election)  6 (Causality and Time), there will be a student presentation event where I will ask students, selected on the spot, to present some topic from the already given lectures on the respective topic and ask related questions. These presentations shall encourage you to really master the things that have been taught :). You can of course use my slides in your presentation, which must be in English, but can also prepare your own slides or use any other suitable form of online presentation.
The grades for the first two quizzes will be communicated via TUWEL. Later, you will find your various other grades here (and here is the Excelsheet, where you can find the [complex] formula (+ some explanation) used for computing the final grade from the various parts). Note that participation in discussions in class, presentations etc. is also taken into account (at most +/ 10% of total points) when assigning the final grade. The final grade will be assigned according to the following scale:
1 for 90% or above of the total points,
2 for 80 to 89%,
3 for 70 to 79%,
4 for 60 to 69%,
5 for less than 60%.
HOMEWORK
All homework assignments are to be worked out in LaTeX using our LaTeX resources (hw.tex, hwnotitle.tex, firstpage.tex). The LaTeX source file of the first homework assignment can be found in TUWEL, the remaining ones (ex2.tex etc.) will be made available via myTI. Just compile hw.tex or hwnotitle.tex (with the macro \homeworknumber set accordingly) to get the appropriate .pdf.
For every homework assignment [except for Homework 5, which is optional and conducted without reviewing, revision and shepherding], the procedure consists of 2 rounds of peerreviewed writtenup solutions (hwXfirst, hwXfinal) and a presentation. The detailed procedure is as follows:
 Download the current assignment as soon as it is announced. There will be a clarification in class soon after the announcement.
 Carefully work out all the exercises (in English). Correctness, clarity of exposition and general presentation will be evaluated in the reviewing process, so take care of those issues! Deliver your solutions by the scheduled time (late assignments will not be graded!) as follows:
 Upload an electronic version (hwXfirst.pdf), without the title page (use hwnotitle.tex), for anonymous reviewing, which must be uploaded using myTI by the deadline.
 Carefully review hwXfirst of your colleagues (anonymously) assigned to you (in English), and submit the reviews via myTI by the deadline. Since peerreviewing is the most important tool for quality assurance in the scientific community, this exercise shall help you to develop your skills in writing objective and useful reviews: Make sure not to praise bad solutions, turn down good ones, or provide comments to the author which are meaningless! You will be graded for inappropriate reviews! In more detail, the review shall address the following issues:
 Assign a single numerical overall grade [5 ... 1, corresponding to very bad (< 20%) ... very good (>= 80%)] that reflects your assessment of the whole homework, based on some suitable average of the assessments of all the exercises as detailed in the next item.
 Individually, for every exercise, evaluate the categories (1) appropriateness (= elegance and correctness of a solution) and (2) presentation (= clarity of exposition and appearance). Please give both a grade [1 .. 5, corresponding to very good (>= 80) ... very bad (< 20%)] and some explanatory text for every category. In addition, provide (3) concise additional comments that allow the author to improve his/her solution and/or its presentation [you are not expected to do the proofreading for the author, however]: Start with major comments [if any] and then go over the exercise and list minor comments in sequential order.
 Carefully prepare a revision of your homework, based on the feedback you got from the anonymous reviews of your colleagues and my own review (I will replace your original upload with a version that contains my corrections and comments). Note that your revised solution may deviate from the first version, in particular, when the latter was entirely missing, wrong or suboptimal. You may incorporate any information you obtained in the meantime (stating the major sources, except the homework presentations, on the title page as usual) , but don't just copy existing other solutions! Important: The final version of your homework must also include a (single) grade and some explanatory text for every anonymous review you have got, which shall reflect its appropriateness, utility, ... for improving your work. Please try to be objective here, since I will compare your assessment of the appropriateness of the reviews with mine! Deliver the final version of your homework by the scheduled deadline (late assignments will not be graded!) as follows:
 Upload an electronic version (hwXfinal.pdf) using myTI by the deadline, without the title page (use hwnotitle.tex), to enable the shepherding reviews.
 You will be assigned the final version hwXfinal of every homework you reviewed already in Step 2 above for a final shepherding review: Read those papers and check whether and how well the authors have managed to improve their solutions. Use the same reviewing rules as for the first review, except that you should be more demanding in your assessment of hwXfinal then you were in hwXfirst: If a bad solution has not improved, for example, then the grade should be worse than before!
Please make sure that you start working on your homework assignments as early as possible: You will find that the time budget for the homework assignments listed in the ECTS breakdown above is not at all a conservative estimate. In particular, do not underestimate the time needed for properly writing up your solutions and the substantial load created by the many pending tasks during the semester  the schedule is in fact quite tight!
SCHEDULE
The schedule of the course is shown in the table below; please note that it may occasionally change slightly throughout the semester. All lectures and quizzes (for eligible participants, see Online participation details) take place in the library of the ECS Group E19102 (Treitlstrasse 13, 2nd floor). [I keep the reservation for the HS17 (Friedrich Hartmann HS, Karlsplatz 13), however, in the case the Corona restrictions would allow us physical/hybrid presence after Easter :).] The required link can be found in the TUWEL course VALG2021S (requires registration via TISS).
Day 
Date 
Time 
Topic 
Chapter (book) 
Thu  04.03.2021  08:30  Lecture Introduction  Intro slides 
Fri  05.03.2021  08:30  Lecture Basics (1)  2 
Thu  11.03.2021  08:30  Quiz 1: Chapter 2 + Prerequisites  
Lecture Basics (2)  2  
Fri  12.03.2021  08:30  Lecture Basics (3)  2 
23:59  Announcement Homework 1  
Thu  18.03.2021  08:30  Lecture Basics (4)  2 
Clarification Homework 1  
Fri  19.03.2021  08:30  Lecture Basics (5)  2 
Thu  25.03.2021  08:30  Quiz 2: Chapter 3 + 2  
Lecture Leader election in rings (1)  3  
Fri  26.03.2021  08:30  Lecture Leader election in rings (2)  3 
Mon  12.04.2021  23:59  First version Homework 1 due  
Thu  15.04.2021  08:30  Lecture Leader election in rings (3)  3 
23:59  Announcement Homework 2  
Fri  16.04.2021  08:30  Lecture Leader election in rings (4)  3 
Clarification Homework 2  
Thu  22.04.2021  08:00  Student presentation 1 (Leader Election)  
Fri  23.04.2021  08:30  Lecture Mutual exclusion in shared memory (1)  4 
23:59  Reviews Homework 1 due  
Thu  29.04.2021  08:30  Lecture Mutual exclusion in shared memory (2)  4 
23:59  Announcement Homework 3  
Fri  30.04.2021  08:30  Lecture Mutual exclusion in shared memory (3)  4 
Thu  06.05.2021  08:30  Clarification Homework 3  
Lecture FaultTolerant Consensus (1)  5  
Fri  07.05.2021  08:30  Student presentation 2 (Mutual Exclusion)  
23:59  Final version Homework 1 due  
Wed  12.05.2021  23:59 
First version Homework 2 due  
Sun  16.05.2021  23:59  Shepherding review Homework 1 due  
Thu  20.05.2021  08:30  Lecture Faulttolerant consensus (2)  5 
23:59  Announce Homework 4  
Fri  21.05.2021  08:30  Lecture Faulttolerant consensus (3)  5 
Clarification Homework 4  
23:59  Reviews Homework 2 due  
Wed  26.05.2021  23:59  First version Homework 3 due  
Thu  27.05.2021  08:30  Lecture Faulttolerant consensus (4)  5 
Fri  28.05.2021  08:30  Lecture Causality and Time (1)  6 
Wed  02.06.2021  23:59  Final version Homework 2 due  
Fri  04.06.2021  08:00  Student presentation 3 (Consensus)  
Thu  10.06.2021  08:30  Lecture Causality and Time (2)  6 
23:59  Reviews Homework 3 due  
23:59  Announcement [optional] Homework 5  
Fri  11.06.2021  08:30  Lecture Causality and Time (3)  6 
Clarification Homework 5  
23:59  First version Homework 4 due  
Thu  17.06.2021  08:30  Lecture Causality and Time (4)  6 
23:59  Shepherding reviews Homework 2 due  
Fri  18.06.2021  no lecture  
Thu  24.06.2021  08:00  Student presentation 4 (Causality and Time) 

23:59  Reviews Homework 4 due  
Fri  25.06.2021  no lecture  
23:59  Final version Homework 3 due  
Thu  01.07.2021  23:59  Final version Homework 4 due  
Fri  02.07.2021  23:59  Shepherding reviews Homework 3 due  
until  08.07.2021  23:59  Shepherding review Homework 4 due  
until  15.07.2021  23:59  Final version [optional] Homework 5 due 
OTHER RESOURCES
Scientific writing:
 Our version of the seminar 193.052 Scientific Working
 Some useful references:
 Nicolas Higham, Writing for the Mathematical Sciences (2nd ed.), SIAM, 1998. (Verfügbar in Lehrbuchsammlung TUBibliothek)
 Linda Olson, Guide to Academic and Scientific Publication: How to Get your Writing Published in Scholarly Journals, eAcademia, 2014.
 Robert A. Day, How to Write and Publish a Scientific Paper, Cambridge University Press, 1989.
 Justin Zobel, Writing for Computer Science, Springer Verlag, 1997.
 Michael Alley, The Craft of Scientific Writing, Springer Verlag, 1996.
 Herbert B. Michaelson, How to Write&Publish Engineering Papers and Reports, Oryx Press, 1990.
 Donald E. Knuth, Tracy Larrabee, and Paul M. Roberts: Mathematical Writing (Report CS209 Stanford course; book available from Cambridge University Press )
Recommended additional books & papers:
 Nancy Lynch. Distributed Algorithms. Morgan Kaufmann, 1996
 Michel Raynal. Distributed Algorithms for MessagePassing Systems, Springer, 2013
 Gerard Tel. Introduction to Distributed Algorithms, Cambridge University Press, 2000
 Sape Mullender. Distributed Systems. AddisonWesley, 1993
 D. Peleg. Distributed Computing: A LocalitySensitive Approach, SIAM, Philadelphia, PA, 2000
 Faith Fich and Eric Ruppert. Hundreds of impossibility results for distributed computing. In Distributed Computing, 16(23), pages 121163, 2003.
Some selected places to look for distributed algorithms papers:
 Journals:
 Distributed Computing
 IEEE Transactions on Parallel and Distributed Systems
 Journal of Parallel and Distributed Computing
 Conference proceedings:
 ACM Symposium on Principles of Distributed Computing (PODC)
 International Symposium on DIStributed Computing (DISC)
 International Conference on Principles of Distributed Systems (OPODIS)
 International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)
 IEEE Conference on Distributed Computing Systems (ICDCS)
 International Parallel and Distributed Processing Symposium (IPDPS)
 International Colloquium on Structural Information and Communication Complexity (SIROCCO)
 The worldwideweb: Most papers are available online and freely accessible for academic institutions like TU Vienna. Here are some very useful links:
Document Actions
Miscellaneous: