This theoretical graduate-level basic course provides an introduction to distributed algorithms and, in particular, their formal-mathematical analysis. Apart from developing formal-mathematical skills in general, it shall allow its attendees to: * become familiar with fundamental models, problems, algorithms, lower bound and impossibility results, and proof techniques in distributed computing, * be able to apply lower bounds and impossibility results learned to new situations where appropriate, * be able to design new distributed algorithms for new situations, using as building blocks the algorithms and techniques learned, * prove new lower bounds and impossibility results for new situations.

Basics: Execution runs, safety and liveness properties, causality and time; Models: Message passing vs. shared memory, synchronous vs. asynchronous, failure models; Algorithms: Leader election, mutual exclusion, clock synchronization, consensus, atomic broadcasting; Proof techniques: Impossibility proofs, lower bounds, simulation, indistinguishability, bivalence.

Please enroll via http://www.ecs.tuwien.ac.at/anmeldung/anmeldung.php and in TUWIS (LVA-Forum & News) only after passing the first quiz!

Homeworks + written 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

Familiarity with the analysis of sequential algorithms and elementary discrete mathematics is required. Some background in distributed systems and fault-tolerant systems is helpful but not absolutely necessary.