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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Программа)
(→‎Программа)
Строка 15: Строка 15:
 
== Программа ==
 
== Программа ==
  
−
<h4>Часть 1. Математические модели.</h4>
+
<h4>Part 1. Formal Models.</h4>
  
−
#Характерные особенности и примеры распределенных систем: компьютерные сети, локальные и глобальные сети, многопроцессорные компьютеры. Архитектура распределенных систем. Стандарт ISO Open System Interconnection. Алгоритмические проблемы организации вычислений распределенных систем. Особенности распределенных алгоритмов. '''[[Media: Lecture-DA-1.pdf| Лекция 1.]]'''
+
#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| Лекция 1.]]'''
−
#Математическая модель распределенных систем. Системы переходов. Синхронный и асинхронный обмен сообщениями. Зависимые и независимые события. Причинно-следственный порядок событий. Эквивалентность выполнений. Вычисления. Логические часы. Топологии распределенных систем. <!--'''[[Media: DistrAlg_2.pdf| Лекция 2.]]'''-->
+
#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: DistrAlg_2.pdf| Лекция 2.]]'''-->
 
#:
 
#:
−
#:<h4>Часть 2. Коммуникационные протоколы.</h4>
+
#:<h4>Part 2. Communication Protocols.</h4>
 
#:
 
#:
−
#Коммуникационные протоколы. Ошибки, возникающие при передаче сообщений. Задача надежного обмена сообщениями. Симметричные протокол раздвижного окна: устройство протокола и обоснование его корректности. Протокол альтернирующего бита. <!--'''[[Media: DistrAlg_3.pdf| Лекция 3.]]'''-->
+
#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: DistrAlg_3.pdf| Лекция 3.]]'''-->
−
#Коммуникационный протокол с таймером: устройство и обоснование корректности. <!--'''[[Media: DistrAlg_4.pdf| Лекция 4.]]'''-->
+
#A timer-based communication protocol. Protocol design. Correctness of timer-based protocol. Implementation of timer-based protocol. <!--'''[[Media: DistrAlg_4.pdf| Лекция 4.]]'''-->
−
#Задача маршрутизации. Алгоритмы построения кратчайших путей в графе. Алгоритм Флойда-Уоршалла. Алгоритм Туэга. Алгоритм Мерлина-Сигала. Алгоритм Чанди-Мизры. <!--'''[[Media: DistrAlg_5.pdf| Лекция 5.]]'''--> Алгоритм Netchange. Разнообразие алгоритмов маршрутизации. <!--'''[[Media: DistrAlg_6.pdf| Лекция 6.]]'''-->
+
#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: DistrAlg_5.pdf| Лекция 5.]]'''--> Алгоритм Netchange. Разнообразие алгоритмов маршрутизации. <!--'''[[Media: DistrAlg_6.pdf| Лекция 6.]]'''-->
 
#:
 
#:
 
#:<h4>Часть 3. Распределенные алгоритмы.</h4>
 
#:<h4>Часть 3. Распределенные алгоритмы.</h4>

Версия 14:43, 17 февраля 2020

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

Курс читает профессор В. А. Захаров.

Лекционная нагрузка — 48 ч., семинары — 16 ч.

ЗАДАЧИ К ЭКЗАМЕНУ.


Программа

Part 1. Formal Models.

  1. 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. Лекция 1.
  2. 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.

    Part 2. Communication Protocols.

  3. 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.
  4. A timer-based communication protocol. Protocol design. Correctness of timer-based protocol. Implementation of timer-based protocol.
  5. 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. Алгоритм Netchange. Разнообразие алгоритмов маршрутизации.

    Часть 3. Распределенные алгоритмы.

  6. Волновые алгоритмы: определение, основные свойства, область применения. Древесный алгоритм. Алгоритм эха. Фазовый алгоритм. Алгоритм Финна. Алгоритмы обхода. Распределенный обход в глубину. Алгоритмы обхода Авербаха и Сидон.
  7. Задача избрания лидера. Избрание лидера на кольцах: алгоритм Ченя-Робертса, оптимальный алгоритм Патерсона –Долева-Клейва-Роде. Избрание лидера в произвольных сетях: алгоритм Галладжера-Хамблета-Спиры, алгоритм Кораха-Каттена-Морана.
  8. Задача обнаружения завершения вычисления. Алгоритм Дейкстры-Шолтена. Алгоритм Шави-Франчеза. Алгоритм Сафры. Алгоритм возвращения кредитов. Алгоритм Раны.
  9. Задача сохранения моментального состояния. Алгоритм Чанди-Лампорта. Алгоритм Лаи-Янга. Применение алгоритмов обнаружения моментальной разметки и завершения вычислений для выявления блокировки вычислений.

    Часть 4. Вопросы надежности распределенных алгоритмов.

  10. Задача обеспечения отказоустойчивости распределенных систем. Невозможность построения робастных асинхронных систем. Синхронные робастные алгоритмы принятия решения. Использование криптографических примитивов для повышения отказоустойчивости.

Литература

  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=6841»