litceysel.ru
добавить свой файл
1
Программа курса

«Распределенные системы и алгоритмы» 

1. Авторы: Миков Александр Иванович, доктор физико-математических наук, профессор; Замятина Елена Борисовна, кандидат физико-математических наук, доцент.

2. Рекомендуется студентам 6 курса (второго года магистратуры) по направлениям «Прикладная математика и информатика», «Прикладная информатика». Материалы курса могут также использоваться при проведении занятий для студентов старших курсов направления «Информационные технологии».

3. Объем курса:


  • Общий объем курса (включая самостоятельную работу): 110 часов.

  • Лекции:  32 академических часа.

  • Практикумы: 16 академических часов.

  • Лабораторные работы: 16 часов

количество работ – 4;

число академических часов – 48 (включая часы, отведенные для самостоятельной работы).

4. Цели и задачи курса:

Проблематика распределенных систем весьма широка. Курс затрагивает только те вопросы, в которых центральными являются распределенные задачи. Он не касается аппаратных вопросов и протоколов низкого уровня.

Курс посвящен распределенным алгоритмам, решающим задачи для распределенных систем. Авторы убеждены, что хотя общая теория имеет несомненную ценность, обучать студентов лучше сначала на хороших примерах. Лекционный курс содержит ряд формулировок задач, специфических именно в распределенной постановке, и распределенные алгоритмы, решающие эти задачи в распределенных компьютерных системах (сетях).

Первая цель состоит в том, чтобы научить студентов ставить распределенные задачи. Для этого им демонстрируются такие постановки в области организационных информационных систем, в области имитационного моделирования, в области баз данных.

Вторая цель состоит в том, чтобы научить студентов разрабатывать распределенные алгоритмы (не путать с распределенными программами), решающие распределенные задачи. Демонстрируются примеры в перечисленных выше областях, а также «элементарные» системные алгоритмы.


Задачами курса, реализуемыми посредством лабораторных работ, являются также овладение навыками реализации распределенных алгоритмов с использованием технологии .Net, отладки распределенных программ и их исследования.

5. Содержание (программа курса):

Раздел 1. Распределенные задачи и системы.

Лекция 1. Распределенные системы (2 часа).

Введение. Предпосылки возникновения распределенных систем. Обзор проблем. Распределенные организационные системы: корпорации, системы государственного административного управления и контроля, банковские системы. Локальные и глобальные цели. Распределенные цели и задачи. Раздельное решение локальных задач, формирование решения глобальной задачи из решений локальных задач.

Лекция 2. Распределенные задачи и алгоритмы (2 часа).

Связь задач и алгоритмов. Примеры формализации распределенных задач и алгоритмов. Простой криптографический протокол. Применение распределенных систем для ускорения решения сосредоточенных задач.

Лекция 3. Надежность и безопасность распределенных систем (2 часа).

Проблемы надежности и безопасности решения задач в распределенных системах. Сравнение архитектур технических средств сосредоточенной и распределенной систем.

Лекция 4. Пример. Распределенная информационная система организации. Концепции (2 часа).

Основные подходы к проектированию распределенной организационной информационной системы регионального масштаба. Структура информационного пространства и структуры ИС. Характеристики ИС.

Лекция 5. Пример. Распределенная информационная система организации. Архитектура (2 часа).

Цели и основные задачи, решаемые с помощью распределенной информационной системы. Основные подсистемы и методы реализации. Схемы взаимодействия.

Раздел 2. Распределенные прикладные алгоритмы.

Лекция 6. Моделирование распределенных систем. Язык Triad (2 часа).


Средства описания распределенных систем. Событийно-ориентированный подход. Описание многоуровневой распределенной архитектуры. Описание поведения. Описание структуры сообщений.

Лекция 7. Распределенное имитационное моделирование (2 часа).

Причины перехода к распределенному моделированию. Типы и свойства распределенных систем имитационного моделирования (прозрачность, масштабируемость, интероперабельность и т.д.). Отличие распределенного алгоритма от централизованного (отсутствие знаний о глобальном состоянии, о глобальном времени, недетерминизм). Объединение разнородных систем моделирования. Время в системах моделирования.

Лекция 8. Синхронизация времени в распределенном имитационном моделировании (2 часа).

Управление временем в распределенных системах моделирования. Консервативный и оптимистический алгоритмы управления временем. Алгоритмы синхронизации.

Лекция 9. Балансировка нагрузки в распределенных системах (2 часа).

Параллелизм задач. Технология распараллеливания: декомпозиция задачи на подзадачи. Причины появления несбалансированной нагрузки. Статическая и динамическая балансировка. Постановка задачи динамической балансировки. Методология практического решения задачи балансировки. Алгоритмы балансировки: случайный алгоритм; алгоритм, основанный на коммуникациях; алгоритм, основанный на вычислении нагрузки.

Лекция 10. Распределенные интеллектуальные системы на основе агентов (2 часа).

Понятие программного агента в распределенной системе. Свойства автономных агентов. Мультиагентные системы. Операции с агентами. Интеллектуальные агенты. Пример использования мобильного агента для обслуживания мобильного пользователя. Пример решения задачи управления на основе мультиагентной системы.

Лекция 11. Распределенное хранение информации (2 часа).

Распределенные базы данных, их отличие от централизованных баз. Фрагментация – горизонтальная и вертикальная. Репликация. Синхронные и асинхронные репликации. Протокол двухфазной фиксации транзакций. Схемы владения данными в распределенной БД.


Раздел 3. Распределенные системные алгоритмы.

Лекция 12. Волновые алгоритмы распространения информации (2 часа).

Связь между вычислительными узлами распределенной системы. Определение волновых алгоритмов, используемых для решения задач: а) широковещательной рассылки; б) глобальной синхронизации; в) вычисления функции, входные данные которой распределены между процессами и т.д. Волновой алгоритм для кольцевой архитектуры и для архитектуры дерева. Алгоритм голосования. Алгоритм «Эхо». Фазовый алгоритм. Алгоритм Финна.

Лекция 13. Алгоритмы обхода сайтов (2 часа).

Алгоритмы обхода; (рассматриваются как волновые алгоритмы, в которых все события вычисления алгоритма совершенно упорядочены каузальным отношением). Алгоритмы для распределенного поиска в глубину и вычисление сложности алгоритмов. Алгоритм обхода полного графа. Алгоритм обхода тора. Алгоритм обхода гиперкуба. Алгоритм Тарри.

Лекция 14. Алгоритмы выбора сайтов (2 часа).

Определение алгоритма выбора. Алгоритм смещения и демонстрация его работы на примере. Выбор с помощью алгоритма для деревьев. Алгоритмы в компьютерных сетях с кольцевой топологией (алгоритм Ле Ланна, Чанга-Робертса).

Лекция 15. Поиск в пиринговых системах (2 часа).

Понятие сети peer-to-peer. Преимущества и недостатки пиринговых сетей. Механизмы поиска информации в известных сетях Пример: метод поиска изображений с помощью распределенного алгоритма статического «замораживания» нечетких (fuzzy) запросов.

Лекция 16. Тенденции в области распределенных систем (2 часа).

Нерешенные и перспективные проблемы теории и практики распределенных систем. Направления исследований. Обработка информации в суперсетях (Грид). Архитектура Грид. Мобильный компьютинг. Тотальный (pervasive) компьютинг. Глобальное «умное» пространство.


6. Литература:

Основная:

  1. Танненбаум Э., Ван Стеен М. Распределённые системы. Принципы и парадигмы.-СПб.:Питер, 2003.-877с.


  2. Теl G. Introduction to Distributed Algorithms. Cambridge University Press, 1994, 534 p.

  3. Coulouris G., Dollimore J., Kindberg T. Distributed Systems. Concepts and Design. Addison-Wesley Publishing Company, 1995, 644 p.


Дополнительная:

  1. Королев Л.Н., Миков А.И. Информатика. Введение в компьютерные науки. – М.: высшая школа, 2003.

  2. Yu-Kwong Kwok and Lap-Sun Cheung. A new fuzzy-decision based load balancing system for distributed object computing/Journal of Parallel and Distributed Computing, 64 (2004) 238-253

  3. H. Baala, O. Flauzac, J. Gaber, M. Bui and T. El-Ghazawi. A self-stabilizing distributed algorithm for spanning tree construction in wireless ad hoc networks. Journal of Parallel and Distributed Computing, 63 (2003) 97-104

  4. Jiannong Cao, Yudong Sun, Xianbin Wang and Sajal K. Das. Scalable load balancing on distributed web servers using mobile agents.Journal of Parallel and Distributed Computing, 63 (2003) 996-1005

  5. Ras Z.W., Dardzinska A. Ontology-based distributed autonomous knowledge systems, Information Systems 29 (2004) 47–58.

  6. Миков А.И. Основы построения региональной распределенной информационной системы образования и науки. // Математика программных систем: Межвуз. сб. науч. тр./ Перм. ун-т. – Пермь, 2002. С. 4 – 24.