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