Распределенные алгоритмы

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.