Diese theoretische Grundlagen-LVA im Magisterstudium bietet eine Einführung in verteilte Algorithmen, insbesondere ihre formal-mathematische Analyse. Neben der generellen Entwicklung formal-mathematischen Fähigkeiten soll die LVA es ihren Absolventen erlauben, * 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, * Beweise für neue Lower-Bounds und Impossibility-Resultate zu finden.

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, atomic broadcasting; Beweistechniken: Impossibility proofs, lower bounds, simulation, indistinguishability, bivalence.

Bitte erst nach bestandenem 1.Quiz unter http://www.ecs.tuwien.ac.at/anmeldung/anmeldung.php und im TUWIS (LVA-Forum & News) anmelden!

Lösung von Übungsbeispielen + Schriftliche Tests

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

Vertrautheit mit der Analyse von sequentiellen Algorithmen und elementarer diskreter Mathematik. Hintergrundwissen über verteilte Systeme und fehlertolerante Systeme ist hilfreich, aber nicht unbedingt erforderlich.