Distributed Algorithms (VALG - 182.702)

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

News

March 15, 2023: Please note that, starting with SS2023, the gatekeeper for the key area Dependable Distributed Systems in the Master Computer Engineering (Technische Informatik) will be switched from this course to the (already mandatory) course Advanced Multiprocessor Systems. Courses from the Wahlmodul Dependable Distributed Systems can hence be chosen freely.

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 SS21
• Ein Benchmark VALG vs. einschlägige LVAs an international renommierten Universitäten [in German]

 

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). 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 ("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.

Presence in the on-line classes is mandatory. Unusual circumstances must be discussed in advance with me, and all excused 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. 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.]

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 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 file 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 (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.
   • Bring along a paper copy, including the title page (use hw.tex), which must be duly signed, in the lecture 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).
   • 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 (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.
• Bring along a paper copy, including the title page (use hw.tex), which must be duly signed, in the next lecture after the deadline.

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 (UNDER CONSTRUCTION!!!)

The schedule of the course 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 lecture room EI 10 (Fritz Paschke HS, Neues EI, Gusshausstrasse 27-29). Lecture and quizzes are usually on Thursday (13:15-14:45) and Friday (9:15-10:45 and sometimes 13:15-14:45); homework presentations are always on Friday.

 

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 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

• 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 world-wide-web: Most papers are available on-line and freely accessible for academic institutions like TU Vienna. Here are some very useful links:
• IEEE Xplore
• ACM Digital Library
• DBLP

Document Actions

Miscellaneous:

• TI Research Presentations