Распределенные алгоритмы и системы — различия между версиями
Материал из Кафедра математической кибернетики
Root (обсуждение | вклад) |
|||
| Строка 7: | Строка 7: | ||
<h4>'''[[Media: Tasks_DisAlg.pdf| ЗАДАЧИ К ЭКЗАМЕНУ.]]'''</h4> | <h4>'''[[Media: Tasks_DisAlg.pdf| ЗАДАЧИ К ЭКЗАМЕНУ.]]'''</h4> | ||
| + | <!-- | ||
<h4>'''[[Media: G-521-2017.pdf| ТЕКУЩАЯ УСПЕВАЕМОСТЬ.]]'''</h4> | <h4>'''[[Media: G-521-2017.pdf| ТЕКУЩАЯ УСПЕВАЕМОСТЬ.]]'''</h4> | ||
<h4>'''[[Media: G-521-2017.pdf| НАЧАЛО ЭКЗАМЕНА - 10.00]]'''</h4> | <h4>'''[[Media: G-521-2017.pdf| НАЧАЛО ЭКЗАМЕНА - 10.00]]'''</h4> | ||
| − | + | --> | |
== Программа == | == Программа == | ||
| Строка 16: | Строка 17: | ||
<h4>Часть 1. Математические модели.</h4> | <h4>Часть 1. Математические модели.</h4> | ||
| − | #Характерные особенности и примеры распределенных систем компьютерные сети, локальные и глобальные сети, многопроцессорные компьютеры). Архитектура распределенных систем. Стандарт ISO Open System Interconnection. Алгоритмические проблемы организации вычислений распределенных систем. Особенности распределенных алгоритмов. '''[[Media: DistrAlg_1.pdf| Лекция 1.]]''' | + | #Характерные особенности и примеры распределенных систем компьютерные сети, локальные и глобальные сети, многопроцессорные компьютеры). Архитектура распределенных систем. Стандарт ISO Open System Interconnection. Алгоритмические проблемы организации вычислений распределенных систем. Особенности распределенных алгоритмов. <!-- '''[[Media: DistrAlg_1.pdf| Лекция 1.]]'''--> |
| − | #Математическая модель распределенных систем. Системы переходов. Синхронный и асинхронный обмен сообщениями. Зависимые и независимые события. Причинно-следственный порядок событий. Эквивалентность выполнений. Вычисления. Логические часы. Топологии распределенных систем. '''[[Media: DistrAlg_2.pdf| Лекция 2.]]''' | + | #Математическая модель распределенных систем. Системы переходов. Синхронный и асинхронный обмен сообщениями. Зависимые и независимые события. Причинно-следственный порядок событий. Эквивалентность выполнений. Вычисления. Логические часы. Топологии распределенных систем. <!--'''[[Media: DistrAlg_2.pdf| Лекция 2.]]'''--> |
#: | #: | ||
#:<h4>Часть 2. Коммуникационные протоколы.</h4> | #:<h4>Часть 2. Коммуникационные протоколы.</h4> | ||
#: | #: | ||
| − | #Коммуникационные протоколы. Ошибки, возникающие при передаче сообщений. Задача надежного обмена сообщениями. Симметричные протокол раздвижного окна: устройство протокола и обоснование его корректности. Протокол альтернирующего бита. '''[[Media: DistrAlg_3.pdf| Лекция 3.]]''' | + | #Коммуникационные протоколы. Ошибки, возникающие при передаче сообщений. Задача надежного обмена сообщениями. Симметричные протокол раздвижного окна: устройство протокола и обоснование его корректности. Протокол альтернирующего бита. <!--'''[[Media: DistrAlg_3.pdf| Лекция 3.]]'''--> |
| − | #Коммуникационный протокол с таймером: устройство и обоснование корректности. '''[[Media: DistrAlg_4.pdf| Лекция 4.]]''' | + | #Коммуникационный протокол с таймером: устройство и обоснование корректности. <!--'''[[Media: DistrAlg_4.pdf| Лекция 4.]]'''--> |
| − | #Задача маршрутизации. Алгоритмы построения кратчайших путей в графе. Алгоритм Флойда-Уоршалла. Алгоритм Туэга. Алгоритм Мерлина-Сигала. Алгоритм Чанди-Мизры. '''[[Media: DistrAlg_5.pdf| Лекция 5.]]''' Алгоритм Netchange. Разнообразие алгоритмов маршрутизации. '''[[Media: DistrAlg_6.pdf| Лекция 6.]]''' | + | #Задача маршрутизации. Алгоритмы построения кратчайших путей в графе. Алгоритм Флойда-Уоршалла. Алгоритм Туэга. Алгоритм Мерлина-Сигала. Алгоритм Чанди-Мизры. <!--'''[[Media: DistrAlg_5.pdf| Лекция 5.]]'''--> Алгоритм Netchange. Разнообразие алгоритмов маршрутизации. <!--'''[[Media: DistrAlg_6.pdf| Лекция 6.]]'''--> |
#: | #: | ||
#:<h4>Часть 3. Распределенные алгоритмы.</h4> | #:<h4>Часть 3. Распределенные алгоритмы.</h4> | ||
#: | #: | ||
| − | #Волновые алгоритмы: определение, основные свойства, область применения. Древесный алгоритм. Алгоритм эха. '''[[Media: DistrAlg_7.pdf| Лекция 7.]]''' Фазовый алгоритм. Алгоритм Финна. Алгоритмы обхода. Распределенный обход в глубину. Алгоритмы обхода Авербаха и Сидон. '''[[Media: DistrAlg_8.pdf| Лекция 8.]]''' | + | #Волновые алгоритмы: определение, основные свойства, область применения. Древесный алгоритм. Алгоритм эха. <!--'''[[Media: DistrAlg_7.pdf| Лекция 7.]]'''--> Фазовый алгоритм. Алгоритм Финна. Алгоритмы обхода. Распределенный обход в глубину. Алгоритмы обхода Авербаха и Сидон. <!--'''[[Media: DistrAlg_8.pdf| Лекция 8.]]'''--> |
| − | #Задача избрания лидера. Избрание лидера на кольцах: алгоритм Ченя-Робертса, оптимальный алгоритм Патерсона –Долева-Клейва-Роде. '''[[Media: DistrAlg_9.pdf| Лекция 9.]]''' Избрание лидера в произвольных сетях: алгоритм Галладжера-Хамблета-Спиры, алгоритм Кораха-Каттена-Морана. '''[[Media: DistrAlg_10.pdf| Лекция 10.]]''' | + | #Задача избрания лидера. Избрание лидера на кольцах: алгоритм Ченя-Робертса, оптимальный алгоритм Патерсона –Долева-Клейва-Роде. <!--'''[[Media: DistrAlg_9.pdf| Лекция 9.]]'''--> Избрание лидера в произвольных сетях: алгоритм Галладжера-Хамблета-Спиры, алгоритм Кораха-Каттена-Морана. |
| − | #Задача обнаружения завершения вычисления. Алгоритм Дейкстры-Шолтена. Алгоритм Шави-Франчеза. Алгоритм Сафры. Алгоритм возвращения кредитов. Алгоритм Раны. '''[[Media: DistrAlg_11.pdf| Лекция 11.]]''' | + | <!--'''[[Media: DistrAlg_10.pdf| Лекция 10.]]'''--> |
| − | #Задача сохранения моментального состояния. Алгоритм Чанди-Лампорта. Алгоритм Лаи-Янга. Применение алгоритмов обнаружения моментальной разметки и завершения вычислений для выявления блокировки вычислений. '''[[Media: DistrAlg_12.pdf| Лекция 12.]]''' | + | #Задача обнаружения завершения вычисления. Алгоритм Дейкстры-Шолтена. Алгоритм Шави-Франчеза. Алгоритм Сафры. Алгоритм возвращения кредитов. Алгоритм Раны. <!--'''[[Media: DistrAlg_11.pdf| Лекция 11.]]'''--> |
| + | #Задача сохранения моментального состояния. Алгоритм Чанди-Лампорта. Алгоритм Лаи-Янга. Применение алгоритмов обнаружения моментальной разметки и завершения вычислений для выявления блокировки вычислений. <!--'''[[Media: DistrAlg_12.pdf| Лекция 12.]]'''--> | ||
#: | #: | ||
#:<h4>Часть 4. Вопросы надежности распределенных алгоритмов.</h4> | #:<h4>Часть 4. Вопросы надежности распределенных алгоритмов.</h4> | ||
#: | #: | ||
| − | #Задача обеспечения отказоустойчивости распределенных систем. Невозможность построения робастных асинхронных систем. Синхронные робастные алгоритмы принятия решения. Использование криптографических примитивов для повышения отказоустойчивости. '''[[Media: DistrAlg_13.pdf| Лекция 13.]]''' | + | #Задача обеспечения отказоустойчивости распределенных систем. Невозможность построения робастных асинхронных систем. Синхронные робастные алгоритмы принятия решения. Использование криптографических примитивов для повышения отказоустойчивости. <!--'''[[Media: DistrAlg_13.pdf| Лекция 13.]]''' |
| − | #Стабилизирующиеся алгоритмы. Пример Дейкстры. Общие принципы построения стабилизирующихся алгоритмов. | + | #Стабилизирующиеся алгоритмы. Пример Дейкстры. Общие принципы построения стабилизирующихся алгоритмов.--> |
== Литература == | == Литература == | ||
#G. Tel. Introduction to Distributed Algorithms. Cambridge University Press. 2000. (русск. пер. Ж. Тель. Введение в распределенные алгоритмы, изд-во МЦНМО, 2009 г., 616 с.) | #G. Tel. Introduction to Distributed Algorithms. Cambridge University Press. 2000. (русск. пер. Ж. Тель. Введение в распределенные алгоритмы, изд-во МЦНМО, 2009 г., 616 с.) | ||
Версия 18:46, 11 февраля 2020
Обязательный курс для магистров 521 группы 10 семестра обучения.
Курс читает профессор В. А. Захаров.
Лекционная нагрузка — 48 ч., семинары — 16 ч.
Содержание
ЗАДАЧИ К ЭКЗАМЕНУ.
Программа
Часть 1. Математические модели.
- Характерные особенности и примеры распределенных систем компьютерные сети, локальные и глобальные сети, многопроцессорные компьютеры). Архитектура распределенных систем. Стандарт ISO Open System Interconnection. Алгоритмические проблемы организации вычислений распределенных систем. Особенности распределенных алгоритмов.
- Математическая модель распределенных систем. Системы переходов. Синхронный и асинхронный обмен сообщениями. Зависимые и независимые события. Причинно-следственный порядок событий. Эквивалентность выполнений. Вычисления. Логические часы. Топологии распределенных систем.
Часть 2. Коммуникационные протоколы.
- Коммуникационные протоколы. Ошибки, возникающие при передаче сообщений. Задача надежного обмена сообщениями. Симметричные протокол раздвижного окна: устройство протокола и обоснование его корректности. Протокол альтернирующего бита.
- Коммуникационный протокол с таймером: устройство и обоснование корректности.
- Задача маршрутизации. Алгоритмы построения кратчайших путей в графе. Алгоритм Флойда-Уоршалла. Алгоритм Туэга. Алгоритм Мерлина-Сигала. Алгоритм Чанди-Мизры. Алгоритм Netchange. Разнообразие алгоритмов маршрутизации.
Часть 3. Распределенные алгоритмы.
- Волновые алгоритмы: определение, основные свойства, область применения. Древесный алгоритм. Алгоритм эха. Фазовый алгоритм. Алгоритм Финна. Алгоритмы обхода. Распределенный обход в глубину. Алгоритмы обхода Авербаха и Сидон.
- Задача избрания лидера. Избрание лидера на кольцах: алгоритм Ченя-Робертса, оптимальный алгоритм Патерсона –Долева-Клейва-Роде. Избрание лидера в произвольных сетях: алгоритм Галладжера-Хамблета-Спиры, алгоритм Кораха-Каттена-Морана.
- Задача обнаружения завершения вычисления. Алгоритм Дейкстры-Шолтена. Алгоритм Шави-Франчеза. Алгоритм Сафры. Алгоритм возвращения кредитов. Алгоритм Раны.
- Задача сохранения моментального состояния. Алгоритм Чанди-Лампорта. Алгоритм Лаи-Янга. Применение алгоритмов обнаружения моментальной разметки и завершения вычислений для выявления блокировки вычислений.
Часть 4. Вопросы надежности распределенных алгоритмов.
- Задача обеспечения отказоустойчивости распределенных систем. Невозможность построения робастных асинхронных систем. Синхронные робастные алгоритмы принятия решения. Использование криптографических примитивов для повышения отказоустойчивости.
Литература
- G. Tel. Introduction to Distributed Algorithms. Cambridge University Press. 2000. (русск. пер. Ж. Тель. Введение в распределенные алгоритмы, изд-во МЦНМО, 2009 г., 616 с.)
