Distributed Algorithms (VALG - 182.702)

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

News

May 7: I re-shuffled the lectures in the schedule, please have a look!

April 30: For some reasons, the Nextcloud group VALG-2020S has disappeared(?). I created a new one, the link is this one.

March 26: You should be able to enroll to this class in myTI now, please act until March 31, 23:59.

March 25: Since I was a bit behind the schedule, I decided to extend the deadline for the submission of the first version of Homework 1 by one week (from April 1 to April 8). Moreover, I need to shorten the lecture on April 2 and extend the lecture on April 3 accordingly, see the schedule below.

CV NEWS (Updated March 18): I was told that TU Wien's Nextcloud (accessible from within TU Wien and via our VPN) works better than Skype. I have hence setup a conversation group VALG-2020S - please join it either by logging in at this URL (using "TU Password Auth") or as a guest using this link so that we can give it a try.

CV NEWS (March 16): The new TU rules force me to cancel Quiz2 and Quiz3. However, unless even stricter rules will be released, it will continue with LectureTube Live as planned. Unfortunately, nobody except me will be able to enter the lecture room :-).

March 14: Since I am behind my regular schedule by one lecture, I re-shuffled the schedule before the Easter break a bit: Since the Presentation of Homework 1 needs to be canceled due to CV anyway, I decided to move Quiz2 (now March 26) and Quiz3 (now April 3). Please adjust your calendar accordingly.

CV NEWS (updated March 12): I will do live streaming of my lecture (that will take place exactly as given in the schedule below) in EI10 via LectureTube Live. I have created a TUWEL course VALG-2020S for this purpose, which provides an RSSPlayer (JWPlayer) that you can use for watching the lecture. (Unfortunately, JWPlayer requires Adobe Flash, which is not supported under Linux any more. Thanks to Aron, however, we discovered the option of using the VLC media player on this URL). Please register for the TUWEL course asap.

As I don't like lecturing in an empty room (hence, I won't kick out people - and will bring a muppet of "Die Maus" along to have at least some audience :-)), I hope that TU Wien will assist us in implementing also a suitable back channel. At the beginning, we are going to use Skype for this purpose - I created a Skype chat group VALG-2020S  that you should join as well. I will initiate a group call at the beginning of every lecture that we can use for interaction during my presentation - let's see how this works.

CV NEWS (March 10): Since regular teaching at TU Wien will be shut down starting Wed March 11, 2020, I will not be able to teach this class as planned. Nevertheless, the rules seem to say that the "Prüfungsbetrieb" can be continued, provided the safety regulations (sufficient spatial separation etc.) are observed. Given that EI10 is large, I intend to do Quiz1 as planned - unless officials tell me otherwise. So please come on Thursday to EI10 at 8:30 as planned - I will try to teach the course as regularly as I can. Stay tuned for further news.

About:

 

Aim

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.

All who want to participate in the course in the next summer term: Please subscribe to the TISS LVA-Forum & News already before the semester holidays. [Enrolling (via myTI) is only possible when the course has already started (and the admission criteria are met).]

ECTS breakdown (6 ECTS = 150 hours):

 30h             Lecture time
   4.5h          6 Quizzes
 12h             4 Homework presentations
 18h             Preparation time for 6 Quizzes
 85.5h          Preparation time for 4 Homework-Assignments  (3-5 exercises each): First and final version (in LaTeX); reviewing.

Subject

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.

Lecturer

Prof. Ulrich Schmid

Homepage

https://ti.tuwien.ac.at/ecs/teaching/courses/valg 

 

BACKGROUND INFO

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). VALG is essentially a considerably downscaled version of Jennifer Welch's course at Texas A&M University.The emphasis is on proving upper and lower bounds on complexity measures and impossibility results, as well as proving the correctness of distributed algorithms.

Prerequisites are familiarity with the complexity analysis of sequential algorithms (level of 186.813 Algorithms and Datastructures 1) 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 182.697 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.

Aims & scope and requirements are different from the undergraduate courses you are probably most familiar with. Master curricula like Technische Informatik have a clear focus on scientific education, and basic courses like VALG contribute to the development of the appropriate formal/mathematical skills. In sharp contrast to undergraduate courses where knowledge acquisition is more or less "push-based", master courses like VALG are hence "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 make sure that you do advance reading of the relevant chapters of the textbook. 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 questions in the quizzes at the beginning of every chapter shall encourage you to do this reading (in addition to detailed questions on the previous chapter taught in the lectures before the quiz, which refer to the content of my slides, of course).

Presence in class is mandatory. Unusual circumstances must be discussed in advance with me, and all excused (= to be certified) absences 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, unless otherwise instructed. 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 and exams, 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 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 enroll to the first and second quiz -- everybody who complies to (1) is eligible here. All participants who passed the above course admission criterion must enroll via myTI.

GRADING

Grading will be based on the following components:

  • Homework assignments (45%): There will be 5 paper exercises, one per chapter, to be worked out in LaTeX and presented in class (33%) and reviewed by other participants (12%); the details can be found below. Late assignments will not be graded!
  • Quizzes (40%): There will be 5 short quizzes in class (20-25 min.), consisting of a few simple questions (for example, short answer, true-false, or multiple choice) concerning (1) the advance reading and (2) detailed knowledge of the material recently covered. 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. There will be no make-up quizzes, but the lowest grade will be dropped.
  • Final exam (15%): There will be a final exam (40-50 min.), with questions similar to the ones in the standard quizzes, but covering all the material taught in the course.

You will find your 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); the grades for the first two quizzes can be found here. Note that participation in discussions in class etc. is also taken into account (at most +/- 10% of total points) when assigning the final grade, which 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 files of the first homework assignment can be found here, 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 (either in English or in German). Correctness, clarity of exposition and general presentation will be evaluated in the reviewing process, so take care of those issues! Deliver your solutions (hwXfirst.pdf) by the scheduled time (late assignments will not be graded!), both:
  • A paper copy, including the title page (use hw.tex), which must be duly signed and given to me in class at the day before the homework presentation (if there is no class at that day, it suffices to bring it along at the day of the homework presentation - I will print the on-line versions for my reading in this case).
  • An electronic version (.pdf), without the title page (use hwnotitle.tex), for anonymous reviewing, which must be uploaded using myTI by the deadline.
  • Present your solutions, on my request, on blackboard in class at the scheduled presentation time [please make sure that you bring your own copy of your solutions along, since I will need "my" copy for taking notes]. Note that this presentation has two purposes: (1) To give you an additional opportunity to find out whether your solution is OK, and (2) to allow me to find out whether it is really your solution [I may of course ask questions that help me to find out]; please note that unsuccessful attempts to sell a solution that is not yours will lower the grade achievable for all the homework. However, the grade assigned for presentations will not be lowered when your solution contains errors. [Incorrect solutions will lower the grade assigned for hwXfirst and, in particular, for hwXfinal, however.] Since the reviewers may fail to spot certain errors in your hwXfirst, you should hence be eager to get feedback from the presentations in order to arrive at a correct hwXfinal. So please make sure that you participate actively here, e.g., by volunteerly presenting/proposing alternative solutions.
  • Carefully review hwXfirst of your colleagues (anonymously) assigned to you, and submit the reviews via myTI by the deadline (please use German only if the reviewed hwXfirst is in German). 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.
  • Carefully prepare a revision of your homework, based on the feedback you got from the reviews and the additional information obtained during the presentations in class. 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. The final version of your homework must also include a (single) grade and some explanatory text for every 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!), both as:
  • paper copy, including the title page (use hw.tex), which must be duly signed and given to me in the next class after the deadline.
  • An electronic version (.pdf), without the title page (use hwnotitle.tex), for shepherding, which must be uploaded using myTI by the deadline.
  • You will be assigned the final version hwXfinal of every homework you reviewed in Step 4 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 (still tentative) is shown in the table below; please note that it may occasionally change slightly throughout the semester. All lectures, presentations etc. take place at the EI10 (Fritz Paschke HS, Gusshausstrasse 25-29). Lecture and quizzes are on Thursday and Friday (8:30-10:00 or sometimes 8:30-11:00), whereas homework presentations take place on Friday (8:15-11:00).

 

Day

Date

Time

Topic

Chapter (book)

Thu 05.03.2020 08:30 Lecture Introduction Intro slides
Fri 06.03.2020 08:30 Lecture Basics (1) 2
Thu 12.03.2020 08:30 Quiz 1: Chapter 2 + Prerequisites  
      Lecture Basics (2) 2
Fri 13.03.2020 08:30-11:00 Lecture Basics (3) 2
    23:59 Announcement Homework 1  
Thu 19.03.2020 08:30 Lecture Basics (4) 2
Clarification Homework 1
Fri 20.03.2020 08:30-11:00 Lecture Basics (5), Leader election in rings (1) 2, 3
Thu 26.03.2020 08:30 Canceled due to CV: Quiz 2: Chapter 3 + 2
Lecture Leader election in rings (2) 3
Fri 27.03.2020 08:30 Lecture Leader election in rings (3) 3
Wed 01.04.2020 23:59 Announcement Homework 2  
Thu 02.04.2020 no lecture
Fri 03.04.2020 08:30-11:00 Lecture Leader election in rings (4) 3
  Clarification Homework 2
Lecture Mutual exclusion in shared memory (1) 4
Canceled due to CV: Quiz 3: Chapter 4 + 3
Wed 08.04.2020 23:59 First version Homework 1 due
    Canceled due to CV: Presentation Homework 1  
Thu 16.04.2020 23:59 Reviews Homework 1 due
Thu 23.04.2020 08:30 Lecture Mutual exclusion in shared memory (2) 4
23:59 Announcement Homework 3
Fri 24.04.2020 08:30 Lecture Mutual exclusion in shared memory (3) 4
Clarification Homework 3
Thu 30.04.2020 08:30 Lecture Mutual exclusion in shared memory (4) 4
23:59 Final version Homework 1 due
Wed 06.05.2020 23:59 First version Homework 2 due  
Thu 07.05.2020 08:30 Canceled due to CV: Quiz 4: Chapter 5 + 4
Lecture Fault-tolerant consensus (1) 5
Fri 08.05.2020 08:30 Lecture Fault-tolerant consensus (2) 5
  Canceled due to CV: Presentation Homework 2
Thu 14.05.2020 08:30 Lecture Fault-tolerant consensus (3) 5
23:59 Shepherding review Homework 1 due
Announce Homework 4
Fri 15.05.2020 08:30 Lecture Fault-tolerant consensus (4) 5
Clarification Homework 4
Thu 21.05.2020 23:59 Reviews Homework 2 due  
Wed 27.05.2020 23:59 First version Homework 3 due  
Thu 28.05.2020 08:30 no lecture
Fri 29.05.2020 08:30 Lecture Causality and time (1) 6
  Canceled due to CV:Presentation Homework 3
Thu 04.06.2020 08:30 Canceled due to CV: Quiz 5: Chapter 6 + 5  
Lecture Causality and time (2) 6
23:59 Final version Homework 2 due  
Fri 05.06.2020 08:30 Lecture Causality and time (3) 6
Wed 10.06.2020 23:59 First version Homework 4 due
Thu 11.06.2020 no lecture
23:59 Announcement [optional] Homework 5
Fri 12.06.2020 08:30 Lecture Causality and time (4)  
  Canceled due to CV:Presentation Homework 4
23:59 Reviews Homework 3 due
Thu 18.06.2020 08:30 no lecture 6
Clarification Homework 5
23:59 Shepherding reviews Homework 2 due
Fri 19.06.2020 08:30 no lecture 6
Sun 21.06.2020 23:59 Reviews Homework 4 due  
Thu 25.06.2020   no lecture  
    23:59 Final version Homework 3 due  
Fri 26.06.2020 08:30 Final exam: Chapters 2 - 6
Thu 05.07.2020 23:59 Final version Homework 4 due  
Fri 03.07.2020 23:59 Shepherding reviews Homework 3 due  
until 13.07.2020 23:59 Shepherding review Homework 4 due  
until 16.07.2020 23:59 Final version [optional] Homework 5 due  

 

OTHER RESOURCES

Scientific writing:

  • Our seminar "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 (www.springerlink.com/index/P8F078J3KQCNEV0F.pdf)

 

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

Miscellaneous: