Distributed Algorithms

Format: 3h UV
ECTS: 5
Teachers: Sebastian Forster and Martin Grösbacher
Language: German and English
Prerequisites: Algorithms and Data Structures, Discrete Mathematics for Computer Science, Statistics for Computer Science (recommended)
Contact:

This course introduces algorithmic questions and techniques in distributed systems. In particular, we consider algorithms for physically distributed systems in which (a) communication between processors is the major bottleneck and (b) every processor only has a local view of the communication network. These types of systems are relevant if the amount of data to store and process is too big for a centralized architecture. Topics: Leader Election, CONGEST Model, Synchronization, Maximal Independen Set, Graph Spanners, Shortest Path Algorithms, Rumor Spreading.

The compulsory attendance rate for this course 75%. The course integrates a lecture part and a tutorial part and the latter consists of theoretical and programming exercises.

Lecture

Monday 11:15-12:45, SR T04

Slides:

Lecture Notes:

Tutorial

Monday 13:00-13:45, SR T04

The proseminar has a mandatory attendance rate of 75%.

The grade will be based upon three homework sheets, each of which consists of four exercises and lets you collect a total of 15 points. Additionally, on some homework sheets you will be able to collect bonus points. In total, at least 27 points will lead to a 4, 31 to a 3, 35 to a 2, and 40 to a 1. You are allowed to work together on these exercises but in that case you must indicate with whom you have collaborated. This includes referencing scientific papers and their authors that gave you ideas for solutions from the internet. Also, it is mandatory to write up the solutions yourself even in the case of collaborating, i.e. plagiarism is not allowed. The homework sheets are to be submitted via the email address mentioned as contact above. They will be made available here on the website in due time. Solutions can be uploaded there as a pdf file (created with LaTeX or readably written by hand and scanned). The deadlines for the homeworks will be announced a few weeks in advance here on the page. The non-homework exercises will also be made visible here on the page at least one week prior to discussing them.