Distributed Algorithms (VALG - 182.702)
[TISS-Seite] [TISS Syllabus] [Background info] [Enrolling] [Grading] [SCHEDULE] [HOMEWORK] [Other resources]
News
Slightly updated version of my lecture slides available (minor error corrections & clarifications)
Updated assignment for Homework 1 (some error correction, clarification & additional hints).
About:
- Some successes of former VALG participants
- Result of the course evaluation (using this questionaire): SS09 SS10 SS11 SS12 SS13 SS14 SS15 SS16 SS17
- 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
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 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 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.
Most importantly, 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 advance knowledge. Although this does of course not mean that you have to know all 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 checking topics taught so far).
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:
- 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 (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:
- A 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 |
Fri | 01.03.2019 | 08:30 | Lecture Introduction | Intro slides |
Thu | 07.03.2019 | 08:30 | Lecture Basics (1) | 2 |
Fri | 08.03.2019 | 08:30 | Quiz 1: Chapter 2 + Prerequisites | |
Lecture Basics (2) | 2 | |||
23:59 | Announcement Homework 1 | |||
Thu | 14.03.2019 | 08:30 | Lecture Basics (3) | 2 |
Clarification Homework 1 | ||||
Fri | 15.03.2019 | 08:30 | Lecture Basics (4) | 2 |
Thu | 21.03.2019 | 08:30 | Lecture Leader election in rings (1) | 3 |
Fri | 22.03.2019 | 08:30 | Quiz 2: Chapter 3 + 2 | |
Lecture Leader election in rings (2) | 3 | |||
Thu | 28.03.2019 | 08:30 | Lecture Leader election in rings (3) | 3 |
Fri | 29.03.2019 | 08:30 | no lecture | 3 |
Wed | 03.04.2019 | 23:59 | First version Homework 1 due | |
Thu | 04.04.2019 | 08:30 | Lecture Mutual exclusion in shared memory (1) | 4 |
23:59 | Announcement Homework 2 | |||
Fri | 05.04.2019 | 08:15-11:00 | Presentation Homework 1 | |
Clarification Homework 2 | ||||
Thu | 11.04.2019 | 08:30 | no lecture | |
Fri | 12.04.2019 | 08:30 | Quiz 3: Chapter 4 + 3 | |
Lecture Mutual exclusion in shared memory (2) | 4 | |||
Thu | 18.04.2019 | 23:59 | Reviews Homework 1 due | |
Wed | 01.05.2019 | 23:59 | First version Homework 2 due | |
Thu | 02.05.2019 | 08:30 | Lecture Mutual exclusion in shared memory (3) | 4 |
23:59 | Final version Homework 1 due | |||
23:59 | Announcement Homework 3 | |||
Fri | 03.05.2019 | 08:15-11:00 | Presentation Homework 2 | |
Clarification Homework 3 | ||||
Thu | 09.05.2019 | 08:30 | Lecture Mutual exclusion in shared memory (4) | 4 |
Fri | 10.05.2019 | 08:30 | Lecture Mutual exclusion in shared memory (5) | 4 |
Thu | 16.05.2019 | 08:30 | Quiz 4: Chapter 5 + 4 | |
23:59 | Shepherding review Homework 1 due | |||
Fri | 17.05.2019 | 08:30 | Lecture Fault-tolerant consensus (1) | 5 |
23:59 | Reviews Homework 2 due | |||
Wed | 22.05.2019 | 23:59 | First version Homework 3 due | |
Thu | 23.05.2019 | 08:30 | Lecture Fault-tolerant consensus (2) | 5 |
23:59 | Announce Homework 4 | |||
Fri | 24.05.2019 | 08:15-11:00 | Presentation Homework 3 | |
Clarification Homework 4 | ||||
Thu | 30.05.2019 | No lecture | ||
Fri | 31.05.2019 | 23:59 | Final version Homework 2 due | |
Thu | 06.06.2019 | 08:30 | Lecture Fault-tolerant consensus (3) | 5 |
Fri | 07.06.2019 | 08:30 | Lecture Fault-tolerant consensus (4) | 5 |
23:59 | Reviews Homework 3 due | |||
Thu | 13.06.2019 | 08:30 | Quiz 5: Chapter 6 + 5 | |
Lecture Causality and time (1) | 6 | |||
Fri | 14.06.2019 | 08:30 | Lecture Causality and time (2) | 6 |
23:59 | Announcement [optional] Homework 5 | |||
23:59 | Shepherding reviews Homework 2 due | |||
Wed | 19.06.2019 | 23:59 | First version Homework 4 due | |
Thu | 20.06.2019 | No lecture | ||
Fri | 21.06.2019 | 08:15-11:00 | Presentation Homework 4 | |
Clarification Homework 5 | ||||
23:59 | Final version Homework 3 due | |||
Thu | 27.06.2019 | 08:30 | Lecture Causality and time (3) | 6 |
Fri | 28.06.2019 | 08:30 | Final exam: Chapters 2 - 6 | |
Sun | 30.06.2019 | 23:59 | Reviews Homework 4 due | |
23:59 | Shepherding reviews Homework 3 due | |||
until | 07.07.2019 | 23:59 | Final version Homework 4 due | |
until | 14.07.2019 | 23:59 | Shepherding review Homework 4 due | |
until | 14.07.2019 | 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
- 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:
Document Actions
Miscellaneous: