Распределённые алгоритмы
Обязательный курс для студентов группы 521. Курс читает В. В. Подымов.
Актуальность информации: весенний семестр 2025/2026 учебного года.
Содержание
Слайды
Лекции
Блок 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. Паксос.
Блок 44. Задача выявления конца вычислений.
Блок 45. Выявление конца вычислений: алгоритм Дейкстры-Шолтена.
Блок 46. Выявление конца вычислений: алгоритм Шави-Франчеза.
Блок 47. Выявление конца вычислений: алгоритм возвращения кредита.
Слайды будут появляться по мере чтения лекций.
Семинары
Материалы обновляются по мере проведения занятий
Прошлогодние
Семинар 1. Псевдокод, системы переходов и справедливость на примере передачи данных с обеспечением надёжности.
Семинар 2. Свойства безопасности и живости.
Семинар 4. Вычисление таблиц маршрутизации. Коммуникационная и битовая сложности.
Семинар 5. Алгоритмы маршрутизации.
Семинар 6. Сложность по времени.
Семинар 7. Приложения волновых алгоритмов.
Экзамен
Экзамен проводится письменно, длительность - 100 минут. Вариант экзамена содержит 5 задач такого же характера, как задачи домашних заданий в семестре.
Каждая задача оценивается по шкале от 0 до 100 баллов. В оценке задачи учитываются следующие характеристики решения:
- Полнота - учтены все детали, разобраны все случаи и т.п.
- Корректность - все утверждения в решении правильны.
- Строгость - решение написано грамотно, в том числе математически грамотно.
Средний балл по всем задачам преобразуется в оценку так: 80-100 - отлично, 60-79 - хорошо, 40-59 - удовлетворительно, менее 40 - неудовлетворительно.
Можно пользоваться лекциями, книгами, конспектами. Нельзя пользоваться никакими иными неодобренными источниками. Имейте в виду, что времени на решение задач даётся не очень много, поэтому использование материалов на экзамене не заменяет подготовку к нему.
Домашние задания
Желающие облегчить экзамен (в том числе избежать его - получить автомат) могут выполнять домашние задания во время семестра.
Каждому семинару отвечает своё домашнее задание. Оно оценивается по шкале от 0 до 100 баллов. В домашнем задании может быть несколько задач, баллы распределяются пропорционально трудности задач. В оценке каждой задачи учитываются те же характеристики, что и в оценке задач экзамена. Кроме того, выдаётся штраф за слишком долгое решение:
- Решение сдано до конца воскресенья, следующего за семинаром - штрафа нет.
- Каждая дополнительная неделя даёт штраф -6 баллов.
- После окончания семестра домашние задания не принимаются, за исключением явно оговорённых случаев.
Средний балл по всем домашним заданиям преобразуется в оценку автоматом так же, как на экзамене. Если не получена желаемая оценка автоматом, то баллы, набранные за домашние задания, особым образом конвертируются в частично или полностью зачтённые задачи экзамена. Каждое решённое домашнее задание принесёт пользу на экзамене независимо от того, получена ли желаемая оценка автоматом.
Литература
- 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.
