DM821: Theory of Distributed Computing (5 ECTS)

STADS: 15007401

Level
Master's level course

Teaching period

Offered according to needs.

Teacher responsible
Email: faith@imada.sdu.dk

Timetable
Show entire timetable
Show personal time table for this course.

Comment:
Ubegrænset deltagerantal. 4.kvartal

Prerequisites:
None

Academic preconditions:
The contents of DM508 Algorithms and Complexity must be known.

Course introduction
The goal of this course is to introduce students to fundamental models and problems in distributed computing with an emphasis on synchronization and fault tolerance. Students will learn to write distributed algorithms, prove them correct, and analyze their complexity. They will also learn techniques to prove the impossibility of solving various distributed computing problems.

Expected learning outcome
- Express distributed algorithms precisely.
- Prove distributed algorithms correct.
- Analyze the complexity of distributed algorithms.
- Prove the impossibility of solving certain distributed problems.

Subject overview
Asynchronous shared memory and message passing models, mutual exclusion, consensus, Byzantine agreement, linearizability, wait-freedom, consensus number, snapshot objects, universality, approximate agreement, timestamps, randomized consensus, renaming, covering arguments, scenario arguments, valency arguments, and information theory lower bounds.

Literature

• Meddeles ved kursets start.: .

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:


Expected working hours
The teaching method is based on three phase model.

Forelæsninger: 21 timer
Eksaminatorietimer/opgaveregning: 14 timer
Educational activities

Language
This course is taught in Danish or English, depending on the lecturer.

Remarks
Evaluation of the course is based on participation in classes and giving a presentation. The presentation consists of choosing an interesting idea or result from the theory of distributed computing literature, understanding the topic, and giving a high quality 20 minute lecture to the class, motivating and describing the topic. The teacher will review a draft of each student's presentation to suggest ways to improve it. The presentation should be in English. Regarding participation, the students must attend at least 80% of all classes (lectures and tutorials combined) in order to pass.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.