Просмотр исходного текста страницы Распределенные алгоритмы и системы

[[Категория:Лекционные курсы кафедры МК]]

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

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

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

[[Media: DAS_VP_01.pdf| Блок 1.]] О чём этот курс. Литература.

[[Media: DAS_VP_02.pdf| Блок 2.]] Вступление: несколько слов о распределённых системах, проблемы организации их вычислений, особенности распределённых алгоритмов.

[[Media: DAS_VP_03.pdf| Блок 3.]] Модель распределённой системы: система переходов системы, система переходов узла, распределённый алгоритм, асинхронный и синхронный обмен сообщениями.

[[Media: DAS_VP_04.pdf| Блок 4.]] Справедливые вычисления.

[[Media: DAS_VP_05.pdf| Блок 5.]] Иллюстрация трудности разработки распределённых алгоритмов

[[Media: DAS_VP_06.pdf| Блок 6.]] Причинно-следственный порядок событий.

[[Media: DAS_VP_07.pdf| Блок 7.]] Логические часы.

[[Media: DAS_VP_08.pdf| Блок 8.]] Дополнительные допущения. Сложность.

[[Media: DAS_VP_09.pdf| Блок 9.]] Симметричный протокол раздвижного окна.

[[Media: DAS_VP_10.pdf| Блок 10.]] Как обосновывать корректность распределённых алгоритмов. Свойства безопасности и живости.

[[Media: DAS_VP_11.pdf| Блок 11.]] Корректность симметричного протокола раздвижного окна.

[[Media: DAS_VP_12.pdf| Блок 12.]] Особенности реализации симметричного протокола раздвижного окна.

[[Media: DAS_VP_13.pdf| Блок 13.]] Коммуникационный протокол с таймерами.

[[Media: DAS_VP_14.pdf| Блок 14.]] Корректность протокола с таймерами.

[[Media: DAS_VP_15.pdf| Блок 15.]] Задача маршрутизации.

[[Media: DAS_VP_16.pdf| Блок 16.]] Основные допущения о весах в задаче маршрутизации. Маршрутизация и свойства графов.

[[Media: DAS_VP_17.pdf| Блок 17.]] Построение оптимальных путей для всех пар вершин. Алгоритм Флойда-Уоршелла.

[[Media: DAS_VP_18.pdf| Блок 18.]] Алгоритм маршрутизации Туэга.

[[Media: DAS_VP_19.pdf| Блок 19.]] Алгоритм маршрутизации Мерлина-Сигалла.

[[Media: DAS_VP_20.pdf| Блок 20.]] Алгоритм маршрутизации Чанди-Мисры.

[[Media: DAS_VP_21.pdf| Блок 21.]] Волновые алгоритмы: основные определения и свойства.

[[Media: DAS_VP_22.pdf| Блок 22.]] Применение волновых алгоритмов: PIF, SYN, INF.

[[Media: DAS_VP_23.pdf| Блок 23.]] Примеры волновых алгоритмов: кольцевой алгоритм, древесный алгоритм, алгоритм эха.

[[Media: DAS_VP_24.pdf| Блок 24.]] Примеры волновых алгоритмов: фазовый алгоритм.

[[Media: DAS_VP_25.pdf| Блок 25.]] Примеры волновых алгоритмов: алгоритм Финна.

[[Media: DAS_VP_26.pdf| Блок 26.]] Распределённые алгоритмы обхода. Алгоритм Тарри. Классический распределённый обход в глубину.

[[Media: DAS_VP_27.pdf| Блок 27.]] Распределённый обход в глубину: алгоритм Авербаха.

[[Media: DAS_VP_28.pdf| Блок 28.]] Алгоритмы избрания лидера: основные определения и допущения, волновое избрание лидера.

[[Media: DAS_VP_29.pdf| Блок 29.]] Избрание лидера в дереве.

[[Media: DAS_VP_30.pdf| Блок 30.]] Избрание лидера в кольце: алгоритм Ле-Ланна, алгоритм Ченя-Робертса.

[[Media: DAS_VP_31.pdf| Блок 31.]] Избрание лидера: эффект угасания.

[[Media: DAS_VP_32.pdf| Блок 32.]] Избрание лидера: нижние оценки.

[[Media: DAS_VP_33.pdf| Блок 33.]] Избрание лидера: алгоритм Галлагера-Хамблета-Спиры (GHS).

[[Media: DAS_VP_34.pdf| Блок 34.]] Задача сохранения снимка сети.

[[Media: DAS_VP_35.pdf| Блок 35.]] Сохранение снимка сети: алгоритм Чанди-Лэмпорта.

[[Media: DAS_VP_36.pdf| Блок 36.]] Сохранение снимка сети: алгоритм Лаи-Янга.

[[Media: DAS_VP_37.pdf| Блок 37.]] Задача обнаружения завершения вычислений.

[[Media: DAS_VP_38.pdf| Блок 38.]] Обнаружение завершения вычислений: алгоритм Дейкстры-Шолтена.

[[Media: DAS_VP_39.pdf| Блок 39.]] Обнаружение завершения вычислений: алгоритм Шави-Франчеза.

[[Media: DAS_VP_40.pdf| Блок 40.]] Обнаружение завершения вычислений: алгоритм возвращения кредита.

[[Media: DAS_VP_41.pdf| Блок 41.]] Отказоустойчивые алгоритмы. Модели неисправностей. Задачи принятия решения.

[[Media: DAS_VP_42.pdf| Блок 42.]] Задача консенсуса.

[[Media: DAS_VP_43.pdf| Блок 43.]] Консенсус: Паксос.

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

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

[[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]].

= Литература =

#G. Tel. Introduction to Distributed Algorithms. Cambridge University Press. 2000. (русск. пер. Ж. Тель. Введение в распределенные алгоритмы, изд-во МЦНМО, 2009 г., 616 с.)
#W. Fokkink. Distributed Algorithms: Intuitive Approach. The MIT Press. 2013. (русск. пер. У. Фоккинк. Распределенные алгоритмв: интуитивный подход., изд-во Питер, 2017 г., 231 с.)
#N. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996, 906 pp.