# 182.702 Distributed Algorithms This course is in all assigned curricula part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_21",{id:"j_id_21",showEffect:"fade",hideEffect:"fade",target:"isAllSteop"});});This course is in at least 1 assigned curriculum part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_23",{id:"j_id_23",showEffect:"fade",hideEffect:"fade",target:"isAnySteop"});}); 2024S 2023S 2022S 2021S 2020S 2019S 2018S 2017S 2016S 2015S 2014S 2013S 2012S

2024S, VU, 4.0h, 6.0EC

## Properties

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

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

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.

## Course dates

DayTimeDateLocationDescription
Fri09:00 - 11:0001.03.2024 - 28.06.2024 Library E191-02 (Treitlstraße 1-3, 2nd floor)Lecture
Tue10:00 - 12:0005.03.2024 - 25.06.2024 Library E191-02 (Treitlstraße 1-3, 2nd floor)Lecture
Tue10:00 - 12:0007.05.2024Seminarraum Techn. Informatik Lecture
Distributed Algorithms - Single appointments
DayDateTimeLocationDescription
Fri01.03.202409:00 - 11:00 Library E191-02 (Treitlstraße 1-3, 2nd floor)Lecture
Tue05.03.202410:00 - 12:00 Library E191-02 (Treitlstraße 1-3, 2nd floor)Lecture
Fri08.03.202409:00 - 11:00 Library E191-02 (Treitlstraße 1-3, 2nd floor)Lecture
Tue12.03.202410:00 - 12:00 Library E191-02 (Treitlstraße 1-3, 2nd floor)Lecture
Fri15.03.202409:00 - 11:00 Library E191-02 (Treitlstraße 1-3, 2nd floor)Lecture
Tue19.03.202410:00 - 12:00 Library E191-02 (Treitlstraße 1-3, 2nd floor)Lecture
Fri22.03.202409:00 - 11:00 Library E191-02 (Treitlstraße 1-3, 2nd floor)Lecture
Tue09.04.202410:00 - 12:00 Library E191-02 (Treitlstraße 1-3, 2nd floor)Lecture
Fri12.04.202409:00 - 11:00 Library E191-02 (Treitlstraße 1-3, 2nd floor)Lecture
Tue16.04.202410:00 - 12:00 Library E191-02 (Treitlstraße 1-3, 2nd floor)Lecture
Fri19.04.202409:00 - 11:00 Library E191-02 (Treitlstraße 1-3, 2nd floor)Lecture
Tue23.04.202410:00 - 12:00 Library E191-02 (Treitlstraße 1-3, 2nd floor)Lecture
Fri26.04.202409:00 - 11:00 Library E191-02 (Treitlstraße 1-3, 2nd floor)Lecture
Tue30.04.202410:00 - 12:00 Library E191-02 (Treitlstraße 1-3, 2nd floor)Lecture
Fri03.05.202409:00 - 11:00 Library E191-02 (Treitlstraße 1-3, 2nd floor)Lecture
Tue07.05.202410:00 - 12:00 Library E191-02 (Treitlstraße 1-3, 2nd floor)Lecture
Tue07.05.202410:00 - 12:00Seminarraum Techn. Informatik Lecture
Tue14.05.202410:00 - 12:00 Library E191-02 (Treitlstraße 1-3, 2nd floor)Lecture
Fri17.05.202409:00 - 11:00 Library E191-02 (Treitlstraße 1-3, 2nd floor)Lecture
Fri24.05.202409:00 - 11:00 Library E191-02 (Treitlstraße 1-3, 2nd floor)Lecture

## Examination modalities

Solution and presentation of homework assignments + reviewing (upload .pdf via myTI) + written tests + written exam.

## Course registration

Begin End Deregistration end
07.03.2024 08:00 17.03.2024 23:59

## Curricula

Study CodeObligationSemesterPrecon.Info
066 504 Master programme Embedded Systems Not specified
066 931 Logic and Computation Mandatory elective
066 932 Visual Computing Mandatory elective
066 937 Software Engineering & Internet Computing Mandatory elective
066 938 Computer Engineering Mandatory elective
860 GW Optional Courses - Technical Mathematics Not specified

## 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).

English