Distributed Algorithms (VALG - 182.702)

[TISS-Seite] [TISS Syllabus] [Background info] [Enrolling] [Grading] [SCHEDULE] [HOMEWORK] [Other resources]


March 3, 2021: I decided to start streaming my lectures from the library of the ECS Group E191-02 (Treitlstrasse 1-3, 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 on-line, 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 3-5 and the final exam have been dropped; only Quiz 1 and 2, which are the basis for the entrance requirement, will take place on-line. 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 E191-02 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.

On-line participation details




Fault-tolerant distributed algorithms are at the heart of any distributed system for critical applications and implement low-level services like clock synchronization, group membership and consensus. Suitable algorithms must work as specified in the presence of the inherent uncertainty in network- or shared-memory 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 formal-mathematical modelling are the only feasible alternative here. This theoretical graduate-level basic course provides an introduction to distributed algorithms and their formal-mathematical analysis. Apart from developing formal-mathematical 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 "anglo-american 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 formal-mathematical problem-solving 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 "hands-on" as well.

In order to participate, you need to enrol in the corresponding TUWEL course first, where the link for on-line 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 Homework-Assignments  (3-5 exercises each): First and final version (in LaTeX); reviewing.


Fault-tolerant distributed algorithms are at the heart of any distributed system for critical applications and implement low-level services like clock synchronization, group membership and consensus. Suitable algorithms must work as specified in the presence of the inherent uncertainty in network- or shared-memory 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 formal-mathematical modelling are the only feasible alternative here.

This theoretical graduate-level basic course provides an introduction to distributed algorithms and their formal-mathematical 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.


Prof. Ulrich Schmid





This is a graduate-level 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 0-471-45324-2). 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 Science104.271 Discrete Mathematics). In particular, you must be familiar with basic mathematical methods like asymptotics ("O-notation"), 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 "push-based", VALG is very much "pull-based": You cannot expect to get all the information required for mastering a course in a conveniently made-up 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 in-depth 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 on-line 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. Non-adherence 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.]


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 on-line lecture and the quizzes, however, you must enrol to the course in TISS, as this will automatically add you to the TUWEL course VALG-2021S that provides all the required links.

Nevertheless, everybody who finally passed the course admission criterion stated above must also enroll via myTI.


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 on-line quizzes (30-40 min.), consisting of a few simple questions (for example, short answer, true-false, 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 make-up 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 on-line 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 Excel-sheet, 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%


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 peer-reviewed written-up solutions (hwXfirst, hwXfinal) and a presentation. The detailed procedure is as follows:

  1. Download the current assignment as soon as it is announced. There will be a clarification in class soon after the announcement.
  2. 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 peer-reviewing 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 proof-reading for the author, however]: Start with major comments [if any] and then go over the exercise and list minor comments in sequential order.
  3. 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 sub-optimal. 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!



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 On-line participation details) take place in the library of the ECS Group E191-02 (Treitlstrasse 1-3, 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 VALG-2021S (requires registration via TISS).






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 Fault-Tolerant 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 Fault-tolerant consensus (2) 5
23:59 Announce Homework 4
Fri 21.05.2021 08:30 Lecture Fault-tolerant 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 Fault-tolerant 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
Sat 12.06.2021 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 08:00 Student presentation 4 (Causality and Time)  
Thu 24.06.2021 no lecture
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  



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 TU-Bibliothek)
    • 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 Message-Passing Systems, Springer, 2013
  • Gerard Tel. Introduction to Distributed Algorithms, Cambridge University Press, 2000
  • Sape Mullender. Distributed Systems. Addison-Wesley, 1993
  • D. Peleg. Distributed Computing: A Locality-Sensitive Approach, SIAM, Philadelphia, PA, 2000
  • Faith Fich and Eric Ruppert. Hundreds of impossibility results for distributed computing. In Distributed Computing, 16(2-3), pages 121-163, 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
Document Actions