|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Распределенные алгоритмыучебный курс
- Автор: Захаров В.А.
- Год создания: 2005
- Организация: МГУ имени М.В. Ломоносова
- Описание: Цель учебного курса – ознакомить студентов, специализирующихся в области программирования, с основными алгоритмическими задачами, возникающими при проектировании распределенных программ (сетевых протоколов, встроенных систем, многопроцессорных вычислительных систем, параллельных программ), наиболее распространенными алгоритмами решения этих задач, математическими моделями и методами, используемыми для анализа распределенных алгоритмов. Основное внимание уделяется вопросам доказательства корректности проектируемых алгоритмов и оценкам их эффективности. Спецкурс состоит из четырех частей. В первой части курса рассматриваются общие вопросы назначения, устройства и проектирования распределенных вычислительных систем. Также вводится единая математическая модель распределенных программ и устанавливаются основные свойства и возможности выполнений параллельных программ. Во второй части курса рассматривается задача построения надежных и корректных коммуникационных протоколов, а также задача маршрутизации. Описываются и анализируются протокол «раздвижного окна» и коммуникационный протокол с таймерами. Также описываются и анализируются алгоритмы маршрутизации (алгоритм Туэга, алгоритм Мерлина-Сигала, алгоритм Чанди-Мизры, алгоритм Netchange). В третьей части курса рассматриваются алгоритмы решения трех фундаментальных задач теории распределенных алгоритмов – широковещательное распространение сообщений, избрание лидера и обнаружение завершения вычисления. Подробно изучается класс волновых алгоритмов, в т. ч. алгоритмы обхода сетей. Рассказывается о том, как адаптировать волновые алгоритмы для решения задач избрания лидера и обнаружения завершения вычислений. Рассматриваются также оптимальные алгоритмы избрания лидера и обнаружения завершения вычислений. В четвертой части курса исследуется задача построения отказоустойчивых распределенных систем. Основное внимание уделяется принципам устройства робастных и стабилизирующихся алгоритмов на примере задач достижения консенсуса и избрания лидера.
- Добавил в систему: Захаров Владимир Анатольевич