182.702 Distributed Algorithms
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2021S, VU, 4.0h, 6.0EC
TUWEL

Merkmale

  • Semesterwochenstunden: 4.0
  • ECTS: 6.0
  • Typ: VU Vorlesung mit Übung
  • Format der Abhaltung: Hybrid

Lernergebnisse

Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage...

  • Modelle, Probleme, Algorithmen, Lower-Bounds, Impossibility-Resultate und Korrektheitsbeweise im Bereich Distributed Computing zu verstehen,
  • existierende Lower-Bounds und Impossibility-Resultate in neuen Situationen anzuwenden,
  • auf Basis der erlernten Algorithmen und Techniken neue verteilte Algorithmen für spezielle Problemstellungen zu entwickeln und deren Korrektheit zu beweisen, und
  • neue Lower-Bounds und Impossibility-Resultate zu finden.

Inhalt der Lehrveranstaltung

Fehlertolerante verteilte Algorithmen sind das Herzstück jedes verteilten Computersystems für kritische Anwendungen und implementieren grundlegende Services wie Uhrensynchronisation, Group Membership und Consensus. Derartige Algorithmen müssen ihre Spezifikation trotz der inhärenten Unsicherheit erfüllen, die in netzwerk- oder shared-memory-gekoppelten verteilten Systemen unvermeidbar ist. Quellen dieser Unsicherheit sind variable/unbekannte Ausführungs- und Nachrichtenübertragungszeiten und, insbesondere, Fehler von Subsystemen. Die daraus resultierende kombinatorische Explosion macht es in vielen Fällen unmöglich, die korrekte Operation solcher Algorithmen durch Model Checking (oder gar erschöpfendes Testing) zu verifizieren. Korrektheitsbeweise basierend auf einer geeigneten formal-mathematischen Modellierung stellen hier die einzig taugliche Alternative dar.

Diese Master-level Basis-LVA bietet eine Einführung in verteilte Algorithmen und deren formal-mathematische Analyse und hat folgende konkreten Inhalte:

  • Grundlagen: Execution runs, safety and liveness properties, causality and time;
  • Modelle: Message passing vs. shared memory, synchronous vs. asynchronous, failure models;
  • Algorithmen: Leader election, mutual exclusion, clock synchronization, consensus, distributed snapshots;
  • Beweistechniken: Impossibility proofs, lower bounds, simulation, indistinguishability, bivalence.

Methoden

Die LVA wird im "angloamerikanischen Modus" abgehalten, der auf kontinuierlicher Beschäftigung mit den Inhalten während des gesamten Semesters basiert: Mehrere Quizzes, Studierendenpräsentationen und Homework-Assignments stellen sicher, dass (1) die in Vorlesung vermittelten Inhalte effizient erlernt und (2) die individuelle Problemlösungskompetenz im formal-mathematischen Bereich entwickelt werden. Die Homework-Assignments werden in Form von "Mini-Konferenzen" (LaTex Ausarbeitung, Reviewing, Lösungspräsentation) abgewickelt, wodurch (3) auch die entsprechenden wissenschaftlichen Soft-Skills "hands-on" trainiert werden.

Prüfungsmodus

Prüfungsimmanent

Weitere Informationen

Für die Teilnahme an der LVA ist zunächst die Anmeldung im entsprechenden TUWEL-Kurs erforderlich, in dem auch der konkrete Link für die on-line Teilnahme veröffentlicht wird. Detaillierte Instruktionen und notwendige Voraussetzungen dafür sind auf der Homepage zu finden.

ECTS-Breakdown (6 ECTS = 150 Stunden):

 33h             Lecture time
   1.5h          2 Quizzes
   8h             4 Studierenden-Präsentationen
 22h             Vorbereitungszeit für Quizzes und Studiernden-Präsentationen
 85.5h          Vorbereitungszeit für 4 Homework-Assignments  (jeweils 3-5 Exercises): First and Final Version (in LaTeX); Reviewing.

Vortragende Personen

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Do.08:00 - 10:0004.03.2021 - 24.06.2021EI 10 Fritz Paschke HS - ETIT Distributed Algorithms
Fr.08:00 - 10:0005.03.2021 - 25.06.2021EI 10 Fritz Paschke HS - ETIT Distributed Algorithms
Distributed Algorithms - Einzeltermine
TagDatumZeitOrtBeschreibung
Do.04.03.202108:00 - 10:00EI 10 Fritz Paschke HS - ETIT Distributed Algorithms
Fr.05.03.202108:00 - 10:00EI 10 Fritz Paschke HS - ETIT Distributed Algorithms
Do.11.03.202108:00 - 10:00EI 10 Fritz Paschke HS - ETIT Distributed Algorithms
Fr.12.03.202108:00 - 10:00EI 10 Fritz Paschke HS - ETIT Distributed Algorithms
Do.18.03.202108:00 - 10:00EI 10 Fritz Paschke HS - ETIT Distributed Algorithms
Fr.19.03.202108:00 - 10:00EI 10 Fritz Paschke HS - ETIT Distributed Algorithms
Do.25.03.202108:00 - 10:00EI 10 Fritz Paschke HS - ETIT Distributed Algorithms
Fr.26.03.202108:00 - 10:00EI 10 Fritz Paschke HS - ETIT Distributed Algorithms
Do.15.04.202108:00 - 10:00EI 10 Fritz Paschke HS - ETIT Distributed Algorithms
Fr.16.04.202108:00 - 10:00EI 10 Fritz Paschke HS - ETIT Distributed Algorithms
Do.22.04.202108:00 - 10:00EI 10 Fritz Paschke HS - ETIT Distributed Algorithms
Fr.23.04.202108:00 - 10:00EI 10 Fritz Paschke HS - ETIT Distributed Algorithms
Do.29.04.202108:00 - 10:00EI 10 Fritz Paschke HS - ETIT Distributed Algorithms
Fr.30.04.202108:00 - 10:00EI 10 Fritz Paschke HS - ETIT Distributed Algorithms
Do.06.05.202108:00 - 10:00EI 10 Fritz Paschke HS - ETIT Distributed Algorithms
Fr.07.05.202108:00 - 10:00EI 10 Fritz Paschke HS - ETIT Distributed Algorithms
Do.20.05.202108:00 - 10:00EI 10 Fritz Paschke HS - ETIT Distributed Algorithms
Fr.21.05.202108:00 - 10:00EI 10 Fritz Paschke HS - ETIT Distributed Algorithms
Do.27.05.202108:00 - 10:00EI 10 Fritz Paschke HS - ETIT Distributed Algorithms
Fr.28.05.202108:00 - 10:00EI 10 Fritz Paschke HS - ETIT Distributed Algorithms

Leistungsnachweis

Lösung von Übungsbeispielen + Reviewing (upload .pdf via myTI) + Quizzes (via ZOOM, mit Hochladen eines Scans (.pdf) der Lösung in TUWEL) + Studierenden-Präsentationen (via ZOOM). Erfordert ZOOM Basisausstattung, Scanner mit .pdf-Ausgabe für Upload in TUWEL sowie nach Möglichkeit Drucker für die Quiz-Angaben. Details siehe Webseite der LVA.

LVA-Anmeldung

Von Bis Abmeldung bis
25.02.2021 08:00 07.03.2021 23:59

Curricula

Literatur

Textbook: Hagit Attiya, Jennifer Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd ed.), John Wiley and Sons, 2004. ISBN 0-471-45324-2

Vorkenntnisse

Vertrautheit mit der Analyse von sequentiellen Algorithmen und elementarer diskreter Mathematik; ausreichende Fertigkeiten bei der Erstellung mathematischer Beweise. Hintergrundwissen über verteilte Systeme und fehlertolerante Systeme ist hilfreich, aber nicht notwendig. Vertrautheit mit den Grundlagen wissenschaftlichen Arbeitens (LaTeX, reviewing).

Vorausgehende Lehrveranstaltungen

Weitere Informationen

Sprache

Englisch