Версия 08:00, 12 февраля 2024

Обязательный курс для студентов группы 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. Консенсус: Паксос.

Литература

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.