City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Distributed Algorithms
Saint Petersburg / spring 2008, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

This course will consider algorithmic aspects of distributed systems. Distributed algorithms arise in a wide range of applications: telecommunications, distributed information processing, scientific computing, embedded computing, etc. The course will provide the basis for designing distributed systems and formally reasoning about their correctness. It will address issues related to what distributed systems can and cannot do (i.e., impossibility results) in certain system models. Emphasis will be given to fundamental distributed systems problems and how they relate to practical applications. The course will focus on three aspects of distributed computing: system models, fundamental problems in distributed computing, and application of distributed algorithms. System models include synchronous versus asynchronous systems, communication models, and failure models. The following fundamental problems will be surveyed: consensus, atomic broadcast, atomic commit and leader election. Algorithms and impossibility results in various models will be presented. If time allows, applications of distributed algorithms in the context of replication techniques will be also covered. Lectures:

  • Introduction to distributed systems and distributed models
  • The consensus problem
  • Fault-tolerant broadcasts
  • The atomic commitment problem

Prerequisites for the classes (courses, books): some knowledge about algorithms and discrete math (basic logic) is a must. It would be good if students had an introduction to distributed systems or distributed programming. Some general notions about an imperative programming language would be a plus.

Date and time Class|Name Venue|short Materials
26 April
Distributed system models, Lecture ПОМИ РАН slides
27 April
The consensus problem, Lecture ПОМИ РАН slides
03 May
Fault-tolerant broadcasts Part I: Definitions, Lecture ПОМИ РАН slides
04 May
Fault-tolerant broadcasts Part II: Algorithms, Lecture ПОМИ РАН slides