Распределённые алгоритмы
Обязательный курс для студентов группы 521. Курс читает В. В. Подымов.
Актуальность информации: весенний семестр 2023/2024 учебного года.
Слайды лекций
Слайды будут появляться по мере чтения лекций.
Прошлогодние слайды
Блок 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. Консенсус: Паксос.
Литература
- 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.
