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

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

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

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

= Слайды =

== Лекции ==

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

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

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

[[Media: DA_VP_04.pdf| Блок 4.]] Системы переходов.

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

[[Media: DA_VP_06.pdf| Блок 6.]] Основные соглашения о псевдокоде.

[[Media: DA_VP_07.pdf| Блок 7.]] Адресованные сообщения.

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

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

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

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

[[Media: DA_VP_12.pdf| Блок 12.]] Особенности реализации симметричного протокола раздвижного окна. Протокол альтернирующих битов.

[[Media: DA_VP_13.pdf| Блок 13.]] Напоминание о графах.

[[Media: DA_VP_14.pdf| Блок 14.]] Типовые допущения и ограничения.

[[Media: DA_VP_15.pdf| Блок 15.]] Коммуникационная и битовая сложности.

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

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

[[Media: DA_VP_18.pdf| Блок 18.]] Алгоритм Флойда-Уоршелла.

[[Media: DA_VP_19.pdf| Блок 19.]] Алгоритм Туэга

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

[[Media: DA_VP_21.pdf| Блок 21.]] Диаграммы событий. Причинно-следственный порядок событий.

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

[[Media: DA_VP_23.pdf| Блок 23.]] Сложность распределённого алгоритма по времени.

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

[[Media: DA_VP_25.pdf| Блок 25.]] Кольцевой волновой алгоритм.

[[Media: DA_VP_26.pdf| Блок 26.]] Древесный волновой алгоритм.

[[Media: DA_VP_27.pdf| Блок 27.]] Алгоритм эха.

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

== Семинары ==

[[Media: DA_VP_S01.pdf| Семинар 1.]] Псевдокод, системы переходов и справедливость на примере передачи данных с обеспечением надёжности.

[[Media: DA_VP_S02.pdf| Семинар 2.]] Свойства безопасности и живости.

[[Media: DA_VP_S04.pdf| Семинар 4.]] Вычисление таблиц маршрутизации. Коммуникационная и битовая сложности.

[[Media: DA_VP_S05.pdf| Семинар 5.]] Алгоритмы маршрутизации.

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

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

[[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.]] Консенсус: Паксос.

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

#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.