Правительство Российской Федерации
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
"Национальный исследовательский университет
"Высшая школа экономики"
Нижегородский филиал
Факультет бизнес-информатики и прикладной математики
Программа научно-исследовательского семинара
«Современные проблемы распределенных информационных систем»
для направления 080500.68– «Бизнес-информатика» подготовки магистра
Автор программы:
Бабкин Э.А., профессор
Рекомендована секцией УМС Одобрена на заседании кафедры
“Информатика” информационных систем и технологий
Председатель Зав. кафедрой
______________А.Н.Визгунов _____________________Бабкин Э.А.
«_____» __________________ 2011 г. «____»__________________ 2011г.
Утверждена УМС филиала
Председатель
______________Л.Г. Макарова
« ____» ___________________2011г.
Нижний Новгород, 2011
Настоящая программа не может быть использована другими подразделениями университета и другими вузами без разрешения кафедры-разработчика программы.
1Область применения и нормативные ссылки
Настоящая программа Научно-исследовательского семинара (далее – НИС) устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности.
Программа предназначена для преподавателей, ведущих НИС, учебных ассистентов и студентов направления 080500– «Бизнес-информатика», изучающих НИС.
Программа разработана в соответствии с:
ФГОС ВПО по направлению 080500– «Бизнес-информатика»;
ООП для направления 080500– «Бизнес-информатика»;
Рабочим учебным планом университета по направлению 080500– «Бизнес-информатика», утвержденным в 2010г.
2Цели освоения НИС
Целями освоения НИС являются изучение студентами принципов алгоритмического решения сложных проблем коммутации, маршрутизации, достижения консенсуса, обеспечения надежной работы в прикладных задачах, возникающих в распределенных информационных системах. У студентов в ходе изучения курса формируется четкое представление о структуре, свойствах, назначении и границах применимости подобных алгоритмов, используемых математических методах и программном инструментарии для анализа, состоянии международных научных исследований в перспективных направлений развития теории и практики распределенных систем в общей IT-структуре предприятия. Достижение целей обучения обеспечивает выпускнику получение высшего профессионально профилированного (на уровне магистра) образования и обладание перечисленными ниже общими и предметно-специализированными компетенциями. Они способствуют его социальной мобильности, устойчивости на рынке труда и успешной работе в таких сферах, как проектирование архитектуры предприятия, стратегическое планирование развития ИС и ИКТ управления предприятием, организация процессов жизненного цикла ИС и ИКТ управления предприятием, аналитическая поддержка процессов принятия решений для управления предприятием.
3Компетенции обучающегося, формируемые в результате освоения НИС
В результате освоения НИС студент должен:
усвоить терминологию, принятую в изучаемой дисциплине, ее основные понятия и определения;
знать основы теории и практики проектирования и эксплуатации распределенных систем, включая формальные модели сети, вычислительных процессов и ошибок;
знать назначение и принципы функционирования и основные алгоритмические свойства алгоритмов маршрутизации, выбора лидера, консенсуса, моментального представления, локальных и глобальных часов;
уметь применять полученные теоретические знания к решению практических вопросов планирования, проектирования, разработки, интеграции, анализа и эксплуатации сложных распределенных систем;
обладать навыками формализации проблем функционирования распределенных систем на основе различных математических формализмов.
В результате освоения НИС студент приобретает следующие компетенции:
Компетенция
|
Код по ФГОС/ НИУ
|
Дескрипторы – основные признаки освоения (показатели достижения результата)
|
Формы и методы обучения, способствующие формированию и развитию компетенции
|
Способность совершенствовать и развивать свой интеллектуальный и общекультурный уровень
|
ОК-1
|
Студент в состоянии дать определения изучаемым понятиям, анализирует взаимосвязи осваиваемых объектов и делает соответствующие выводы.
|
регулярные упражнения, включающие разбор стандартных технических приемов, самостоятельное выполнение задач по анализу данных и принятию решений, изучение базового теоретического материала и дополнительной литературы с целью тщательной подготовки к семинарским занятиям и контрольным работам
|
способностью к творческой адаптации к конкретным условиям выполняемых задач и их инновационным решениям
|
ОК-5
|
Самостоятельно изучает научную и техническую литературу, умеет анализировать информацию и применять полученные знания для решения поставленных задач.
|
систематическое изучение конспектов и электронных материалов, литературы по учебному плану, руководств по работе в вычислительных компьютерных средах, обсуждения возникающих вопросов с преподавателем и коллективом учебной группы, поиск нужной информации в библиотеках и сети Интернет
|
способностью готовить аналитические материалы для оценки мероприятий и выработки стратегических решений в области ИКТ
|
ПК-1
|
Демонстрирует навыки проведения анализа предметной области и представления результатов для аудитории.
|
грамотное выполнение и оформление домашних заданий, лабораторных работ и другой отчетности по изучаемой дисциплине
|
способностью применять методы системного анализа и моделирования для анализа архитектуры предприятий
|
ПК-3
|
Обладает опытом изучения предметной области с различных точек зрения и выработки решения в соответствии с требованиями задачи
|
решение задач анализа данных, имеющих характер самостоятельного исследования с применением современных вычислительных средств и компьютерного экспериментирования
|
способностью проводить исследования и поиск новых моделей и методов совершенствования архитектуры предприятия
|
ПК-10
|
Применяет навыки разработки математических моделей и алгоритмов распределенных систем.
|
самостоятельное проектирование и реализация алгоритмов распределенных систем
|
4Тематический план НИС
№
|
Название раздела
|
Всего часов
|
Аудиторные часы
|
Самостоятельная работа
|
Лекции
|
Семинары
|
1.
|
Технологические аспекты разработки и эксплуатации распределенных систем
|
6
|
|
2
|
4
|
2.
|
Введение в проблематику разработки и эксплуатации распределенных систем
|
8
|
|
2
|
6
|
3.
|
Коммуникационные протоколы
|
6
|
|
4
|
2
|
4.
|
Алгоритмы маршрутизации
|
10
|
|
4
|
6
|
5.
|
Неблокируемая коммутация пакетов
|
6
|
|
4
|
2
|
6.
|
Выбор лидера в синхронной сети
|
14
|
|
8
|
6
|
7.
|
Обнаружение завершения
|
12
|
|
8
|
4
|
8
|
Анонимные сети
|
6
|
|
4
|
2
|
9.
|
Синхронизация в сетях
|
8
|
|
4
|
4
|
10.
|
Отказоустойчивость в распределенных системах
|
18
|
|
8
|
10
|
11.
|
Моментальные состояния и логическое время в распределенных системах
|
14
|
|
8
|
6
|
Итого
|
108
|
0
|
56
|
52
| 5Формы контроля знаний студентов
Тип контроля
|
Форма контроля
|
1 год
|
Кафедра
|
Параметры **
|
3
|
4
|
|
|
Текущий
(неделя)
|
Контрольная работа
|
|
|
|
|
|
|
|
|
Домашнее задание
|
|
|
|
|
Итоговый
|
зачет
|
v
|
|
|
Заключительная письменная работа по материалам курса 90 мин.
| 5.1Критерии оценки знаний, навыков
Для любого из оговоренных в пункте 5 видов контроля требования к отчетности соотнесены с указанными в пункте 2 компетенциями. Результатом проверки работы является оценка, выставляемая по 10-ти балльной шкале в соответствии со следующими критериями:
высшая оценка в 10 баллов выставляется при отличном выполнении задания, то есть при наличии полных (с детальными пояснениями и культурой выкладок), оригинальных и правильных решений задач, дополненных при необходимости документами, полученными в результате реализации (проверки) решения в компьютерной вычислительной среде, верных ответов и высококачественного оформления работы.
оценка в 7-8-9 баллов выставляется при наличии решений задач и правильных ответов, но при отсутствии какого-либо из выше перечисленных отличительных признаков, как, например: детальных выкладок или пояснений, качественного оформления, представления алгоритма или последовательности решения задач.
Оценка в 6 баллов выставляется при наличии отдельных неточностей в ответах (включая грамматические ошибки) или неточностях в решении задач непринципиального характера (описки и случайные ошибки арифметического характера).
Оценка в 5 баллов выставляется в случаях, когда в ответах и в решениях задач имеются неточности и ошибки, свидетельствующие о недостаточном понимании вопросов и требующие дополнительного обращения к тематическим материалам.
Оценка в 4 балла выставляется при наличии серьезных ошибок и пробелов в знаниях по контролируемой тематике.
Оценка в 3 балла выставляется при наличии лишь отдельных положительных моментов в представленной работе.
Оценка в 2 балла выставляется при полном отсутствии положительных моментов в представленной работе.
Оценка в 1 или 0 баллов выставляется в случаях, когда небрежные записи, неправильные ответы и решения, кроме того, сопровождаются какими-либо демонстративными проявлениями безграмотности или неэтичного отношения к изучаемой теме и предмету в целом.
Высший балл при оценивании видов работ, не допускающих контроля за личным выполнением (домашние расчетные задания), может быть увязан с результатами контрольной работы по текущей теме.
6Содержание НИС
Количество часов аудиторной работы по разделам и общий объем самостоятельной работы указаны выше в пункте 4.
Раздел 1. Технологические аспекты разработки и эксплуатации распределенных систем
Сетевая архитектура. Модель ISO. Коммуникационные протоколы. Средства анализа и имитационного моделирования распределенных систем.
Основная литература [1].
Раздел 2. Введение в проблематику разработки и эксплуатации распределенных систем
Требования к точности. Классификация алгоритмов. Учет особенностей реального мира. Известные источники. Используемый математический аппарат. Модель сети. Модель вычислительного процесса. Модель коммуникационных каналов. Модель ошибок. Характеристики сложности. Учет сложности.
Основная литература [1].
Дополнительная литература [1].
Раздел 3. Коммуникационные протоколы
Симметричный протокол раздвижного окна. Протокол с таймерами.
Основная литература [1].
Раздел 4. Алгоритмы маршрутизации
Маршрутизация на основе узлов-адресатов. Задача построения картчайших путей для всех пар вершин. Алгоритм Netchange. Маршрутизация с использованием компактных таблиц. Иерархическая маршрутизация.
Основная литература [1].
Раздел 5. Неблокируемая коммутация пакетов
Структурированные решения. Неструктурированные решения.
Основная литература [1].
Раздел 7. Выбор лидера в синхронной сети
Суть проблемы. Выбор лидера в терминах формальной модели. Модификация исходной модели. Алгоритм LCR. Формальное доказательство корректности. Модификация алгоритма. Оценка сложности. Задачи по алгоритму. Библиография. Алгоритм HS. Анализ HS-алгоритма. Избрание лидера в произвольной сети. Алгоритм Корача-Каттена-Морана. Библиография.
Основная литература [1].
Дополнительная литература [1-8].
Раздел 7. Обнаружение завершения
Деревья и леса вычислений. Семейство волновых алгоритмов. Алгоритмы обхода. Сложность. Решения на основе волновых алгоритмов.
Основная литература [1].
Дополнительная литература [1-3].
Основные понятия. Детерминированные алгоритмы. Вероятностный алгоритм. Вычисление размера сети.
Основная литература [1].
Раздел 9. Синхронизация в сетях
Начальные сведения. Выборы в синхронных сетях. Алгоритмы-синхронизаторы. Поиск в ширину. Допущение Архимеда.
Основная литература [1].
Раздел 10. Отказоустойчивость в распределенных системах
Обзор проблемы. Робастные алгоритмы. Стабилизирующиеся алгоритмы. Формализация задачи консенсуса. Невозможность построения точного алгоритма. Рандомизированная версия алгоритма. Слабая завершаемость. Синхронные протоколы принятия решений. Протоколы с аутентификацией. Синхронизация часов.
Основная литература [1].
Дополнительная литература [1-8].
Раздел 11. Моментальные состояния и логическое время в распределенных системах
Начальные сведения. Алгоритмы построения моментального состояния. Обнаружение тупиков. Логическое время для асинхронных сетей. Введение времени в асинхронные алгоритмы. Применение в прикладных задачах. Преобразование реального времени в логическое время.
Основная литература [1].
Дополнительная литература [3-12].
7Образовательные технологии
В ходе семинарских занятий осуществляется подробный разбор решений типичных задач текущей тематики, обсуждается библиография по данной тете, заслушиваются доклады студентов по текущей тематике.
7.1Методические указания студентам
При выполнении заданий по темам НИС поощряется использование самостоятельно найденной справочной информации и программных разработок из Интернет–источников, но с обязательной ссылкой на адрес сайта и авторов использованных материалов. Предпочтительной представляется работа, выполненная, например, в виде адаптации существующего алгоритма на другом языке программирования или интеграции в целостную систему с указанием изменений, выполненных в оригинальном алгоритме с объективной оценкой характеристик полученного решения. Приветствуется работа с актуальными материалами из зарубежной профессиональной периодики, посвященными обсуждению реальных проблем построения и эксплуатации распределенных систем.
8Оценочные средства для текущего контроля и аттестации студента 8.1Тематика заданий текущего контроля
Программная реализация LCR-алгоритма.
Дайте пример назначения UID в котором коммуникационная сложность O(n2) .
Дайте пример назначения UID в котором коммуникационная сложность O(n).
Модифицировать оригинальный LCR-алгоритм, чтобы status=non-leader.
Рассмотрите проблему выбора лидера в синхронном кольце размера n, для случая, когда размер кольца известен всем процессам, а сами процессы не имеют уникальных идентификаторов (UID).
Придумайте алгоритм с использованием случайности, т.е. такой, в котором процессы могут делать случайный выбор в дополнение к детерминированным шагам.
Докажите корректность HS-алгоритма.
Рассмотрите такую модификацию алгоритма, в которой увеличение расстояния после каждой фазы l происходит по закону kl, k > 2. Получите оценку коммуникационной и временной сложности такого алгоритма.
Рассмотрите вариант HS-алгоритма, в котором процессы посылают сообщения только в одном направлении (используется топология двунаправленного кольца).
Определите, какой способ модификации алгоритма оставляет оценку коммуникационной сложности без изменения.
Придумайте алгоритм с использованием случайности, т.е. такой, в котором процессы могут делать случайный выбор в дополнение к детерминированным шагам.
Определите свойства алгоритма с использованием случайности. Например, существует ли для такого алгоритма абсолютная гарантия выбора единственного лидера ? Или же есть некоторая вероятность неспособности определения лидера ? Что можно сказать о коммуникационной и временной сложности такого алгоритма ?
Изучите и реализуйте распределенный алгоритма Беллмана-Форда.
Предложите такую модификацию алгоритма SyncBSF, в которой вычисляются не только указатели на дочерние вершины, но также информация о кратчайшем пути от дочерних вершин к родителям.
Разработайте наиболее эффективный алгоритм, который определяет общее число вершин в связном орграфе, в котором процессы имеют уникальные UID.
Предложите распределенный алгоритм, который вычисляет для каждого события показания векторных часов Маттерна.
Предложите определение часов для системы с синхронным обменом сообщениями и постройте распределенные алгоритмы для вычисления показаний таких часов.
8.2Вопросы для оценки качества освоения дисциплины
Предложите определение модели распределенной системы, в которой возможен как синхронный, так и асинхронный обмен сообщениями.
Подберите подходящее определение для причинно-следственного порядка переходов системы с синхронным обменом сообщениями.
Покажите, что симметричный протокол раздвижного окна не удовлетворяет требованию непременной доставки сообщения, если из двух допущений справедливости F1 и F2 выполняется только допущение F2.
Опишите вычисление протокола с таймерами, в ходе которого слово будет утрачено, но отправитель не сможет отметить это в отчете.
Докажите, что ни один алгоритм маршрутизации не способен обеспечить доставку пакетов по адресу, если сеть испытывает непрерывные изменения топологии.
Дайте детальное определение шагов индукции в доказательстве лемм о сложности LCR-алгоритма.
Докажите, что в среднем для всех различных вариантов назначения UID коммуникационная сложность O(nLogn).
Определите свойства алгоритма выбора единственного лидера использованием случайности. Например, существует ли для такого алгоритма абсолютная гарантия выбора единственного лидера? Или же есть некоторая вероятность неспособности определения лидера? Что можно сказать о коммуникационной и временной сложности такого алгоритма?
Покажите, что простейший способ модификации HS-алгоритма приводит к повышению оценки коммуникационной сложности (сложность > O(n log n)).
Рассмотрите проблему выбора лидера в синхронном кольце размера n, для случая, когда размер кольца известен всем процессам, а сами процессы не имеют уникальных идентификаторов (UID).
9Порядок формирования оценок по НИС
Преподаватель оценивает работу студентов на семинарских занятиях и самостоятельную работу, выставляя баллы за активность в аудитории, контрольные работы и домашние расчетные задания. Оценки за все виды работ преподаватель выставляет в рабочую электронную ведомость. Критерии их оценивания приведены выше в пункте 5.1.
Результирующая оценка Оаудиторная по 10-ти балльной шкале за работу в аудитории определяется перед итоговым контролем.
Результирующая оценка за текущий контроль учитывает результаты студента по текущему контролю следующим образом:
Отекущий = 0.15·Ок/р + 0.85·Одз ;
Результирующая оценка за итоговый контроль в форме зачета выставляется по следующей формуле, где Озачет – оценка за работу непосредственно на зачет:
Оитоговый = 0.45·Озачет +0.35·Отекущий + 0.2·Оаудиторная
10Учебно-методическое и информационное обеспечение НИС 10.1Основная литература
Тель Ж. Введение в распределенные алгоритмы. Пер. с англ. – М: МЦНМО, 2009. – 616с.
10.2Дополнительная литература
Linch N.A. Distributed Algorithms, Morgan Kaufmann, 1996.
Gerard Le Lann. Distributed systems – towards a formal approach. In Bruce Gilchrist, editor, Information Processing 77 (Toronto, August, 1977), volume 7 of Proceedings of IFIP Congress, pp. 155-160. North-Holland, Amsterdam, 1977.
Ernest Chang and Rosemary Roberts. An improved algorithm for decentralized extrema-finding in circular configurations of processes. Communications of the ACM, 22(5): 281-283, May 1979.
Robert W. Floyd. Assigning meanings to programs. In Mathematical aspects of Computer Science (New York, April, 1966), volume 19 of Proceedings of the Symposia in Applied Mathematics, pp.19-32. American Mathematical Society, Providence, 1967.
E.A. Ashcroft. Providing assertions about parallel programs. Journal of Computer and System Sciences, 10(1):110-135, February 1975.
Leslie Lamport. Providing the correctness of multiprocess programs. IEEE Transactions on Software Engineering, SE-3(2):125-143, March, 1977.
Leslie Lamport. Specifying concurrent program modules. ACM Transactions on Programming Languages and Systems, 5(2):190-222, April 1983.
D.S. Hirschberg and J.B. Sinclair. Decentralized extrema-finding in circular configurations of processes. Communications of ACM, 23 (11):627-628. November 1980.
G. N. Frederickson and N.A. Lynch. Electing a leader in a synchronous ring. Journal of the ACM, 34 (1):98-115. January 1987.
H. Attia, M. Snir, and M. K. Warmuth. Computing in a anonymous ring. Journal of the ACM, 35 (4):845-875. October 1988.
R. Bellman. On a routing problem. Quarterly of Applied Mathematics, 16 (1):87-90, 1958.
L. R. Ford, Jr. and D.R. Fulkerson. Flows in Networks. Princeton University Press, Princeton, N.J. 1962.
10.3Программные средства
Для успешного освоения дисциплины, студент использует следующий программный инструментарий: MIT Alloy Analyzer.
10.4Дистанционная поддержка НИС
Предусмотрено регулярное снабжение студентов текущими материалами по анализу данных в форме электронных документов, содержащих лекции, практические пособия по использованию вычислительных сред, примеры компьютерного экспериментирования в ходе выполнения учебного плана.
11Материально-техническое обеспечение НИС
Для обучения используются средства вычислительной техники, проектор.
Автор программы Э.А. Бабкин
|
