Версия 11:45, 2 мая 2023

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

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

Слайды лекций

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

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

Блок 3. Модель распределённой системы: система переходов системы, система переходов узла, распределённый алгоритм, асинхронный и синхронный обмен сообщениями.

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

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

Блок 6. Причинно-следственный порядок событий.

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

Блок 8. Дополнительные допущения. Сложность.

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

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

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

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

Блок 13. Коммуникационный протокол с таймерами.

Блок 14. Корректность протокола с таймерами.

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

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

Блок 17. Построение оптимальных путей для всех пар вершин. Алгоритм Флойда-Уоршелла.

Блок 18. Алгоритм маршрутизации Туэга.

Блок 19. Алгоритм маршрутизации Мерлина-Сигалла.

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

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

Блок 22. Применение волновых алгоритмов: PIF, SYN, INF.

Блок 23. Примеры волновых алгоритмов: кольцевой алгоритм, древесный алгоритм, алгоритм эха.

Блок 24. Примеры волновых алгоритмов: фазовый алгоритм.

Блок 25. Примеры волновых алгоритмов: алгоритм Финна.

Блок 26. Распределённые алгоритмы обхода. Алгоритм Тарри. Классический распределённый обход в глубину.

Блок 27. Распределённый обход в глубину: алгоритм Авербаха.

Блок 28. Алгоритмы избрания лидера: основные определения и допущения, волновое избрание лидера.

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

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

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

Блок 32. Избрание лидера: нижние оценки.

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

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

Блок 35. Сохранение снимка сети: алгоритм Чанди-Лэмпорта.

Блок 36. Сохранение снимка сети: алгоритм Лаи-Янга.

Блок 37. Задача обнаружения завершения вычислений.

Блок 38. Обнаружение завершения вычислений: алгоритм Дейкстры-Шолтена.

Блок 39. Обнаружение завершения вычислений: алгоритм Шави-Франчеза.

Блок 40. Обнаружение завершения вычислений: алгоритм возвращения кредита.

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

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

Блок 43. Консенсус: Паксос.

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

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

Lecture 1. Lecture 2. Lecture 3. Lecture 4. Lecture 5. Lecture 6. Lecture 7. Lecture 8. Lecture 9. Lecture 10. Lecture 11. Lecture 12.

Литература

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.