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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Новая страница: «Категория:Лекционные курсы кафедры МК Обязательный курс для студентов группы 521. Курс…»)
 
 
(не показаны 35 промежуточные версии 1 участника)
Строка 3: Строка 3:
 
Обязательный курс для студентов группы 521. Курс читает [[Подымов Владислав Васильевич|В. В. Подымов]].
 
Обязательный курс для студентов группы 521. Курс читает [[Подымов Владислав Васильевич|В. В. Подымов]].
  
−
Актуальность информации: весенний семестр 2022/2023 учебного года.
+
Актуальность информации: весенний семестр 2024/2025 учебного года.
  
−
= Слайды лекций =
+
= Слайды =
  
−
[[Media: DAS_VP_01.pdf| Блок 1.]] О чём этот курс. Литература.
+
== Лекции ==
  
−
[[Media: DAS_VP_02.pdf| Блок 2.]] Вступление: несколько слов о распределённых системах, проблемы организации их вычислений, особенности распределённых алгоритмов.
+
[[Media: DA_VP_01.pdf| Блок 1.]] О чём этот курс. Литература.
  
−
[[Media: DAS_VP_03.pdf| Блок 3.]] Модель распределённой системы: система переходов системы, система переходов узла, распределённый алгоритм, асинхронный и синхронный обмен сообщениями.
+
[[Media: DA_VP_02.pdf| Блок 2.]] Вступление: несколько слов о распределённых системах, проблемы организации их вычислений, особенности распределённых алгоритмов.
  
−
[[Media: DAS_VP_04.pdf| Блок 4.]] Справедливые вычисления.
+
[[Media: DA_VP_03.pdf| Блок 3.]] Иллюстрация трудности разработки распределённых алгоритмов: начало.
  
−
[[Media: DAS_VP_05.pdf| Блок 5.]] Иллюстрация трудности разработки распределённых алгоритмов
+
[[Media: DA_VP_04.pdf| Блок 4.]] Системы переходов.
  
−
[[Media: DAS_VP_06.pdf| Блок 6.]] Причинно-следственный порядок событий.
+
[[Media: DA_VP_05.pdf| Блок 5.]] Справедливые вычисления систем.
  
−
[[Media: DAS_VP_07.pdf| Блок 7.]] Логические часы.
+
[[Media: DA_VP_06.pdf| Блок 6.]] Основные соглашения о псевдокоде.
  
−
[[Media: DAS_VP_08.pdf| Блок 8.]] Дополнительные допущения. Сложность.
+
[[Media: DA_VP_07.pdf| Блок 7.]] Адресованные сообщения.
  
−
[[Media: DAS_VP_09.pdf| Блок 9.]] Симметричный протокол раздвижного окна.
+
[[Media: DA_VP_08.pdf| Блок 8.]] Симметричный протокол раздвижного окна.
  
−
[[Media: DAS_VP_10.pdf| Блок 10.]] Как обосновывать корректность распределённых алгоритмов. Свойства безопасности и живости.
+
[[Media: DA_VP_09.pdf| Блок 9.]] Как обосновывать корректность распределённых алгоритмов. Свойства безопасности и живости. Свойства корректности симметричного протокола раздвижного окна.
  
−
[[Media: DAS_VP_11.pdf| Блок 11.]] Корректность симметричного протокола раздвижного окна.
+
[[Media: DA_VP_10.pdf| Блок 10.]] Безопасность симметричного протокола раздвижного окна.
  
−
[[Media: DAS_VP_12.pdf| Блок 12.]] Особенности реализации симметричного протокола раздвижного окна.
+
[[Media: DA_VP_11.pdf| Блок 11.]] Живость симметричного протокола раздвижного окна.
  
−
[[Media: DAS_VP_13.pdf| Блок 13.]] Коммуникационный протокол с таймерами.
+
[[Media: DA_VP_12.pdf| Блок 12.]] Особенности реализации симметричного протокола раздвижного окна. Протокол альтернирующих битов.
  
−
[[Media: DAS_VP_14.pdf| Блок 14.]] Корректность протокола с таймерами.
+
[[Media: DA_VP_13.pdf| Блок 13.]] Напоминание о графах.
  
−
[[Media: DAS_VP_15.pdf| Блок 15.]] Задача маршрутизации.
+
[[Media: DA_VP_14.pdf| Блок 14.]] Типовые допущения и ограничения.
  
−
[[Media: DAS_VP_16.pdf| Блок 16.]] Основные допущения о весах в задаче маршрутизации. Маршрутизация и свойства графов.
+
[[Media: DA_VP_15.pdf| Блок 15.]] Коммуникационная и битовая сложности.
  
−
[[Media: DAS_VP_17.pdf| Блок 17.]] Построение оптимальных путей для всех пар вершин. Алгоритм Флойда-Уоршелла.
+
[[Media: DA_VP_16.pdf| Блок 16.]] Задача маршрутизации.
  
−
[[Media: DAS_VP_18.pdf| Блок 18.]] Алгоритм маршрутизации Туэга.
+
[[Media: DA_VP_17.pdf| Блок 17.]] Основные допущения в задаче маршрутизации. Маршрутизация и свойства графов.
  
−
[[Media: DAS_VP_19.pdf| Блок 19.]] Алгоритм маршрутизации Мерлина-Сигалла.
+
[[Media: DA_VP_18.pdf| Блок 18.]] Алгоритм Флойда-Уоршелла.
  
−
[[Media: DAS_VP_20.pdf| Блок 20.]] Алгоритм маршрутизации Чанди-Мисры.
+
[[Media: DA_VP_19.pdf| Блок 19.]] Алгоритм Туэга
  
−
[[Media: DAS_VP_21.pdf| Блок 21.]] Волновые алгоритмы: основные определения и свойства.
+
[[Media: DA_VP_20.pdf| Блок 20.]] Алгоритм Чанди-Мисры.
  
−
[[Media: DAS_VP_22.pdf| Блок 22.]] Применение волновых алгоритмов: PIF, SYN, INF.
+
[[Media: DA_VP_21.pdf| Блок 21.]] Диаграммы событий. Причинно-следственный порядок событий.
  
−
[[Media: DAS_VP_23.pdf| Блок 23.]] Примеры волновых алгоритмов: кольцевой алгоритм, древесный алгоритм, алгоритм эха.
+
[[Media: DA_VP_22.pdf| Блок 22.]] Логические часы.
  
−
[[Media: DAS_VP_24.pdf| Блок 24.]] Примеры волновых алгоритмов: фазовый алгоритм.
+
[[Media: DA_VP_23.pdf| Блок 23.]] Сложность распределённого алгоритма по времени.
  
−
[[Media: DAS_VP_25.pdf| Блок 25.]] Примеры волновых алгоритмов: алгоритм Финна.
+
[[Media: DA_VP_24.pdf| Блок 24.]] Волновые алгоритмы: основные определения и свойства.
  
−
[[Media: DAS_VP_26.pdf| Блок 26.]] Распределённые алгоритмы обхода. Алгоритм Тарри. Классический распределённый обход в глубину.
+
[[Media: DA_VP_25.pdf| Блок 25.]] Кольцевой волновой алгоритм.
  
−
[[Media: DAS_VP_27.pdf| Блок 27.]] Распределённый обход в глубину: алгоритм Авербаха.
+
[[Media: DA_VP_26.pdf| Блок 26.]] Древесный волновой алгоритм.
  
−
[[Media: DAS_VP_28.pdf| Блок 28.]] Алгоритмы избрания лидера: основные определения и допущения, волновое избрание лидера.
+
[[Media: DA_VP_27.pdf| Блок 27.]] Алгоритм эха.
  
−
[[Media: DAS_VP_29.pdf| Блок 29.]] Избрание лидера в дереве.
+
[[Media: DA_VP_28.pdf| Блок 28.]] Распределённые алгоритмы обхода.
  
−
[[Media: DAS_VP_30.pdf| Блок 30.]] Избрание лидера в кольце: алгоритм Ле-Ланна, алгоритм Ченя-Робертса.
+
[[Media: DA_VP_29.pdf| Блок 29.]] Алгоритм Тарри.
  
−
[[Media: DAS_VP_31.pdf| Блок 31.]] Избрание лидера: эффект угасания.
+
[[Media: DA_VP_30.pdf| Блок 30.]] Классический обход в глубину.
  
−
[[Media: DAS_VP_32.pdf| Блок 32.]] Избрание лидера: нижние оценки.
+
[[Media: DA_VP_31.pdf| Блок 31.]] Алгоритм Авербаха.
  
−
[[Media: DAS_VP_33.pdf| Блок 33.]] Избрание лидера: алгоритм Галлагера-Хамблета-Спиры (GHS).
+
''Слайды будут появляться по мере чтения лекций.''
  
−
[[Media: DAS_VP_34.pdf| Блок 34.]] Задача сохранения снимка сети.
+
=== Прошлогодние ===
  
−
[[Media: DAS_VP_35.pdf| Блок 35.]] Сохранение снимка сети: алгоритм Чанди-Лэмпорта.
+
[[Media: DA_VP_32.pdf| Блок 32.]] Задача избрания лидера: основные определения и допущения, избрание лидера INF-алгоритмом.
  
−
[[Media: DAS_VP_36.pdf| Блок 36.]] Сохранение снимка сети: алгоритм Лаи-Янга.
+
[[Media: DA_VP_33.pdf| Блок 33.]] Задача избрания лидера: эффект угасания.
  
−
[[Media: DAS_VP_37.pdf| Блок 37.]] Задача обнаружения завершения вычислений.
+
[[Media: DA_VP_34.pdf| Блок 34.]] Избрание лидера в дереве.
  
−
[[Media: DAS_VP_38.pdf| Блок 38.]] Обнаружение завершения вычислений: алгоритм Дейкстры-Шолтена.
+
[[Media: DA_VP_35.pdf| Блок 35.]] Избрание лидера в кольце: алгоритм Ле-Ланна, алгоритм Ченя-Робертса.
  
−
[[Media: DAS_VP_39.pdf| Блок 39.]] Обнаружение завершения вычислений: алгоритм Шави-Франчеза.
+
[[Media: DA_VP_36.pdf| Блок 36.]] Задача избрания лидера: нижние оценки.
  
−
[[Media: DAS_VP_40.pdf| Блок 40.]] Обнаружение завершения вычислений: алгоритм возвращения кредита.
+
[[Media: DA_VP_37.pdf| Блок 37.]] Избрание лидера и построение остовного дерева: алгоритм Галлагера-Хамблета-Спиры (GHS).
  
−
[[Media: DAS_VP_41.pdf| Блок 41.]] Отказоустойчивые алгоритмы. Модели неисправностей. Задачи принятия решения.
+
[[Media: DA_VP_38.pdf| Блок 38.]] Задача сохранения снимка сети.
  
−
[[Media: DAS_VP_42.pdf| Блок 42.]] Задача консенсуса.
+
[[Media: DA_VP_39.pdf| Блок 39.]] Алгоритм Чанди-Лэмпорта.
  
−
[[Media: DAS_VP_43.pdf| Блок 43.]] Консенсус: Паксос.
+
[[Media: DA_VP_40.pdf| Блок 40.]] Алгоритм Лаи-Янга.
  
−
''Слайды будут появляться по мере проведения занятий''
+
[[Media: DA_VP_41.pdf| Блок 41.]] Отказоустойчивые алгоритмы. Модели неисправностей. Задачи приниятия решения.
  
−
== Прошлогодние слайды ==
+
[[Media: DA_VP_42.pdf| Блок 42.]] Задача консенсуса.
  
−
[[Media: Lecture-DA-1.pdf| Lecture 1]].
+
[[Media: DA_VP_43.pdf| Блок 43.]] Паксос.
−
[[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: DA_VP_S01.pdf| Семинар 1.]] Псевдокод, системы переходов и справедливость на примере передачи данных с обеспечением надёжности.
−
[[Media: Lecture-DA-6.pdf| Lecture 6]].
+
 
−
[[Media: Lecture-DA-7.pdf| Lecture 7]].
+
[[Media: DA_VP_S02.pdf| Семинар 2.]] Свойства безопасности и живости.
−
[[Media: Lecture-DA-8.pdf| Lecture 8]].
+
 
−
[[Media: Lecture-DA-9.pdf| Lecture 9]].
+
[[Media: DA_VP_S04.pdf| Семинар 4.]] Вычисление таблиц маршрутизации. Коммуникационная и битовая сложности.
−
[[Media: Lecture-DA-10.pdf| Lecture 10]].
+
 
−
[[Media: Lecture-DA-11.pdf| Lecture 11]].
+
[[Media: DA_VP_S05.pdf| Семинар 5.]] Алгоритмы маршрутизации.
−
[[Media: Lecture-DA-12.pdf| Lecture 12]].
+
 
 +
[[Media: DA_VP_S06.pdf| Семинар 6.]] Сложность по времени.
 +
 
 +
[[Media: DA_VP_S07.pdf| Семинар 7.]] Приложения волновых алгоритмов.
 +
 
 +
''Слайды будут появляться по мере проведения занятий.''
  
 
= Литература =
 
= Литература =

Текущая версия на 19:23, 28 марта 2025


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

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

Слайды

Лекции

Блок 1. О чём этот курс. Литература.

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

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

Блок 4. Системы переходов.

Блок 5. Справедливые вычисления систем.

Блок 6. Основные соглашения о псевдокоде.

Блок 7. Адресованные сообщения.

Блок 8. Симметричный протокол раздвижного окна.

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

Блок 10. Безопасность симметричного протокола раздвижного окна.

Блок 11. Живость симметричного протокола раздвижного окна.

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

Блок 13. Напоминание о графах.

Блок 14. Типовые допущения и ограничения.

Блок 15. Коммуникационная и битовая сложности.

Блок 16. Задача маршрутизации.

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

Блок 18. Алгоритм Флойда-Уоршелла.

Блок 19. Алгоритм Туэга

Блок 20. Алгоритм Чанди-Мисры.

Блок 21. Диаграммы событий. Причинно-следственный порядок событий.

Блок 22. Логические часы.

Блок 23. Сложность распределённого алгоритма по времени.

Блок 24. Волновые алгоритмы: основные определения и свойства.

Блок 25. Кольцевой волновой алгоритм.

Блок 26. Древесный волновой алгоритм.

Блок 27. Алгоритм эха.

Блок 28. Распределённые алгоритмы обхода.

Блок 29. Алгоритм Тарри.

Блок 30. Классический обход в глубину.

Блок 31. Алгоритм Авербаха.

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

Прошлогодние

Блок 32. Задача избрания лидера: основные определения и допущения, избрание лидера INF-алгоритмом.

Блок 33. Задача избрания лидера: эффект угасания.

Блок 34. Избрание лидера в дереве.

Блок 35. Избрание лидера в кольце: алгоритм Ле-Ланна, алгоритм Ченя-Робертса.

Блок 36. Задача избрания лидера: нижние оценки.

Блок 37. Избрание лидера и построение остовного дерева: алгоритм Галлагера-Хамблета-Спиры (GHS).

Блок 38. Задача сохранения снимка сети.

Блок 39. Алгоритм Чанди-Лэмпорта.

Блок 40. Алгоритм Лаи-Янга.

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

Блок 42. Задача консенсуса.

Блок 43. Паксос.

Семинары

Семинар 1. Псевдокод, системы переходов и справедливость на примере передачи данных с обеспечением надёжности.

Семинар 2. Свойства безопасности и живости.

Семинар 4. Вычисление таблиц маршрутизации. Коммуникационная и битовая сложности.

Семинар 5. Алгоритмы маршрутизации.

Семинар 6. Сложность по времени.

Семинар 7. Приложения волновых алгоритмов.

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

Литература

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