Algorithms for Distributed Systems

Format: 2h VO + 1h PS
ECTS: 2 + 2
Teachers: Sebastian Forster (VO) and Tijn de Vos (PS)
Language: German (VO) and English (PS)
Prerequisites: Algorithms and Data Structures, Discrete Mathematics for Computer Science, Statistics for Computer Science (recommended)

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.

Lecture (VO)

Thursday 9:00-11:00, HS T02

Slides:

Lecture Notes:

Recitation (PS)

Tuesday 12:00-13:00, HS T02

The proseminar has a mandatory attendance rate of 75%. 

The grade will be based upon three homework sheets, on each of which you can collect 10 points. Additionally, on some homework sets you’ll be able to collect bonus points. In total 15 points will lead to a 4, 19 to a 3, 23 to a 2, and 27 to a 1. You are allowed to work together on these exercises, but you should indicate with whom you have collaborated. The homework sheets can be found on Blackboard (in due time). Solutions can be uploaded there as a pdf file (created with LaTeX).

Deadline Homework 1: Thursday 23.03, 23:59
Deadline Homework 2: Thursday 04.05, 23:59
Deadline Homework 3: Sunday 21.05, 23:59