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

Версия 13:31, 8 февраля 2016

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

Курс читает профессор В. А. Захаров.

Лекционная нагрузка — 48 ч., семинары — 16 ч.

Программа

Часть 1. Математические модели.

1. Характерные особенности и примеры распределенных систем компьютерные сети, локальные и глобальные сети, многопроцессорные компьютеры). Архитектура распределенных систем. Стандарт ISO Open System Interconnection. Алгоритмические проблемы организации вычислений распределенных систем. Особенности распределенных алгоритмов.
2. Математическая модель распределенных систем. Системы переходов. Синхронный и асинхронный обмен сообщениями. Зависимые и независимые события. Причинно-следственный порядок событий. Эквивалентность выполнений. Вычисления. Логические часы. Топологии распределенных систем.

   Часть 2. Коммуникационные протоколы.

3. Коммуникационные протоколы. Ошибки, возникающие при передаче сообщений. Задача надежного обмена сообщениями. Симметричные протокол раздвижного окна: устройство протокола и обоснование его корректности. Протокол альтернирующего бита.
4. Коммуникационный протокол с таймером: устройство и обоснование корректности.
5. Задача маршрутизации. Алго-ритмы построения кратчай-ших путей в графе. Алгоритм Флойда-Уоршалла. Алгоритм Туэга. Алгоритм Мерлина-Сигала. Алгоритм Чанди-Мизры. Алгоритм Netchange.

   Часть 3. Распределенные алгоритмы.

6. Волновые алгоритмы: определение, основные свойства, область применения. Древесный алгоритм.
7. Алгоритм эха. Фазовый алгоритм. Алгоритм Финна. Алгоритмы обхода. Распределенный обход в глубину. Алгоритмы обхода Авербаха и Сидон.
8. Задача избрания лидера. Избрание лидера на кольцах: алгоритм Ченя-Робертса, оптимальный алгоритм Патерсона –Долева-Клейва-Роде. Избрание лидера в произвольных сетях: алгоритм Галладжера-Хамблета-Спиры, алгоритм Кораха-Каттена-Морана.
9. Задача обнаружения завершения вычисления. Алгоритм Дейкстры-Шолтена. Алгоритм Шави-Франчеза. Алгоритм возвращения кредитов. Алгоритм Раны. Применение алгоритмов обнаружения завершения вычислений для выявления блокировки вычислений.
10. Задача сохранения моментального состояния. Алгоритм Чанди-Лампорта. Алгоритм Лаи-Янга.

    Часть 4. Вопросы надежности распределенных алгоритмов.

11. Задача обеспечения отказоустойчивости распределенных систем. Невозможность построения робастных асин-хронных систем. Синхронные робастные алгоритмы принятия решения. Использование криптографических примитивов для повышения отказоустойчивости.
12. Стабилизирующиеся алгоритмы. Пример Дейкстры. Общие принципы построения стабилизирующихся алгоритмов.
13. (Список задач.(pdf))

Литература

1. G. Tel. Introduction to Distributed Algorithms. Cambridge University Press. 2000. (русск. пер. Ж. Тель. Введение в распределенные алгоритмы, изд-во МЦНМО, 2009 г., 616 с.)