|
|
| Строка 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.
| + | |
