автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Адаптивный алгоритм управления координатором в распределенных системах обработки информации

На правах рукописи

ии^45658Э

Сан Ян Наинг У

•Ям ^

СО1

АДАПТИВНЫЙ АЛГОРИТМ УПРАВЛЕНИЯ КООРДИНАТОРОМ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ ОБРАБОТКИ ИНФОРМАЦИИ

05.13.01 - Системный анализ, управление и обработка информации (в приборостроении)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

о 5 ДЕК ИОВ

Москва - 2008

003456589

Работа выполнена на кафедре Информатики и программного обеспечения вычислительных систем в Московском государственном институте электронной техники (техническом университете) Научный руководитель: Доктор технических наук, профессор

Гагарина Лариса Геннадиевна

Официальные оппоненты: Доктор технических наук

Щагин Анатолий Васильевич

Кандидат технических наук, Степанов Андрей Михайлович

Ведущая организация: ОАО «ОТИК»

Защита состоится « |» I 2 200 £ года в : .^¡рна заседании диссертационного совета Д 212.134.02 при Московском государственном институте электронной техники (техническом университете) по адресу: 124498, Москва, Зеленоград, проезд 4806, МИЭТ

С диссертацией можно ознакомиться в библиотеке МИЭТ.

Автореферат разослан « » ^ ( 200 £ г.

Ученый секретарь диссертационного совета д.т.н., доцент А.В. Гуреев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность проблемы

Современное приборостроительное производство представляет собой сложный комплекс с высокими темпами технического прогресса в области теории и практики автоматизации как при управлении подвижными объектами, физическими и технологическими процессами в производстве и научных исследованиях, так и в области интеллектуальной деятельности. Управление такими комплексами, характеризующимися большими объемами разнородной информации, является сложной задачей, решение которой во многом зависит от методов, моделей и алгоритмов обработки и представления информации.

Распределенные системы обработки информации (РСОИ) являются перспективным направлением в области управления производственными комплексами. РСОИ в настоящее время широко используются при проведении научных исследований, проектировании и разработке информационно-управляющих систем и процессов, в процессах дистанционного обучения специалистов и многих других сферах научной и практической деятельности. Постоянное развитие и совершенствование информационных технологий оказывает существенное влияние на все научные и технологические направления, связанные с использованием РСОИ. Эволюция РСОИ все в большей степени определяется их надежностью и устойчивостью, которые обеспечивают, во-первых, расширение круга задач, решаемых с помощью компьютеров, и, во-вторых, повышают уровень обработки информации.

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

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

В целом проблема управления координатором, а также обеспечение взаимного исключения - это классические проблемы распределенных систем. Алгоритм управления координатором предназначен для того, чтобы выбрать один из процессов дд« выполнения специальной роли

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

Для выполнения задачи координации среди узлов РСОИ, координатор должен функционировать на протяжении всего времени работы этой системы. Однако, в работе компьютерных систем, в том числе в распределенных системах, необходимо учитывать вероятность отказа. Эта вероятность намного выше в распределенной системе большого размера с тысячами одновременно выполняющихся процессов. Очень быстро координатор может стать узким местом в работе системы и действовать как единственный пункт отказа.

Теоретическим исследованиям и разработке фундаментальных основ РСОИ, созданию математического аппарата, моделей и методов обработки и управления координатором посвящены труды видных ученых Н. Garsia-Molina, G. Singh, S. Olariu, A. Nakano и многих других.

Большинство существующих алгоритмов выбора координатора в РСОИ основано на индивидуальной передаче сообщений между процессами. Однако, этой схеме работы алгоритмов присущ ряд недостатков. Во-первых, участвующие процессы должны располагать подробной информацией об адресах других процессов. Во-вторых, эта схема усложняет обработку изменений в размере группы процессов и существенно увеличивает трафик в сети.

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

В последнее время было разработано много алгоритмов и Методов, минимизирующих коммуникационную сложность. Однако ни один из алгоритмов не обеспечивает сложность лучше, чем 0(п log п), где п -число процессов. Таким образом, актуальными являются разработка и исследование адаптивного алгоритма управления координатором в

РСОИ, который учитывает переменный сетевой трафик и является более эффективным, чем существующие алгоритмы. Цели и задачи диссертационной работы

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

Поставленная цель определяет следующие основные задачи:

1. Анализ принципов надежной 1рупповой рассылки сообщений в РСОИ.

2. Разработка адаптивного алгоритма управления координатором для РСОИ в условиях надежной групповой рассылки.

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

4. Адаптация алгоритма управления координатором к условиям переменного сетевого трафика.

Методы исследования

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

Научная новизна работы состоит в разработке алгоритма управления координатором для РСОИ; алгоритм основан на групповой рассылке сообщений и является адаптивным к изменению сетевого трафика. В ходе выполнения диссертационных исследований получены следующие новые научные результаты:

1. Разработан адаптивный алгоритм управления координатором в РСОИ при использовании механизма надежной групповой рассылки, что значительно упрощает протокол, так как у членов группы нет необходимости знать адреса друг друга для отправки сообщений и делать реконфигурации группы при изменении ее размера; а также снижает сетевой трафик, так как алгоритм предусматривает участие в выборе координатора только ограниченного количества процессов, и все сообщения передаются в режиме групповой рассылки.

2. Разработано формализованное описание и аналитическая модель подсистемы выбора координатора и проведен анализ сценариев работы алгоритма для его проверки.

3. Осуществлена программная реализация алгоритма управления координатором, внедрение которого практически подтвердило повышение быстродействия РСОИ.

4. Разработана имитационная модель подсистемы выбора координатора в терминах расширенных сетей Петри при помощи программного средства моделирования Winsim. Результаты работы имитационной модели подтверждают, что разработанный алгоритм обеспечивает уменьшение коммуникационной сложности на 15% для РСОИ с 21 процессом при коэффициенте загрузки координатора 0,9. Сравнение результатов имитационного моделирования и аналитической модели показало их хорошее совпадение.

5. Проведен анализ динамики изменения коммуникационной сложности в зависимости от тайм-аутов для разного количества процессов.

Достоверность научных результатов

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

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

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

Представляется перспективным применение адаптивного алгоритма в транспортной отрасли для организации бесперебойного обмена данными между единицами транспорта, в логистике для организации управления складами и их охраны, в метеорологии для организации беспрерывного сбора, анализа метеоинформации и радиовещания. Личный вклад автора

Все основные результаты диссертационной работы получены лично автором, в частности:

1. На основе аналитического обзора средств и методов анализа алгоритмов показана актуальность разработки алгоритмов выбора координатора.

2. Проведена классификация существующих алгоритмов выбора координатора.

3. Разработан и исследован адаптивный алгоритм управления координатора в РСОИ, имеющий меньшую коммуникационную сложность, чем существующие алгоритмы, и адаптирующийся к условиям переменного сетевого трафика.

4. Разработано формализованное описание и математическая модель подсистемы выбора координатора на основе адаптивного алгоритма.

5. Разработана имитационная модель РСОИ для выбора координатора в терминах расширенных сетей Петри при помощи программного средства моделирования Winsim.

6. Реализована подсистема выбора координатора для РСОИ с использованием языка программирования С в ОС UNIX.

7. Проведен анализ динамики изменения коммуникационной сложности алгоритма в зависимости от длительности тайм-аутов для разного количества процессов.

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

В ходе проведенных исследований получены и выносятся на защиту следующие основные научные результаты:

1. Адаптивный алгоритм управления координатором в РСОИ в условиях надежной групповой рассылки, обеспечивающий низкий сетевой трафик.

2. Формализованное описание, аналитическая и имитационная модель подсистемы выбора координатора для РСОИ, использующие адаптивный алгоритм управления координатором для РСОИ в условиях надежной групповой рассылки.

3; Программная реализация блока голосования в узле РСОИ с использованием языка программирования С в операционной системе UNIX.

4. Результаты внедрения, экспериментальных исследований и апробация махсриалоБ диссертационной работы.

Апробация работы и публикации

Положения данной диссертации докладывались и обсуждались на следующих конференциях:

1. Международная школа-конференция (по приоритетному направлению «Информационно-телекоммуникационные системы» с участием молодых ученых, аспирантов и студентов стран-членов СНГ) -Москва, МИЭТ, 2005.

2. 13-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов "Микроэлектроника и информатика -2006" - Москва, МИЭТ, 2006.

3. 14-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов "Микроэлектроника и информатика -2007" - Москва, МИЭТ, 2007.

4. XI Московская международная телекоммуникационная конференция студентов и ученых «Молодежь и наука» - Москва, МИФИ, 2008.

По результатам проведенных научных исследований опубликовано 8 печатных работ без соавторов, в том числе одна работа - в издании, входящем в перечень ВАК. Структура и объем диссертации

Диссертация состоит из введения, четырех глав, заключения, библиографического списка из 77 наименований и приложения (включающего 5 частей). Работа изложена на 142 страницах, содержит 8 таблиц и 54 рисунка.

СОДЕРЖАНИЕ РАБОТЫ

^ Во введении дана общая характеристика работы, обоснована актуальность решаемой проблемы, сформулированы цель работы, проблемы и задачи исследования, перечислены положения, выносимые на защиту, показана научная новизна и практическая значимость результатов, рассмотрена структура диссертации и взаимосвязь отдельных глав.

В первой главе представлено описание предметной области, проведен анализ проблематики синхронных РСОИ. Выполнен обзор РСОИ и их классификации, проводимые по различным признакам, рассмотрены области применения распределенных систем различных типов. Проведен обзор существующих методов синхронизации процессов в РСОИ по различным классифицирующим группам, в частности, таким, как алгоритм взаимного исключения и выбора координатора.

Показана недостаточная адекватность существующих методов имеющимся задачам и определены недостатки существующих решений; обоснована необходимость разработки новых эффективных алгоритмов управления координатором для РСОИ.

Анализ характеристик РСОИ указывает на актуальность задачи разработки и исследования новых алгоритмов синхронизации таких систем. С целью решения этой задачи в диссертации проведено сравнение ряда существующих алгоритмов взаимного исключения и голосования.

В централизованных вычислительных системах используется общая память для вычислений, в то время как в РСОИ доступен только обмен сообщениями. Существует два типа систем: синхронные и асинхронные системы. Асинхронные системы просты и адаптированы к средам, обеспечивающим небольшую вераятность работоспособности. Однако в таких системах невозможно достигнуть согласованности в случае каких либо ошибок.

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

Во второй главе проведен анализ проблем групповой рассылки сообщений в распределенных вычислительных системах. Дана общая характеристика надежной групповой рассылки.

Групповая рассылка - это способность сети копировать данные, передаваемые источником, в определенных внутренних точках. Скопированные данные отправляются конечным системам получателя. Когда процесс посылает групповое сообщение, набор групповых маршрутизаторов отправляет отдельную копию сообщения на маршрутизатор локальной сети. Чтобы доставить сообщение адресатам, конечный маршрутизатор использует специальные аппаратные средства.

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

Групповая рассылка на канальном уровне

Групповая рассылка на основе дерева канального уровня является типичной для проводных локальных вычислительных сетей (ЛВС), таких как Ethernet или Token Ring, где для групповой и широковещательной рассылки достаточно относительно простой аппаратной поддержки. В частности, в ЛВС типа Ethernet каждая станция видит кадр, переданный станцией на общую шину через сетевые карты, и, если МАС-адрес (физический адрес) назначения кадра совпадает с адресом данной станции, то станция может принять этот кадр «на лету».

С другой стороны, если кадр предназначен для нескольких станций на шине, то принимающие прикладные процессы во всех станциях назначения могут заранее потребовать своей принадлежности к тому же IP-адресу групповой рассылки, и процесс-отправитель должен использовать этот адрес в качестве группового адреса назначения. В алгоритме IP версии 4 IP-адреса групповой рассылки принадлежат классу D, с диапазоном от224.0.0.0 до 239.255.255.255.

Групповая рассылка на сетевом уровне

В IP-модели групповой рассылки предполагается, что групповая IP-рассылка основана на протоколе UDP, таким образом, пакеты доставляются к месту назначения сетью с сервисом типа Best Effort, однако не гарантируется, что направленный пакет будет доставлен всем членам группы назначения. Любой процесс может направить IP-пакеты при помощи групповой рассылки в любое время. С этой целью источник должен знать только адрес группы рассылки. Источник может как быть так и не быть членом группы, при этом ему не требуется знать размер группы. Таким образом, модель поддерживает открытые и закрытые группы рассылки.

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

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

ществляется через Интернет-маршрутизаторы. Однако прежде чем пересылка может быть осуществлена, группа должна быть организована и должны быть установлены пути к ее членам.

Для управления групповой рассылкой используется протокол Internet Group Management Protocol (IGMP). Сферой его функционирования является лишь физическая сеть. В такой сети ЮМР используется для того, чтобы сообщить информацию о своей группе непосредственно связанным между собой маршрутизаторам.

На рис. 1. показана физическая сеть, с которой связан один маршрутизатор. Предполагается, что маршрутизатор управляет протоколом IGMP. В физической сети есть участники, принадлежащие двум различным группам групповой рассылки, 1 и 2. Информация об этих двух группах хранится в списке групп маршрутизатора в результате сообщений IGMP о членстве, направленных участниками группы в маршрутизатор. Когда пакет групповой рассылки с адресом IP, предназначенным группе 1 или 2, прибудет в маршрутизатор из другой физической сети, этот маршрутизатор, после консультации со своим списком групп, рассылает пакет в физической сети для того, чтобы его получили члены группы. Если в показанной физической сети не будет участников для пакета групповой рассылки, который получил маршрутизатор, то последний откажется от пакета.

Группа 1

/

К / с другой физической сети

Рис. 1. Обработка групповой передачи пакетов в маршрутизаторе.

В третьей главе разработано формальное описание распределенного алгоритма голосования и предложена общая схема алгоритма. Приведены главные аспекты предложенного алгоритма, типы сообщений и переменные, используемые в алгоритме. Разработана диаграмма состояния алгоритма для узла РСОИ, представленная на рис. 2.

Истбк Т2, авТАТ-1,8 нет 1В.Т

ф-

Конч Осн paß. норм сост.

1ЕП

tREP

JREQ, нач Т1

JREP

О

Ист«« Т1, SLEDR»1,S STAT=Q

SET (SEQN)

Истек T1, SLEDR=0 S STAT = 1

JELT, LEDR^O, STAT, начинать T2

течение T2, STAT=1,S нет Г ELT & _tlDR_

LEDR ~t. STAT-О

ИСТ4ИТ2, tELT 8 STAT-1

LOR — SRC. LEDR .- 1 .STAT 0

JLDR

течение T2, SSTAT-1.S TELT & UWHtSRC) д SELF

-О

I t1-0^ 8. «то Я

Состояние Г4-

лидера

Перезагру

Нач (осн Рэб). LE0R*-0, SEQN «- -1

-0-

LEDR tREQ

JREP

(B.T

JLDR

Состояние отказа

Рис. 2. Диаграмма состояния узла РСОИ при выполнении алгоритма выбора координатора.

Состояния на диаграмме имеют следующие значения: 0 - процесс выполняет очередной этап своей основной работы; 1 - процесс направил сообщение типа REQ и установил тайм-аут Тй 2 - процесс начал выбор (направил сообщение типа ELT) и установил тайм-аут Тг\ 3 -процесс направил сообщение типа LDR и ждет, чтобы стать новым координатором; 4 - процесс получил направленное сообщение LDR и стал новым координатором; 5 - отказ процесса.

Разработана реализация адаптивного алгоритма управления координатором в операционной системе UNIX, где процессы направляют сообщение через групповую рассылку с использованием сокетов UDP. В алгоритме каждый процесс проверяет существование координатора по посылке сообщения и по интервалу времени, а не путем непрерывной проверки. Поэтому нет необходимости того, чтобы каждый процесс находился в спин-ожидании, что приводило бы к увеличению нагрузки системы.

На рис. 3 показана схема данного алгоритма в узле РСОИ.

Начало

Рис. 3. Схема адаптивного алгоритма управления координатором в

РСОИ

Среднее число сообщений, посылаемое в течение процедуры выбора, определяет коммуникационную сложностью алгоритма. При оценке коммуникационной сложности во внимание принимаются только сообщения, рассылаемые в ходе одной процедуры выбора, то есть сообщения типов ELT и LDR.

В главе на основе разработанной аналитической модели работы узла РСОИ выведено соотношение для расчета коммуникационной сложности (КС) предложенного алгоритма:

КС-2+ W-2 )т„ (1)

где

N - число процессов в РСОИ;

т,/ - верхняя граница задержки доставки сообщения в сети от исходного процесса ко всем процессам в группе, включая задержки, связанные с буферизацией, направлением и получением сообщения; Т\ - значение времени тайм-аута в состоянии 1; Тпкпп ~ среднее значение длительности периода основной работы процесса;

Т2 - значение времени тайм-аута в состоянии 2.

При разработке аналитической модели предполагалось, что в модели коммуникационной подсистемы время доставки групповых сообщений является случайной равномерно распределенной величиной. Тогда значение времени Т\ должно удовлетворять неравенству

T,>2rd+Ts, (2)

где 2тd - время, необходимое для прохождения сообщения от исходного процесса к самому отдаленному процессу в группе и обратно;

Ts - максимальное время обслуживания запроса координатором. Также значение тайм-аута Г] должно удовлетворять неравенству Т2 > 2т,/, что означает, что процесс, направляя сообщение ELT, должен ждать возможного конфликтного сообщения в течение некоторого временного окна.

При этом большое время тайм-аута Т2 не влияет на сложность алгоритма, поскольку обнаружение конфликта участвующими процессами происходит в течение первой задержки 2rj тайм-аута Т2. Однако большой тайм-аут Т2 может увеличить временную сложность алгоритма.

14

Пусть продолжительность основной работы процесса является случайной величиной, распределенной по экспоненциальному закону с параметром МТтат. Следовательно, каждый процесс направляет сообщения REQ согласно распределению Пуассона со средней интенсивностью

Хс=У(Ттат+Т{), (3)

где Xс - средняя интенсивность входного потока заявок. Обозначим через Tim - время, в течение которого в системе существует координатор, Trpr - время,' в течение которого координатор отсутствует. Тогда TLDR и Trpr будут существенно больше среднего времени основной работы процесса, а также значений Т\ и Т2- TLDR, Trpr» Tma,„, Т\, Т2. Таким образом, в текущей процедуре выбора нет необходимости принимать во внимание отсутствие координатора.

Для оценки сложности сообщения рассмотрены три случая: общее состояние, нижняя граница и верхняя граница.

Общее состояние относится к оценке ожидаемого среднего числа сообщений ELT и LDR процедуры выбора за большой отрезок времени. Если координатор отказывает, то в системе остается (N-]) процессов.

Пусть ке - интенсивность, с которой работающие процессы начинает направлять сообщения ELT. В предложенном алгоритме Хе равен интенсивности, с которой сообщения REQ направляются сети, т.е.

Xe=U(Tmol„+T{), (4)

где 1е - интенсивность сообщений ELT входного потока заявок.

Допустим, что после отказа координатора один из оставшихся (Л-1) процессов обнаруживает отсутствие координатора, направляет первое сообщение ELT и начинает отсчет тайм-аута Тг. Назовем этот процесс процессом-инициатором. Далее процедура выбора может перейти в фазу конкуренции - состояние 2 на рис. 3. В этой фазе в процедуре может участвовать (7V-2) процессов и конкурировать с другими, если только они обнаруживают отказ координатора и направляют сообщение ELT в течение временного окна rd. Это период, начинающийся с момента направления первого сообщения ELT в сеть до момента, когда это сообщение достигает всех других (N-2) процессов. Это объясняется тем, что, в соответствии с алгоритмом, процесс не будет инициировать процедуру выбора, если он получает сообщения ELT от других процессов. Итак, коммуникационная сложность алгоритма рассчитывается как сумма первого сообщения ELT, направленного процессом-инициатором, числа г.побшений ELT, направленных N-2 процессами в течение фазы конку-

ренции, и одного сообщения LDR, которое заканчивает процедуру выбора, т.е.

КС = 1 +КСк + 1 = 2 +КСк, (5)

где КСк - число сообщений ELT в течение фазы конкуренции.

Теперь оценим среднее число сообщений в течение фазы конкуренции. Пусть С] указывает на ожидаемое число сообщений в течение интервала tj первого сообщения ELT, направленного сети процессом-инициатором. В соответствии с алгоритмом, если процесс получает сообщение ELT в это время, то он подождет инициировать процедуру выбора, иначе после окончания Тг он будет направлять сообщение LDR в систему. Однако в течение интервала Т2 может поступить несколько сообщений ELT. Поэтому ожидаемое число сообщений ELT в течение интервала Т2 может быть вычислено как

С) = (N-2) Хе td. (6)

Среднее число сообщений ELT в течение фазы конкуренции

КСк = с, —-----(7)

Поставляя (6) в (7) имеем,

КСк = (N-2) Ае rrf-1-. (8)

Верхняя фаница выражения достигается, когда знаменатель выражения (5) имеет минимальное значение, т. е. когда rd максимально, что наблюдается при г</ = TJ2 (из неравенства Т2>2 Td). Следовательно,

КСк (Верхняя граница) = ^

1

11-^/72

ггТ2П

=2С,. (9)

Соответственно, нижняя граница выражения достигается, когда знаменатель имеет максимальное значение, т.е. когда т^ = 0. Следовательно,

КСк (Нижняя граница) = г---1 л = С\. (10)

Наконец, получаем

КС = 7+ (И)

(Т,+Тташ)(\-т,/Тг) ■

Выражение (11) определяет ожидаемое число сообщений ЕЬТ и 1£>Я на одну процедуру выбора. При этом сложность алгоритма равна О (п), что указывает на его эффективную работу.

Далее в главе проведен анализ сценариев работы алгоритма, в которых рассматриваются процедуры ложных выборов в системе с низкой и высокой загрузкой координатора, а также в перегруженной системе. Разработана реализация блока выбора координатора в узле РСОИ и общая схема подсистемы.

В четвертой главе проведено исследование разработанного алгоритма при помощи имитационной модели РСОИ.

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

Имитационные эксперименты были выполнены для трех коэффициентов загрузки координатора: низкой (0,1), средней (0,5) и высокой (0,9).

Различные значения загрузки координатора могут быть получены

как

/> =Я.//£. (12)

В свою очередь,

(13)

л=0

где

р - коэффициент загрузки координатора; ц - интенсивность обслуживания координатора; Хе - долгосрочная эффективная интенсивность поступления запросов к очереди координатора; N - общее количество процессов в группе; р„ - вероятность наличия п запросов в системе.

Из (12) и модели узла РСОИ (рис. 4) получаем следующее выражение, позволяющее оценить загрузку координатора в зависимости от экспериментальных результатов:

си)

где Т\у, - коэффициент использования перехода Гц в ¡-ом узле РСОИ. Величина коммуникационной сложности КС алгоритма выбора координатора равна

n с , о

кс = Z о ' (15)

¿=1 503/

где 592„ 595/, 55оз; (рис. 4) - число фишек, поступивших в позиции S92, S95,5*503 в ¿-ом узле РСОИ.

Правильная установка значений времени тайм-аутов 7\ и Гг является критической для надлежащего функционирования алгоритма. На основе времени доставки сообщений в модели коммуникационной подсистемы и с учетом (1), в имитационных экспериментах были установлены следующие значения параметров: Tf= 400 мс, Т2 = 500 мс, TLDR = 5000 мс, Trpr = 10000 мс, Tserv = 20 мс.

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

Результаты моделирования, приведенные на рис. 5, показывают, что коммуникационная сложность алгоритма медленно увеличивается с ростом количества процессов и дает стабильную и эффективную работу РСОИ, в том числе и при высокой загрузке координатора. Коммуникационная сложность алгоритма на 15% меньше по сравнению существующими алгоритмами управления координатором для РСОИ с 21 процессом при коэффициенте загрузки координатора 0,9.

Далее в главе проанализировано изменение коммуникационной сложности в зависимости от величины тайм-аута для различных количеств процессов и показано, что результаты имитационного моделирования соответствует аналитической модели.

В конце главы проанализированы различные методы адаптации значений тайм-аутов алгоритма к переменному сетевому трафику.

В частности, подробно рассмотрены методы, основанные на экспоненциальном сглаживании и на нейронных сетях.

л

Рис. 4. Имитационная модель узла РСОЙ

Уровня загрузки координатора

С адаптивного алгоритма С алгоритма забияки

низкая загрузка 0,1 —низкая загрузка 0,1

-»-средняя загрузка 0,5 -»-средняя загрузка 0,5

-у высокая загрузка 0,9 -*- высокая загрузка 0,9

2

О

* 1.8-1-,-,-,-,-,-,-,-,-,-,-,

1 3 5 7 9 11 13 15 17 19 21 23

число процессов

Рис. 5. Зависимость коммуникационной сложности от числа процессов в РСОИ

В заключении диссертации изложены полученные результаты и сформулированы основные выводы.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

2. Разработан адаптивный алгоритм управления координатором для РСОИ в условиях надежной групповой рассылки, обеспечивающий низкий сетевой трафик.

3. Реализована подсистема блока голосования в узле РСОИ с использованием языка программирования С в операционной системе UNIX.

4. Разработаны имитационная и аналитическая модели РСОИ, использующие адаптивный алгоритм выбора координатора для распределенных вычислительных систем в условиях надежной групповой рассылки.

5. Проведенные результаты экспериментов показали, что предложенный алгоритм демонстрируют стабильную и эффективную работу РСОИ, в том числе и при высокой загрузке координатора. Коммуникационная сложность алгоритма на 15% меньше, чем у существующих алгоритмов управления координатором при коэффициенте загрузки координатора 0,9.

Таким образом, предложенный алгоритм управления координатором в РСОИ позволяет снизить сетевой трафик, повысить быстродействие РСОИ.

По теме диссертации опубликованы следующие работы:

1. Сан Ян Наинг У. Исследование протоколов взаимного исключения в распределенных вычислительных системах. // Международная школа-конференция по приоритетному направлению «Информационно-телекоммуникационные системы» с участием молодых ученых, аспирантов и студентов стран-членов СНГ. - М.: МИЭТ, 2005. -С. 36.

2. Сан Ян Наинг У. Исследование распределенных алгоритмов выбора координатора в условиях надежной групповой рассылки. // Материалы XV всероссийской научно-технической конференции "Информационные технологии в науке, проектировании и производстве". -Нижний Новгород, ННИМЦ «Диалог», 2005. -С. 34.

3. Сан Ян Наинг У. Адаптивный алгоритм синхронизации для распределенных вычислительных систем. // 13-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов "Микроэлектроника и информатика- 2006". - М.: МИЭТ, 2006. -С. 172.

4. Сан Ян Наинг У. Исследование нового алгоритма выбора координатора в распределенных вычислительных системах. // Материалы

XVII всероссийской научно-технической конференции "Информационные технологии в науке, проектировании и производстве" - Нижний Новгород, ННИМЦ «Диалог», 2007. -С. 10.

5. Сан Ян Наинг У. Новый адаптивный протокол выбора координатора в условиях надежной групповой рассылки.//14-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов "Микроэлектроника и информатика-2007"- М.: МИЭТ, 2007.-С. 273.

6. Сан Ян Наинг У. Разработка нового синхронизационного протокола выбора координатора для распределенных вычислительных систем. // "Естественные и технические науки". ISSN 1684-2626, № 2, 2007. -С. 202-204.

7. Сан Ян Наинг У. Анализ сценариев работы нового протокола выбора координатора для распределенных вычислительных систем. // Оборонный комплекс - научно-техническому прогрессу России. - М.: ВИМИ, № 4, 2007. -С. 48-50.

8. Сан Ян Наинг У. Исследование нового адаптивного алгоритма голосования в условиях надежной групповой рассылки. //XI Московская международная телекоммуникационная конференция студентов и ученых «Молодежь и наука», Часть 2 -М.: МИФИ, 2008. -С. 91-92.

1. Подписано в печать: .

Заказ № УЗ^Т- Тираж экз. Уч.-изд. п^л • Формат 60x84 1/16 Отпечатано в типографии МИЭТ 124498, Москва, МИЭТ

СПИСОК СОКРАЩЕНИЙ ВВЕДЕНИЕ

1. АНАЛИЗ АЛГОРИТМОВ СИНХРОНИЗАЦИИ В РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

1.1. Характеристики распределенных вычислительных систем

1.1.1. Особенности распределенных вычислительных систем

1.1.2. Классификация распределенных вычислительных систем

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

1.2.1. Особенности алгоритмов синхронизации в распределенных системах

1.2.2. Распределенные алгоритмы взаимного исключения

1.2.3. Распределенные алгоритмы управления координатором

ВЫВОДЫ

2. АНАЛИЗ ПРОБЛЕМ ГРУППОВОЙ РАССЫЛКИ СООБЩЕНИЙ В РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

2.1. Групповая рассылка сообщений и области ее применения

2.1.1. Характеристики групповой рассылки

2.1.2. Надежная групповая рассылка

2.2. Модели и схемы групповой рассылки в распределенных системах

2.2.1. Типы деревьев маршрутизации групповой рассылки

2.2.2. Нахождение оптимального дерева маршрутизации

2.3. Алгоритмы групповой рассылки

2.3.1. Групповая рассылка на канальном уровне

2.3.2. Групповая рассылка на сетевом уровне

ВЫВОДЫ

3. РАЗРАБОТКА АДАПТИВНОГО АЛГОРИТМА УПРАВЛЕНИЯ КООРДИНАТОРОМ ДЛЯ РСОИ С НАДЕЖНОЙ ГРУППОВОЙ РАССЫЛКОЙ

3.1. Описание адаптивного алгоритма управления координатором

3.1.1. Предпосылки и общая характеристика алгоритма

3.1.2. Формальное описание алгоритма

3.1.3. Анализ сложности алгоритма

3.2. Анализ сценариев работы алгоритма

3.3. Ограничения алгоритма

3.4. Реализация подсистемы голосования

3.4.1. Общая схема подсистемы

3.4.2. Реализация блока голосования в узле распределенной системы

ВЫВОДЫ

4. ИССЛЕДОВАНИЕ ХАРАКТЕРИСТИК АДАПТИВНОГО АЛГОРИТМА УПРАВЛЕНИЯ КООРДИНАТОРОМ

4.1. Имитационная модель для исследования адаптивного алгоритма управления координатором

4.1.1. Формальный аппарат имитационного моделирования

4.1.2. Структура имитационной модели

4.1.3. Модель коммуникационной подсистемы

4.1.4. Модель узла распределенной системы

4.2. Результаты имитационных экспериментов

4.2.1. Зависимость коммуникационной сложности от числа процессов

4.2.2. Зависимость коммуникационной сложности от изменений значений таймаутов

4.2.3. Зависимость коммуникационной сложности от числа процессов в адаптивном алгоритме

4.3.Исследование адаптивного алгоритма управления координатором к условиям переменного сетевого трафика

4.3.1. Влияние сетевого трафика на работу алгоритма управления координатором

4.3.2. Методы адаптации, основанные на сглаживании

4.3.3. Методы адаптации, основанные на нейронных сетях

ВЫВОДЫ

Актуальность проблемы

Современное приборостроительное производство представляет собой сложный комплекс с высокими темпами технического прогресса в области теории и практики автоматизации как при управлении подвижными объектами, физическими и технологическими процессами в производстве и научных исследованиях, так и в области интеллектуальной деятельности. Управление такими комплексами, характеризующимися большими объемами разнородной информации, является сложной задачей, решение которой во многом зависит от методов, моделей и алгоритмов обработки и представления информации.

Распределенные системы обработки информации (РСОИ) являются перспективным направлением в области управления производственными комплексами. РСОИ в настоящее время широко используются при проведении научных исследований, проектировании и разработке информационно-управляющих систем и процессов, в процессах дистанционного обучения специалистов и многих других сферах научной и практической деятельности. Постоянное развитие и совершенствование информационных технологий оказывает существенное влияние на все научные и технологические направления, связанные с использованием РСОИ. Эволюция РСОИ все в большей степени определяется их надежностью и устойчивостью, которые обеспечивают, во-первых, расширение круга задач, решаемых с помощью компьютеров, и, во-вторых, повышают уровень обработки информации.

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

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

В целом проблема управления координатором, а также обеспечение взаимного исключения - это классические проблемы распределенных систем. Алгоритм управления координатором предназначен для того, чтобы выбрать один из процессов для выполнения специальной роли координатора. Причем в большинстве случаев не столь важно, какой именно процесс будет выбран. Могут применяться различные алгоритмы, но, если процедура выбора инициирована, то она должна закончиться согласием всех процессов в отношении нового координатора.

Для выполнения задачи координации среди узлов РСОИ, координатор должен функционировать на протяжении всего времени работы этой системы. Однако, в работе компьютерных систем, в том числе в распределенных системах, необходимо учитывать вероятность отказа. Эта вероятность намного выше в распределенной системе большого размера с тысячами одновременно выполняющихся процессов. Очень быстро координатор может стать узким местом в работе системы и действовать как единственный пункт отказа.

Теоретическим исследованиям и разработке фундаментальных основ РСОИ, созданию математического аппарата, моделей и методов обработки и управления координатором посвящены труды видных ученых Н. Garsia-Molina, G. Singh, S. Olariu, A. Nakano и многих других.

Большинство существующих алгоритмов выбора координатора в РСОИ основано на индивидуальной передаче сообщений между процессами. Однако, этой схеме работы алгоритмов присущ ряд недостатков. Во-первых, участвующие процессы должны располагать подробной информацией об адресах других процессов. Во-вторых, эта схема усложняет обработку изменений в размере группы процессов и существенно увеличивает трафик в сети.

Существует три критерия эффективности распределенных' алгоритмов: среднее число сообщений, посланных в течение выполнения алгоритма, или коммуникационная сложность; средняя продолжительность алгоритма, или временная сложность; размер сообщений, посылаемых алгоритмом, или емкостная сложность. При этом коммуникационная сложность является определяющим фактором при оценке эффективности алгоритмов для РСОИ. В распределенных алгоритмах все факторы необходимо минимизировать, при этом алгоритмы должны быть масштабируемыми, т.е. легко адаптируемы в широком диапазоне размеров распределенных систем.

В последнее время было разработано много алгоритмов и методов, минимизирующих коммуникационную сложность. Однако ни один из алгоритмов не обеспечивает сложность лучше, чем 0(n log п), где п - число процессов. Таким образом, актуальными являются разработка и исследование адаптивного алгоритма управления координатором в РСОИ, который учитывает переменный сетевой трафик и является более эффективным, чем существующие алгоритмы.

Цели и задачи диссертационной работы

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

Поставленная цель определяет следующие основные задачи диссертационной работы:

1. Анализ принципов надежной групповой рассылки сообщений в РСОИ.

2. Разработка алгоритма управления координатором для РСОИ в условиях надежной групповой рассылки.

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

4. Адаптация алгоритма управления координатором к условиям переменного сетевого трафика.

Методы исследования

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

Научная новизна

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

1. Разработан адаптивный алгоритм управления координатором в РСОИ при использовании механизма надежной групповой рассылки, что значительно упрощает протокол, так как у членов группы нет необходимости знать адреса друг друга для отправки сообщений и делать реконфигурации группы при изменении ее размера; а так же снижает сетевой трафик, так как алгоритм предусматривает участие в выборе координатора только ограниченного количества процессов, и все сообщения передаются в режиме групповой рассылки.

2. Разработано формализованное описание и аналитическая модель подсистемы выбора координатора и проведен анализ сценариев работы алгоритма для его проверки.

3. Осуществлена программная реализация алгоритма управления координатором, внедрение которого практически подтвердило повышение быстродействия РСОИ.

4. Разработана имитационная модель подсистемы выбора координатора в терминах расширенных сетей Петри при помощи программного средства моделирования Winsim. Результаты работы имитационной модели подтверждают, что разработанный алгоритм обеспечивает уменьшение коммуникационной сложности на 15% для РСОИ с 21 процессом при коэффициенте загрузки координатора 0,9. Сравнение результатов имитационного моделирования и аналитической модели показало их хорошее совпадение.

5. Проведен анализ динамики изменения коммуникационной сложности в зависимости от тайм-аутов для разного количества процессов.

Достоверность научных результатов

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

Практическая значимость

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

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

Представляется перспективным применение адаптивного алгоритма в транспортной отрасли для организации бесперебойного обмена данными между единицами транспорта, в логистике для организации управления складами и их охраны, в метеорологии для организации беспрерывного сбора, анализа метеоинформации и радиовещания.

Личный вклад автора

Все основные результаты диссертационной работы получены лично автором, в частности:

1. На основе аналитического обзора средств и методов анализа алгоритмов показана актуальность разработки алгоритмов выбора координатора.

2. Проведена классификация существующих алгоритмов выбора координатора.

3. Разработан и исследован адаптивный алгоритм управления координатора в РСОИ, имеющий меньшую коммуникационную сложность, чем существующие алгоритмы, и адаптирующийся к условиям переменного сетевого трафика.

4. Разработано формализованное описание и математическая модель подсистемы выбора координатора на основе адаптивного алгоритма.

5. Разработана имитационная модель РСОИ для выбора координатора в терминах расширенных сетей Петри при помощи программного средства моделирования Winsim.

6. Реализована подсистема выбора координатора для РСОИ с использованием языка программирования С в ОС UNIX.

7. Проведен анализ динамики изменения коммуникационной сложности алгоритма в зависимости от длительности тайм-аутов для разного количества процессов.

Внедрение результатов работы

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

В ходе проведенных исследований получены и выносятся на защиту следующие основные научные результаты:

1. Адаптивный алгоритм управления координатором в РСОИ в условиях надежной групповой рассылки, обеспечивающий низкий сетевой трафик.

2. Формализованное описание, аналитическая и имитационная модель подсистемы выбора координатора для РСОИ, использующие адаптивный алгоритм управления координатором для РСОИ в условиях надежной групповой рассылки.

3. Программная реализация блока голосования в узле РСОИ с использованием языка программирования С в операционной системе UNIX.

4. Результаты внедрения, экспериментальных исследований и апробация материалов диссертационной работы.

Апробация работы и публикации

Положения данной диссертации докладывались и обсуждались на следующих конференциях:

1. Международная школа-конференция (по приоритетному направлению «Информационно-телекоммуникационные системы» с участием молодых ученых, аспирантов и студентов стран-членов СНГ) - Москва, МИЭТ, 2005.

2. 13-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов "Микроэлектроника и информатика - 2006" -Москва, МИЭТ, 2006.

3. 14-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов "Микроэлектроника и информатика - 2007" -Москва, МИЭТ, 2007.

4. XI Московская международная телекоммуникационная конференция студентов и ученых «Молодежь и наука» - Москва, МИФИ, 2008.

По результатам проведенных научных исследований опубликовано 8 печатных работ без соавторов, в том числе одна работа - в издании, входящем в перечень ВАК.

Структура и объем диссертации

Диссертация состоит из введения, четырех глав, заключения, библиографического списка из 77 наименований и приложения (включающего 5

ВЫВОДЫ

В данной главе описана структура имитационной модели подсистемы выбора координатора РСОИ, а также модели коммуникационной подсистемы и узла распределенной системы. С помощью созданной модели были проведены имитационные эксперименты, результаты которых, в частности, позволили определить зависимость коммуникационной сложности как от изменений значений тайм-аутов, так и от числа процессов, в том числе, от количества процессов в адаптивном алгоритме. Было проведено подробное изучение влияния трафика на работу распределенного алгоритма голосования, детально рассмотрены различные методы адаптации. На основе анализа полученных в процессе изучения результатов была осуществлена адаптация распределенного алгоритма голосования к условиям переменного трафика с использованием метода экспоненциального сглаживания.

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

ЗАКЛЮЧЕНИЕ

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

Надежная групповая рассылка является важной темой исследования в организации вычислительных сетей. В работе изучены проблемы групповой рассылки сообщений и выявлено, что основной проблемой в этой области является построение оптимального дерева маршрутизации для групповой рассылки.

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

Важно, что алгоритму не требуется делать никакой реконфигурации, когда к системе присоединяется новый процесс, или процесс оставляет систему. Система также быстро восстановится, когда текущий лидер отказывает, поскольку все процессы имеют достаточно информации о последнем состоянии системы.

Таким образом, предложенный алгоритм позволяет снизить коммуникационную сложность алгоритма, повысить быстродействие РСОИ, улучшить качество программного обеспечения. В работе показано, что даже при современной технологии организации сетей, предложенный протокол распределенного голосования может быть вполне реализован для использования в больших группах компьютеров, взаимодействующих при помощи локальной вычислительной сети.

1. Олифер В.Г., Олифер Н.А. Сетевые операционные системы СПб.: Издательство "Питер", 2005. - 539 с.

2. Coulouris G., Dollimore J., Kindberg Т. Distributed Systems: Concepts and Design, 3rd ed. Addison-Wesley, 2001. - 644 p.

3. Новиков Ю.В., Кондратенко С.В. Локальные сети: архитектура, алгоритмы, проектирование. М.: ЭКОМ, 2000. - 312 с.

4. The ACM Computing Classification System. Http://www.acm.org

5. Flynn M.J. Some Computer Organizations and their Effectivness // IEEE Trans, on Computers, 1972, vol. 21, No. 9, p. 948 960.

6. Таненбаум Э., ван Стеен M. Распределенные системы. Принципы и парадигмы. СПб.: Питер, 2003. - 877 с.

7. Enslow Р.Н. What is a Distributed Data Processing Systems // Computer, 1978, vol. 11, No. l,pp. 13-21.

8. Столлингс В. Операционные системы. М.: Издательский дом "Вильяме", 2004. - 848 с.

9. Lamport L. Time, clocks and ordering of events in a distributed system // Communications of the ACM, 1978, vol.21, pp. 568 564.

10. Helary J.-M., Mostefaoui A., Raynal M. A General Scheme for Token- and Tree-Based Distributed Mutual Exclusion Algorithms // IEEE Trans, on Parallel and Distributed Systems, 1994, vol. 5, No. 11, pp. 1185 1994.

11. Ricart G, Agrawala A.K. An Optimal Algorithm for Mutual Exclusion in Computer Networks // Communications of the ACM, 1981, vol. 24, pp. 9 -17.

12. Maekawa M. A VN Algorithm for Mutual Exclusion in Decentralized Systems // ACM Trans, on Computer Systems, 1985, vol. 3, No. 2, pp. 145 -159.

13. Naimi M., Trehel M., Arnold A. A Log(N) Distributed Mutual Exclusion Algorithm Based On the Path Reversal // Journal of Parallel and Distributed Comput-ing, 1996, vol. 34, pp. 1 13.

14. Suzuki I., Kasami T. A Distributed Mutual Exclusion Algorithm //ACM Trans, on Computer Systems, 1985, vol.3, No. 4, pp. 344 349.

15. Garcia-Molina H. Elections in a Distributed Computing System // IEEE Trans, on Computers, 1982, vol. 31, No.l, pp. 47-59.

16. Nakano K., Olariu S. Uniform Leader Election Protocols for Radio Networks // IEEE Trans, on Parallel and Distributed Systems, 2002, vol. 03, pp. 516 526.

17. Nakano K., Olariu S. A Survey on Leader Election Protocols for Radio Networks // International Symposium on Parallel Architectures Algorithms and Networks (ISPAN *02), May 2002, pp. 71.

18. Koji Nakano, Stephan Olariu. Randomized Leader Election Protocols in Radio Networks with No Collision Detection // Proceedings of the 11th International Conference on Algorithms and Computation, December 18-20, 2000, p. 362373.

19. Fredrickson N., Lynch N. Electing a leader in an asynchronous ring // Journal of the ACM, January 1987, vol.34, pp. 98-115.

20. Huang Y., McKinley P.K. Group leader election under link-state routing // International Conference on Network Protocols (ICNP '97) , October 1997, pp. 95-104.

21. Fetzer C., Cristian F. A Highly Available Local Leader Election Service // IEEE Transactions on Software Engineering, September 1999, Vol. 25, № 5, pp. 603-618.

22. Steve Chien, Chung-chieh Shan. Hierarchical Distributed Election Protocols // http://www.digitas.harvard.edu/~ken/cs262/election/, May 1997.

23. Scott D. Stoller. Leader Election in Asynchronous Distributed Systems // IEEE Transactions on Computers, March 2000, vol. 49, № 3, pp. 283-284.

24. Yamashita M., Kameda T. Leader Election Problem on Networks in which Processor Identity Numbers Are Not Distinct // IEEE Transactions on Parallel and Distributed Systems, September 1999, Vol. 10, № 9, pp. 878-887.

25. Cristian F., Fetzer C. The Timed Asynchronous Distributed System Model // IEEE Transactions on Parallel and Distributed Systems, June 1999, Vol. 10, No. 6, pp. 642-657.

26. Prasad Jogalekar, Murray Woodside. Evaluating the Scalability of Distributed Systems // IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, June 2000, Vol. 11, № 6, pp. 589.

27. Castorino A., Ciccarella G. Optimal-election algorithms for hypercubes // Proceedings of the Seventh Euromicro Workshop on Parallel and Distributed Processing, PDP *99, 3-5 Feb. 1999, pp. 215 220.

28. Bernard Mans and Nicola Santoro. Optimal Elections in Faulty Loop Networks and Applications // IEEE TRANSACTIONS ON COMPUTERS, March 1998, Vol. 47, № 3, pp. 184.

29. Lynch, Nancy A. Distributed Algorithms, Morgan Kaufmann Publishers, San Mateo, CA 1996. ch.3, 4.1, 15.1, 15.2.

30. Chan M.Y., Chin F.Y.L. Optimal resilient distributed algorithms for ring election // IEEE Transactions on Parallel and Distributed Systems, April 1993, Vol. 4, Issue: 4, pp. 475 480.

31. Itai A., ICutten S., WOLFSTAHL Y., ZAKS S. Optimal Distributed t-Resilient Election in Complete Networks // IEEE Transactions on software Engineering, April 1990, Vol. 16, № 4, pp. 415-420.

32. Koji Nakano, Stephan Olariu, "Uniform Leader Election Protocols for Radio Networks", IEEE Transactions on Parallel and Distributed Systems, May 2002, Vol. 13, №5, pp. 516- 526.

33. Kasera S. К., Bhattacharyya S., Keaton M., Kiwior D., Zabele S., Kurose J., and Towsley D. Scalable Fair Reliable Multicast Using Active Services // IEEE Network, January/February 2000, vol.14, no.l, pp. 48-57.

34. Rahul Shah, Zulfikar Ramzan, Ravi Jain, Raghu Dendukuri, Farooq Anjum. Efficient Dissemination of Personalized Information Using Content-Based Multicast // IEEE Transactions on Mobile Computing, Oct. 2004, vol. 3, № 4, pp. 394-408.

35. Maxemchuk N. F. Reliable multicast with delay guarantees // IEEE Communications Magazine, 2002, Vol. 40, Issue: 9, pp. 96-102.

36. Tushar Deepak Chandra, Sam Toueg. Unreliable failure detectors for reliable distributed systems // Journal of the ACM (JACM), March, 1996, vol. 43, № 2, pp. 225-267.

37. Delporte-Gallet C., Fauconnier H., and Guerraoui R. Shared memory vs. message passing // Technical report, Dec. 2003.

38. Gerla M., Palnati P. Walton S. Multicasting Protocols for High-Speed, Wormhole-Routing Local Area Networks // ACM SIGCOMM'96, Palo Alto, CA, Aug. 1996.

39. Giuseppe Anastasi, Alberto Bartoli. On the Structuring of Reliable Multicast Protocols for Distributed Mobile Systems // The Computer Journal, February 2003, Vol. 46, Issue: 2, pp. 146-160.

40. Kuri J. and Kasera S. K. Reliable Multicast in Multi-Access Wireless LANs // ACM Wireless Networks, 2001. Vol. 7, pp. 359-369.

41. FLOYD S., JACOBSON V., LIU C. G., MCCANNE S., ZHANG L. A reliable multicast framework for light-weight sessions and application level framing // IEEE/ACM Trans. Network. 1997, Vol. 5, Issue: 6, pp. 784-803.

42. PADHYE J., FIROIU V., TOWSLEY D., KRUSOE J. Modeling TCP throughput: A simple model and its empirical validation // In Proceedings of ACM SIGCOMM (Vancouver, Canada), 1998, pp. 303-314.

43. Floyd S., Jacobson V., Liu C., McCanne S., Zhang L. A reliable multicast framework for light-weight sessions and application level framing // IEEE/ACM Trans. Networking, Dec. 1997, vol. 5, pp. 784-803.

44. Baldi M., Ofek Y. Ring versus tree embedding for real-time group multicast // In Proceedings of IEEE INFOCOM 1999, New York, USA, March 1999.

45. Ofek Y., Yener B. Reliable concurrent multicast from busty sources // IEEE J. Select. Areas Communication, Apr. 1997, vol. 14, pp. 434-444.

46. Ferrari D., Banerjea A., Zhang H. Network support for multimedia: A discussion of the tenet approach // Computer Networks & ISDN Systems, 1994, vol. 26, pp. 1267-1280.

47. AHLSWEDE R., CAI N., LI S. Y., YEUNG R. W. Network information flow // IEEE Trans. Inform. Theory. Jul. 2004, vol. 6, pp. 1204-1216.

48. BANERJEE S., BHATTACHARJEE В., KOMMAREDDY C. Scalable application layer multicast // In Proceedings of ACM SIGCOMM, 2002.50.0NLrNE:http://www.personal.kent.edu/~nnuhamma/Algorithms/MyAlgorithm s/GraphAlgor/dijkstraAlgor.htm.

49. Narendra Singhal K., Canhui Ou., Biswannath Mukherjee. Cross-sharing vs. self-sharing terees for protecting multicast sessions in mesh networks // IEEE commu. Magazine, 2006, vol. 50, Issue 2. pp. 206.

50. Bing-Hong Liu, Ming-Jer Tsai, Wei-Chei Ко. Advanced Information Networking and Applications // AINA 19th International Conference, vol. 1, Issue 1, 28-30 March, 2005, pp. 90-95.

51. Winter P. Steiner Problem in Networks: // A Survey Networks, 1987, vol. 17, no. 2, pp. 129-167.

52. Steven Skiena S. The Algorithm Design Manual: Springer, 1997. 510 p.

53. Kay Robbins A., Steven Robbins. UNIX Systems Programming: Communication, Concurrency, and Threads: Prentice Hall PTR, 2003. 912 p.

54. Deering S. E., Estrin D., Farinacci D., Jacobson V., Liu C., Wei L. The PIM Architecture for Wide-Area Multicast Routing // IEEE/ACM Transactions on Networking, Apr. 1996, vol. 4, Issue. 2, pp. 153-162.

55. Deering S. Host extensions for IP multicasting. STD 5, RFC 1112, August 1989.

56. Yeo C., Lee В., and Er M. H. A survey of application level multicast technique // Computer Communication, 2004, vol. 27, Issue. 15.

57. Francis Yoid P. Extending the Internet multicast architecture. // Technical report, ICIR, http://www.icir.org/yoid/docs/yoidArch.ps, April, 2000.

58. Atwood L W. Classification of Reliable Multicast Protocols. // IEEE Net. May-June 2004, vol. 13, № 3, pp. 24-34.

59. Li X., Ammar M., Paul S. Video Multicast over the Internet. // IEEE Network Magazine, April, 1999.

60. Deering S. et al. Multicast Listener Discovery(MLD) for IPv6. IETF RFC 2710, Oct. 1999.

61. Held G., Enhancing Local Area Network Performance: fourth Edition: Auerbach Publication, 2004, 480 p.

62. Richard Stevens W., Bill Fenner, Andrew Rudoff M. UNIX Network Programming Volume 1, Third Edition: The Sockets Networking API, Addison Wesley, Nov. 2003, 1024 p.65. ONLINE: www.knoppix.net

63. ONLINE: https://www.redhat.com/apps/download/

64. ONLINE: http://www.slackware.com/

65. W. Richard Stevens, Stephen A. Rago, "Advanced Programming in the UNIX® Environment: Second Edition", Addison Wesley Professional, June 2005.

66. ONLINE: http://www.daimi.au.dk/PetriNets/tools/complete db.html (2003)

67. Simulation System Winsim Based on Extended Petri Nets: User Manual.

68. A.E. Kostin, "Models and Algorithms for Organization of Distributed Data Processing in Information Systems", Diss. D.Sc., Moscow Institute of Electronic Technology (Technical University), 1989 (in Russian).

69. Hadzilacos V., Tueg S. A Modular Approach to Fault-Tolerant Broadcasts and Related Problems // Technical Report TR94-1425, Dept. of Computer Science, Cornell Univ., May 1994.

70. Mah B. An empirical model of HTTP network traffic // In Proc. IEEE INFOCOM, Apr. 1997, vol. 2, pp. 592-600.

71. Монахова E., Нейрохирурги с Ордынки: PC Week/RE, № 9, 1995.

72. Ф.Уоссермен. Нейрокомпьютерная техника, М.: Мир, 1992.

73. Руковская Д., Пилиньский., Рутковский Л. Нейронные сети, генетические алгоритм и нечеткие системы: Пер. с польск. И. Д. Рудинского. М.: Горячая линия - Телеком, 2006. - 452 с.

74. Richard P. Lippmann. An Introduction to Computing with Neural Nets // IEEE Acoustics, Speech, and Signal Processing Magazine, April 1987.