Распределенные алгоритмы и системы — различия между версиями
Материал из Кафедра математической кибернетики
| Строка 1: | Строка 1: | ||
| − | + | Обязательный курс для магистров 521 группы 10 семестра обучения. Курс читает профессор [[Захаров Владимир Анатольевич|В. А. Захаров]]. | |
| + | Лекционная нагрузка — 48 ч., семинары — 16 ч. | ||
== Программа == | == Программа == | ||
| Строка 12: | Строка 13: | ||
#Коммуникационные протоколы. Ошибки, возникающие при передаче сообщений. Задача надежного обмена сообщениями. Симметричные протокол раздвижного окна: устройство протокола и обоснование его корректности. Протокол альтернирующего бита. | #Коммуникационные протоколы. Ошибки, возникающие при передаче сообщений. Задача надежного обмена сообщениями. Симметричные протокол раздвижного окна: устройство протокола и обоснование его корректности. Протокол альтернирующего бита. | ||
#Коммуникационный протокол с таймером: устройство и обоснование корректности. | #Коммуникационный протокол с таймером: устройство и обоснование корректности. | ||
| − | #Задача маршрутизации. | + | #Задача маршрутизации. Алго-ритмы построения кратчай-ших путей в графе. Алгоритм Флойда-Уоршалла. Алгоритм Туэга. Алгоритм Мерлина-Сигала. Алгоритм Чанди-Мизры. Алгоритм Netchange. |
#: | #: | ||
#:<h4>Часть 3. Распределенные алгоритмы.</h4> | #:<h4>Часть 3. Распределенные алгоритмы.</h4> | ||
Версия 13:20, 8 февраля 2016
Обязательный курс для магистров 521 группы 10 семестра обучения. Курс читает профессор В. А. Захаров. Лекционная нагрузка — 48 ч., семинары — 16 ч.
Содержание
Программа
Часть 1. Математические модели.
- Характерные особенности и примеры распределенных систем компьютерные сети, локальные и глобальные сети, многопроцессорные компьютеры). #Архитектура распределенных систем. Стандарт ISO Open System Interconnection. Алгоритмические проблемы организации вычислений распределенных систем. Особенности распределенных алгоритмов.
- Математическая модель распределенных систем. Системы переходов. Синхронный и асинхронный обмен сообщениями. Зависимые и независимые события. #Причинно-следственный порядок событий. Эквивалентность выполнений. Вычисления. Логические часы. Топологии распределенных систем.
Часть 2. Коммуникационные протоколы.
- Коммуникационные протоколы. Ошибки, возникающие при передаче сообщений. Задача надежного обмена сообщениями. Симметричные протокол раздвижного окна: устройство протокола и обоснование его корректности. Протокол альтернирующего бита.
- Коммуникационный протокол с таймером: устройство и обоснование корректности.
- Задача маршрутизации. Алго-ритмы построения кратчай-ших путей в графе. Алгоритм Флойда-Уоршалла. Алгоритм Туэга. Алгоритм Мерлина-Сигала. Алгоритм Чанди-Мизры. Алгоритм Netchange.
Часть 3. Распределенные алгоритмы.
- Волновые алгоритмы: определение, основные свойства, область применения. Древесный алгоритм.
- Алгоритм эха. Фазовый алгоритм. Алгоритм Финна. Алгоритмы обхода. Распределенный обход в глубину.
- Задача избрания лидера. Избрание лидера на кольцах: алгоритм Ченя-Робертса, оптимальный алгоритм Патерсона –Долева-Клейва-Роде.
- Избрание лидера в произвольных сетях: алгоритм Галладжера-Хамблета-Спиры.
- Задача обнаружения завершения вычисления. Алгоритм Дейкстры-Шолтена. Алгоритм Шави-Франчеза. Алгоритм возвращения кредитов. Алгоритм Раны. #Применение алгоритмов обнаружения завершения вычислений для выявления блокировки вычислений.
- Задача сохранения моментального состояния. Алгоритм Чанди-Лампорта. Алгоритм Лаи-Янга.
- (Список задач.(pdf))
Литература
- G. Tel. Introduction to Distributed Algorithms. Cambridge University Press. 2000.
