182.073 Distributed Algorithms
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2011S, VU, 3.0h, 4.5EC

Properties

  • Semester hours: 3.0
  • Credits: 4.5
  • Type: VU Lecture and Exercise

Aim of course

Fault-tolerant distributed algorithms are at the heart of any distributed system for critical applications and implement low-level services like clock synchronization, group membership and consensus. Suitable algorithms must work as specified in the presence of the inherent uncertainty in network- or shared-memory coupled distributed systems, which is caused by varying/unknown communication delays and computing speeds and, in particular, subsystem failures. Due to combinatorial explosion, it is often impossible to verify the correct operation of such algorithms by means of model checking (or exhaustive testing). Correctness proofs based on formal-mathematical modelling are the only feasible alternative here. This theoretical graduate-level basic course provides an introduction to distributed algorithms and their formal-mathematical analysis. Apart from developing formal-mathematical skills in general, this course shall allow its attendees to: (1) become familiar with fundamental models, problems, algorithms, lower bound and impossibility results, and proof techniques in distributed computing, (2) be able to apply lower bounds and impossibility results learned to new situations where appropriate, (3) be able to design new distributed algorithms for new situations, using the algorithms and techniques learned as building blocks, and (4) find new lower bounds and impossibility results.

The course is organized in the "anglo-american style", which is based on continuous engagement during the whole semester: Several quizzes and homework assignments ensure (1) that the topics taught in the lecture are efficiently acquired, and (2) that the individual formal-mathematical problem-solving skills are trained.

Subject of course

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, distributed snapshots; Proof techniques: Impossibility proofs, lower bounds, simulation, indistinguishability, bivalence.

Additional information

All who want to participate in the next course: Please subscribe to the TISS LVA-Forum & News as soon as possible. [Enrolling (via myTI) is only allowed after having passed the admission criterion, however.]

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Thu08:15 - 10:0003.03.2011 - 30.06.2011EI 10 Fritz Paschke HS SCHMID
Fri08:15 - 11:0004.03.2011 - 30.06.2011EI 10 Fritz Paschke HS SCHMID
Distributed Algorithms - Single appointments
DayDateTimeLocationDescription
Thu03.03.201108:15 - 10:00EI 10 Fritz Paschke HS SCHMID
Fri04.03.201108:15 - 11:00EI 10 Fritz Paschke HS SCHMID
Thu10.03.201108:15 - 10:00EI 10 Fritz Paschke HS SCHMID
Fri11.03.201108:15 - 11:00EI 10 Fritz Paschke HS SCHMID
Thu17.03.201108:15 - 10:00EI 10 Fritz Paschke HS SCHMID
Fri18.03.201108:15 - 11:00EI 10 Fritz Paschke HS SCHMID
Thu24.03.201108:15 - 10:00EI 10 Fritz Paschke HS SCHMID
Fri25.03.201108:15 - 11:00EI 10 Fritz Paschke HS SCHMID
Thu31.03.201108:15 - 10:00EI 10 Fritz Paschke HS SCHMID
Fri01.04.201108:15 - 11:00EI 10 Fritz Paschke HS SCHMID
Thu07.04.201108:15 - 10:00EI 10 Fritz Paschke HS SCHMID
Fri08.04.201108:15 - 11:00EI 10 Fritz Paschke HS SCHMID
Thu14.04.201108:15 - 10:00EI 10 Fritz Paschke HS SCHMID
Fri15.04.201108:15 - 11:00EI 10 Fritz Paschke HS SCHMID
Thu21.04.201108:15 - 10:00EI 10 Fritz Paschke HS SCHMID
Fri22.04.201108:15 - 11:00EI 10 Fritz Paschke HS SCHMID
Thu28.04.201108:15 - 10:00EI 10 Fritz Paschke HS SCHMID
Fri29.04.201108:15 - 11:00EI 10 Fritz Paschke HS SCHMID
Thu05.05.201108:15 - 10:00EI 10 Fritz Paschke HS SCHMID
Fri06.05.201108:15 - 11:00EI 10 Fritz Paschke HS SCHMID

Examination modalities

Solution and presentation of homework assignments + written tests + written exam

Course registration

Registration modalities:

Ort: nach 1. Quiz (elektronisch in myTI)

Curricula

Literature

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

Previous knowledge

Familiarity with the analysis of sequential algorithms and elementary discrete mathematics; reasonable skills in devising mathematical proofs. Some background in distributed systems and fault-tolerant systems is helpful but not required.

Preceding courses

Miscellaneous

Language

German