Algorithms for Distributed SystemsModulbeschreibung #41127 / Version 1
- 6 LP
- Mündliche Prüfung
- Benotet
- Wintersemester
- Englisch
Diese Modulbeschreibung gilt nicht im aktuellen Semester (WiSe 2026/27).
Zur aktuellen Version (v3)
| Modul / Version | #41127 / #1 |
|---|---|
| Gültigkeit | WiSe 2023/24 – SoSe 2024 |
| Verfügbare Sprache(n) | Englisch |
| Leistungspunkte | 6 |
| Modulverantwortliche*r | Schmid, Stefan |
| Benotung | Benotet |
| Prüfungsform | Mündliche Prüfung |
| Lehrsprache(n) | Englisch |
Zugehörigkeit
| Fakultät | Fakultät IV |
|---|---|
| Institut | Institut für Telekommunikationssysteme |
| Fachgebiet | 34331700 FG Intelligent Networks and Management of Distributed Systems (INET) |
Kontakt
| Sekretariat | EN 18 |
|---|---|
| Ansprechpartner*in | Schmid, Stefan |
| E-Mail-Adresse | stefan.schmid@tu-berlin.de |
| Webseite | https://www.tu.berlin/eninet |
Lernergebnisse
Most modern computer systems are inherently distributed and networked, including multi-core computers, machine-learning clusters, wireless sensorsystems, datacenters, peer-to-peer systems, blockchain or cryptocurrencies, to just give some examples. In order to operate correctly and efficiently, all these systems rely on clever algorithms. Some of the underlying algorithms are fundamentaland are used by most of the systems, others are specialized and exploit specific features of the particular distributed system.
The goal of the module is to provide the students with tools and techniques to reason about efficient algorithms for distributed systems.
The lecture is problem-oriented and structured into different fundamental principles, such as Distributed Coordination, Decentralization, Randomization, etc. Each lecture will cover a different basic problem (such as Load Balancing, Leader Election, Symmetry Breaking, etc., arising in various different applications, from the Internet over distributed data analytics to sensor networks) and will be self-contained.
By the end of the lecture, the student will be able to develop her/his own distributed algorithms, and formally prove correctness as well as complexity guarantees (e.g., on the computational complexity or the communication complexity).
The students will also have a good understanding of when to apply which principle, i.e., where randomization can be useful and where not, or to which extent a distributed system should be decentralized. The students will further have a good idea of the different natures of today's distributed systems. If time permits, we will also extend our discussion beyond computer systems and have an algorithmic look at social and biological networks.
This module is principally designed to impart:
technical skills: 40x, method skills: 40x, system skills 10x, social skills 10x
The goal of the module is to provide the students with tools and techniques to reason about efficient algorithms for distributed systems.
The lecture is problem-oriented and structured into different fundamental principles, such as Distributed Coordination, Decentralization, Randomization, etc. Each lecture will cover a different basic problem (such as Load Balancing, Leader Election, Symmetry Breaking, etc., arising in various different applications, from the Internet over distributed data analytics to sensor networks) and will be self-contained.
By the end of the lecture, the student will be able to develop her/his own distributed algorithms, and formally prove correctness as well as complexity guarantees (e.g., on the computational complexity or the communication complexity).
The students will also have a good understanding of when to apply which principle, i.e., where randomization can be useful and where not, or to which extent a distributed system should be decentralized. The students will further have a good idea of the different natures of today's distributed systems. If time permits, we will also extend our discussion beyond computer systems and have an algorithmic look at social and biological networks.
This module is principally designed to impart:
technical skills: 40x, method skills: 40x, system skills 10x, social skills 10x
Lehrinhalte
The lectures revolve around fundamental problems and design principles. A tentative outline of the main topics to be covered in the course are
* Models for Distributed Systems: from shared-memory over datacenter applications to Internet-scale systems
* Algorithmic techniques for small ("shared memory") and large distributed systems ("distributed graph algorithms")
* Decentralization: why and how? Complexity Measures
* Randomization: why and how? Basic Tools
* Algorithms: Local Algorithms, Random Algorithms, Online Algorithms, Dynamic Programming
* Distributed Algorithms for Leader Election, Coloring, Maximal Independent Sets, Medium Access
* Resource Allocation and Embedding (e.g., energy, bandwidth, CPU)
* Social and Biological Networks: An Algorithmic Perspective
* Models for Distributed Systems: from shared-memory over datacenter applications to Internet-scale systems
* Algorithmic techniques for small ("shared memory") and large distributed systems ("distributed graph algorithms")
* Decentralization: why and how? Complexity Measures
* Randomization: why and how? Basic Tools
* Algorithms: Local Algorithms, Random Algorithms, Online Algorithms, Dynamic Programming
* Distributed Algorithms for Leader Election, Coloring, Maximal Independent Sets, Medium Access
* Resource Allocation and Embedding (e.g., energy, bandwidth, CPU)
* Social and Biological Networks: An Algorithmic Perspective
Modulbestandteile
Pflichtbereich
Die folgenden Veranstaltungen sind für das Modul obligatorisch:
| Lehrveranstaltungen | Art | Nummer | Turnus | Sprache | SWS | VVZ |
|---|---|---|---|---|---|---|
| Algorithms for Distributed Systems | Integrierte Veranstaltung | 432 L 818 | Wintersemester | [en] | 4 | ISIS |
Arbeitsaufwand und Leistungspunkte
Algorithms for Distributed Systems (Integrierte Veranstaltung)
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Attendance lecture | 15 | 2 h | 30 h |
| Attendance tutorial | 15 | 2 h | 30 h |
| Solving excercises | 15 | 4 h | 60 h |
| Preparation and rework of the lecture | 15 | 3 h | 45 h |
| Preparation for the exam | 1 | 15 h | 15 h |
| 180 h | |||
Der Aufwand des Moduls summiert sich zu 180 Stunden. Damit umfasst das Modul 6 Leistungspunkte.
Beschreibung der Lehr- und Lernformen
* Common lecture
* Exercises and/or programming assignments: to be issued weekly; half to be solved individually and half to be solved in groups of 2 (if the class has an odd number of participants then there will be a group of 3); to be graded by the instructor; solutions to be jointly discussed (by instructor + students) during the tutorials * English language for both the lecture and the tutorials.
* Exercises and/or programming assignments: to be issued weekly; half to be solved individually and half to be solved in groups of 2 (if the class has an odd number of participants then there will be a group of 3); to be graded by the instructor; solutions to be jointly discussed (by instructor + students) during the tutorials * English language for both the lecture and the tutorials.
Voraussetzungen für die Teilnahme / Prüfung
Wünschenswerte Voraussetzungen für die Teilnahme an den Lehrveranstaltungen:
* Modul "Diskrete Strukturen" oder Modul "Algorithmen und Datenstrukturen"
* Modul "Rechnernetze und Verteilte Systeme"
* Modul "Network Architectures - Basics"
* Gute Englischkenntnisse
* Modul "Rechnernetze und Verteilte Systeme"
* Modul "Network Architectures - Basics"
* Gute Englischkenntnisse
Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:
Dieses Modul hat keine Prüfungsvoraussetzungen.
Abschluss des Moduls
| Benotung | Benotet |
|---|---|
| Prüfungsform | Mündliche Prüfung |
| Sprache | Englisch |
| Dauer/Umfang | 30 min. |
Dauer des Moduls
Für Belegung und Abschluss des Moduls ist folgende Semesteranzahl veranschlagt: 1 Semester.
Dieses Modul kann in folgenden Semestern begonnen werden: Wintersemester.
Maximale teilnehmende Personen
Die maximale Teilnehmerzahl beträgt 60.
Anmeldeformalitäten
Registration for the course on ISIS. Registration for the complete module on MOSES / QISPOS / registration office.
Literaturhinweise, Skripte
Skript in Papierform
nicht verfügbar
Skript in elektronischer Form
verfügbar
Empfohlene Literatur
- Mitzenmacher, Michael. Upfal, Eli: Probability and Computing. Cambridge University Press, 2005.
- Newman, Mark: Networks. 2nd ed. Oxford University Press, 2018 - https://global.oup.com › networks-9780198805090
- Peleg, David: Distributed Computing - A Locality-Sensitive Approach, SIAM 2000
Zugeordnete Studiengänge
Dieses Modul findet in keinem Studiengang Verwendung.
Sonstiges
Keine Angabe