Models and Theory of Distributed Algorithms (6 LP)Module description #40578 / Version 5
- 6 CP
- Portfolio examination
- Graded
- Winter semester
- English, German
This module description is not valid in the current semester (Winter semester 2026/27).
| Module / Version | #40578 / #5 |
|---|---|
| Validity | SS 2017 – WS 2019/20 |
| Available language(s) | German |
| Credit points | 6 |
| Person responsible for the module | Nestmann, Uwe |
| Grading | Graded |
| Exam format | Portfolio examination |
| Language(s) of instruction | English, German |
Affiliation
| Faculty | Fakultät IV |
|---|---|
| Institute | Institut für Softwaretechnik und Theoretische Informatik |
| Academic chair | 34351900 FG Modelle und Theorie Verteilter Systeme (MTV) |
Contact
| Office | TEL 7-2 |
|---|---|
| Contact person | Nestmann, Uwe |
| E-mail address | lehre@mtv.tu-berlin.de |
| Website | http://www.mtv.tu-berlin.de/menue/lehre/module/distalgo/ |
Learning outcomes
Successful participants of this module dispose of knowledge and capabilities on the formal modeling and formal analysis of distributed, and in particular fault-tolerant, algorithms. Moreover, they dispose of deeper knowledge and understanding about formal proofs of correctness and impossibility results concerning distributed communication and coordination problems. They are capable to acquire the necessary pieces of knowledge partially independently by themselves and to orally present their results.
Content
In essence, this module takes selected chapters from a well-known text book on distributed algorithms and tackles their formalisation such that they become accessible to a deep understanding of the underlying computation models. As a side effect, this activity enables formal proofs that may possibly even form the basis of a verification by means of a mechanical proof checker. More concretely, the topics cover:
- synchronous and asynchronous communication
- process models
- models of failure and failure detection
- leader election
- reliable broadcast
- consensus
- synchronous and asynchronous communication
- process models
- models of failure and failure detection
- leader election
- reliable broadcast
- consensus
Module components
Compulsory area
The following courses are mandatory for this module:
| Courses | Type | Number | Frequency | Language | Hours per week | Course catalog |
|---|---|---|---|---|---|---|
| Modelle und Theorie Verteilter Algorithmen | Integrated course | Winter semester | – | 4 | ISIS |
Workload and credit points
Modelle und Theorie Verteilter Algorithmen (Integrated course)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Modellierung und Formalisierung | 15 | 6 h | 90 h |
| Präsenzzeit | 15 | 4 h | 60 h |
| 150 h | |||
Course-independent workload
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Prüfungsvorbereitung | 1 | 30 h | 30 h |
| 30 h | |||
The workload of the module adds up to 180 hours. The module therefore comprises 6 credit points.
Description of teaching and learning methods
Die Veranstaltung ist betont interaktiv konzipiert. Sie besteht aus einer flexiblen Abfolge von Vorlesungs-und Übungsanteilen sowie offenen projektartigen Komponenten, in denen die Studierenden zusammen mit dem Dozenten eigene Vorschläge und Ideen entwickeln. Insofern ist es das Ziel der Veranstaltung, exemplarisch den Alltag eines Forschers der Theoretischen Informatik im ausgewählten Gebiet beispielhaft nachzuvollziehen. Diese Arbeit beinhaltet neben der konzeptionellen Erarbeitung von formalen Modellen deren kritischer Überprüfung durch Tests und mathematische Beweise, als auch der sorgfältigen Darstellung dieser Arbeiten im Rahmen eines gemeinsam durch die Teilnehmer zu erstellenden LaTeX-Dokumentes.
Requirements for participation and examination
Desirable prerequisites for participation in the courses:
Inhaltlich werden Kenntnisse aus der Theoretischen Informatik zu Diskreten Strukturen, Logik, und Automatentheorie vorausgesetzt. Nützlich wären auch bereits existierende Kenntnisse zu Verteilten Algorithmen (aus dem Angebot der Fachgebiete CIT oder KBS), Nebenläufiger Programmierung (beispielsweise in Java), sowie Prozesskalkülen und Temporaler Logik (Module "Reaktive Systeme" und "Algebraische Prozesskalküle").
Mandatory requirements for the module examination registration:
This module has no examination requirements.
Completion of the module
| Grading | Graded |
|---|---|
| Exam format | Portfolio examination |
| Type of portfolio examination | 100 points in total |
| Language | English, German |
Test elements
| Name | Points/Weight | Category | Duration/Extent |
|---|---|---|---|
| (Ergebnisprüfung) Projektbericht als Gruppen-Abgabe | 30 | written | 20-50 Seiten LaTeX |
| (Ergebnisprüfung) Projektbericht als Gruppen-Fortschrittsbericht nach Hausaufgabe | 20 | flexibel | 45 Minuten |
| (Lernprozessevaluation) Mündliche Rücksprache | 50 | oral | 30-40 Minuten |
Duration of the module
The following number of semesters is estimated for taking and completing the module: 1 semester(s).
This module can be started in the following semesters: Winter semester.
Maximum number of participants
The maximum capacity of participants is 15.
Registration procedures
Die Teilnahme an der Lehrveranstaltung (nicht zu verwechseln mit der Modulprüfung) wird über einen ISIS-Kurs gesteuert. Die entsprechenden Zugangskoordinaten werden zu Beginn des Moduls bekanntgegeben und 3-4 Wochen lang offen gehalten.
Recommended reading, lecture notes
Lecture notes
unavailable
Electronic lecture notes
unavailable
Recommended literature
- Lynch, Nancy: Distributed Algorithms. Morgan Kaufmann Publishers, 1996
Assigned programs
This module is not used in any program.
Miscellaneous
Je nach Wunsch bzw. Notwendigkeit wird die Veranstaltung auf Deutsch oder Englisch abgehalten.