Распределенные алгоритмы и системы — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
Строка 1: Строка 1:
−
Basic Master Course (group 521).  
+
Обязательный курс для студентов группы 521. Курс читает [[Подымов Владислав Васильевич|В. В. Подымов]].
  
−
Lecturer [[Vladimir Zakharov|V. A. Zakharov]].
+
Актуальность информации: весенний семестр 2022/2023 учебного года.
  
−
Lectures — 48 h., Homework — 16 h.
+
= Слайды лекций =
  
−
<h4>'''[[Media: Tasks_DisAlg.pdf| EXAMINATION TASKS.]]'''</h4>
+
''Слайды будут появляться по мере проведения занятий''
  
−
<!--
+
== Прошлогодние слайды ==
−
<h4>'''[[Media: G-521-2017.pdf| ТЕКУЩАЯ УСПЕВАЕМОСТЬ.]]'''</h4>
+
  
−
<h4>'''[[Media: G-521-2017.pdf| НАЧАЛО ЭКЗАМЕНА - 10.00]]'''</h4>
+
[[Media: Lecture-DA-1.pdf| Lecture 1]].
−
-->
+
[[Media: Lecture-DA-2.pdf| Lecture 2]].
 +
[[Media: Lecture-DA-3.pdf| Lecture 3]].
 +
[[Media: Lecture-DA-4.pdf| Lecture 4]].
 +
[[Media: Lecture-DA-5.pdf| Lecture 5]].
 +
[[Media: Lecture-DA-6.pdf| Lecture 6]].
 +
[[Media: Lecture-DA-7.pdf| Lecture 7]].
 +
[[Media: Lecture-DA-8.pdf| Lecture 8]].
 +
[[Media: Lecture-DA-9.pdf| Lecture 9]].
 +
[[Media: Lecture-DA-10.pdf| Lecture 10]].
 +
[[Media: Lecture-DA-11.pdf| Lecture 11]].
 +
[[Media: Lecture-DA-12.pdf| Lecture 12]].
  
−
== Program of the course ==
+
= Literature =
−
 
+
−
<h4>Part 1. Formal Models.</h4>
+
−
 
+
−
#Distributed systems and their generic features. Distributed systems architecture. ISO Open System Interaction standard. Algorithmic problems of distributed computing systems. Specific features of distributed algorithms. '''[[Media: Lecture-DA-1.pdf| Lecture 1.]]'''
+
−
#Formal models of distributed systems. Transition systems. Synchronous and asynchronous message passing. Fairness properties. Dependent and independent events. Causal order of events. Equivalence of execution. Distributed computations. Logical clocks. '''[[Media: Lecture-DA-2.pdf| Lecture 2.]]'''
+
−
#:
+
−
#:<h4>Part 2. Communication Protocols.</h4>
+
−
#:
+
−
#Communication Protocols. Errors in message transmission. Symmetric sliding window protocol: protocol design. Mathematical techniques for proving correctness of distributed algorithms. Correctness of sliding window protocol. Implementation of sliding window protocol. Alternating Bit Protocol. '''[[Media: Lecture-DA-3.pdf| Lecture 3.]]'''
+
−
#A timer-based communication protocol. Protocol design. Correctness of timer-based protocol. Implementation of timer-based protocol. '''[[Media: Lecture-DA-4.pdf| Lecture 4.]]'''
+
−
#Routing problem. Destination-based routing. The all-pairs shortest-path problem. Floyd--Warshall algorithm. Toueg's shortest-path algorithm. Merlin--Segall algorithm. Chandy--Misra algorithm. '''[[Media: Lecture-DA-5.pdf| Lecture 5.]]'''
+
−
#:
+
−
#:<h4>Part 3. Wave and Election Algorithms.</h4>
+
−
#:
+
−
#Wave algorithms: definition, basic properties, applications. The Ring algorithm. The Tree algorithm. The Echo algorithm. '''[[Media: Lecture-DA-6.pdf| Lecture 6.]]'''
+
−
#The Phase algorithm. Phinn's algorithm. Traversal algorithms. Depth-first-search traversal. Awerbuch's and Cidon's algorithms. '''[[Media: Lecture-DA-7.pdf| Lecture 7.]]'''
+
−
#Leader Election Problem. Leader election in rings: Le Lann Algorithm. Cheng-Roberts Algorithm. Paterson/Dolev-Clave-Rode Algorithm. Extinguish effect. '''[[Media: Lecture-DA-8.pdf| Lecture 8.]]'''
+
−
#Leader election in arbitrary networks. Lower bounds. Gallager-Humblet-Spira Algorithm (GHS). Corach-Katten-Moran Algorithm. '''[[Media: Lecture-DA-9.pdf| Lecture 9.]]'''
+
−
#:
+
−
#:<h4>Part 4. Termination and Deadlock Detection.</h4>
+
−
#:
+
−
#Termination detection problem. The Dijkstra-Scholten Algorithm. The Shavit-Francez Algorithm. The Safra's Algorithm. The Credit-Recovery Algorithm. The Rana's Algorithm. '''[[Media: Lecture-DA-10.pdf| Lecture 10.]]'''
+
−
#Snapshot problem. Chandy--Lamport algorithm. Lai--Yang algorithm. Applications of snapshot algorithms. Deadlock detection. '''[[Media: Lecture-DA-11.pdf| Lecture 11.]]'''
+
−
#:
+
−
#:<h4>Part 4. Fault Tolerance of Distributed Algorithms.</h4>
+
−
#:
+
−
# Fault Tolerant Algorithms. Failure Models. Decision Problems. Consensus Problem. Impossibility of Perfect Consensus. On the possibility of Consensus for some Distributed Systems. Consensus Problem for synchronous systems. '''[[Media: Lecture-DA-12.pdf| Lecture 12.]]'''
+
−
<!-- #Стабилизирующиеся алгоритмы. Пример Дейкстры. Общие принципы построения стабилизирующихся алгоритмов.-->
+
−
 
+
−
== Literature ==
+
  
 
#G. Tel. Introduction to Distributed Algorithms. Cambridge University Press. 2000. (русск. пер. Ж. Тель. Введение в распределенные алгоритмы, изд-во МЦНМО, 2009 г., 616 с.)
 
#G. Tel. Introduction to Distributed Algorithms. Cambridge University Press. 2000. (русск. пер. Ж. Тель. Введение в распределенные алгоритмы, изд-во МЦНМО, 2009 г., 616 с.)
 
#W. Fokkink. Distributed Algorithms: Intuitive Approach. The MIT Press. 2013. (русск. пер. У. Фоккинк. Распределенные алгоритмв: интуитивный подход., изд-во Питер, 2017 г., 231 с.)
 
#W. Fokkink. Distributed Algorithms: Intuitive Approach. The MIT Press. 2013. (русск. пер. У. Фоккинк. Распределенные алгоритмв: интуитивный подход., изд-во Питер, 2017 г., 231 с.)
 
#N. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996, 906 pp.
 
#N. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996, 906 pp.

Версия 13:09, 7 февраля 2023

Обязательный курс для студентов группы 521. Курс читает В. В. Подымов.

Актуальность информации: весенний семестр 2022/2023 учебного года.

Слайды лекций

Слайды будут появляться по мере проведения занятий

Прошлогодние слайды

Lecture 1. Lecture 2. Lecture 3. Lecture 4. Lecture 5. Lecture 6. Lecture 7. Lecture 8. Lecture 9. Lecture 10. Lecture 11. Lecture 12.

Literature

  1. G. Tel. Introduction to Distributed Algorithms. Cambridge University Press. 2000. (русск. пер. Ж. Тель. Введение в распределенные алгоритмы, изд-во МЦНМО, 2009 г., 616 с.)
  2. W. Fokkink. Distributed Algorithms: Intuitive Approach. The MIT Press. 2013. (русск. пер. У. Фоккинк. Распределенные алгоритмв: интуитивный подход., изд-во Питер, 2017 г., 231 с.)
  3. N. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996, 906 pp.
Источник — «https://mk.cs.msu.ru/index.php?title=Распределенные_алгоритмы_и_системы&oldid=9889»