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

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

Текущая версия на 14:00, 16 февраля 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. Алгоритмы маршрутизации.

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

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

Литература

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