182.702 Distributed Algorithms
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2021S, VU, 4.0h, 6.0EC
TUWEL

Properties

  • Semester hours: 4.0
  • Credits: 6.0
  • Type: VU Lecture and Exercise
  • Format: Hybrid

Learning outcomes

After successful completion of the course, students are able to...

  • understand fundamental models, problems, algorithms, lower bound and impossibility results, and proof techniques in distributed computing,
  • apply lower bounds and impossibility results learned to new situations where appropriate,
  • design new distributed algorithms for new situations, using the algorithms and techniques learned as building blocks, and
  • find new lower bounds and impossibility results.

Subject of course

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.

Teaching methods

The course is organized in the "anglo-american style", which is based on continuous engagement during the whole semester: Several quizzes, student presentations 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.

Mode of examination

Immanent

Additional information

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.

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Thu08:00 - 10:0004.03.2021 - 24.06.2021EI 10 Fritz Paschke HS - BI Distributed Algorithms
Fri08:00 - 10:0005.03.2021 - 25.06.2021EI 10 Fritz Paschke HS - BI Distributed Algorithms
Distributed Algorithms - Single appointments
DayDateTimeLocationDescription
Thu04.03.202108:00 - 10:00EI 10 Fritz Paschke HS - BI Distributed Algorithms
Fri05.03.202108:00 - 10:00EI 10 Fritz Paschke HS - BI Distributed Algorithms
Thu11.03.202108:00 - 10:00EI 10 Fritz Paschke HS - BI Distributed Algorithms
Fri12.03.202108:00 - 10:00EI 10 Fritz Paschke HS - BI Distributed Algorithms
Thu18.03.202108:00 - 10:00EI 10 Fritz Paschke HS - BI Distributed Algorithms
Fri19.03.202108:00 - 10:00EI 10 Fritz Paschke HS - BI Distributed Algorithms
Thu25.03.202108:00 - 10:00EI 10 Fritz Paschke HS - BI Distributed Algorithms
Fri26.03.202108:00 - 10:00EI 10 Fritz Paschke HS - BI Distributed Algorithms
Thu15.04.202108:00 - 10:00EI 10 Fritz Paschke HS - BI Distributed Algorithms
Fri16.04.202108:00 - 10:00EI 10 Fritz Paschke HS - BI Distributed Algorithms
Thu22.04.202108:00 - 10:00EI 10 Fritz Paschke HS - BI Distributed Algorithms
Fri23.04.202108:00 - 10:00EI 10 Fritz Paschke HS - BI Distributed Algorithms
Thu29.04.202108:00 - 10:00EI 10 Fritz Paschke HS - BI Distributed Algorithms
Fri30.04.202108:00 - 10:00EI 10 Fritz Paschke HS - BI Distributed Algorithms
Thu06.05.202108:00 - 10:00EI 10 Fritz Paschke HS - BI Distributed Algorithms
Fri07.05.202108:00 - 10:00EI 10 Fritz Paschke HS - BI Distributed Algorithms
Thu20.05.202108:00 - 10:00EI 10 Fritz Paschke HS - BI Distributed Algorithms
Fri21.05.202108:00 - 10:00EI 10 Fritz Paschke HS - BI Distributed Algorithms
Thu27.05.202108:00 - 10:00EI 10 Fritz Paschke HS - BI Distributed Algorithms
Fri28.05.202108:00 - 10:00EI 10 Fritz Paschke HS - BI Distributed Algorithms

Examination modalities

Solution of homework assignments + reviewing (upload .pdf via myTI) + quizzes (via ZOOM, upload scan (.pdf) of solution in TUWEL)+ student presentations (via ZOOM). Requires ZOOM basic setup, scanner with .pdf output for upload in TUWEL and, if possible, a printer for the quiz assignments. Details see course webpage.

Course registration

Begin End Deregistration end
25.02.2021 08:00 07.03.2021 23:59

Curricula

Literature

Textbook: Hagit Attiya, Jennifer Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd ed.), John Wiley and Sons, 2004. ISBN 0-471-45324-2

Previous knowledge

Familiarity with the analysis of sequential algorithms and elementary discrete mathematics; reasonable skills in devising mathematical proofs. Some background in distributed systems and fault-tolerant systems is helpful but not required. Familiarity with the basics of scientific working (LaTeX, reviewing).

Preceding courses

Miscellaneous

Language

English