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

Материал из Кафедра математической кибернетики
Страница-перенаправление
Перейти к: навигация, поиск
м
(Перенаправление на Распределённые алгоритмы)
 
(не показана 1 промежуточная версия 1 участника)
Строка 1: Строка 1:
[[Категория:Лекционные курсы кафедры МК]]
+
#перенаправление [[Распределённые алгоритмы]]
 
+
Обязательный курс для студентов группы 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.
+

Текущая версия на 07:53, 12 февраля 2024