Е. Б. Замятина Распределенные системы и алгоритмы Курс лекций

Вид материала

Курс лекций

Содержание V – множество элементов системы. Тогда бинарное отношение R Распределенными системами Примеры распределенных систем. A, ставит задачу проводки платежа из своего банка, находящегося в пункте B Сосредоточенные и распределенные системы Тандемы распределенных систем S2 и/или цель функционирования системы S S1 является распределенной, имеет подразделения в разных городах и странах, то и систему S S1 можно описать как набор S S2 описывается как набор S S2 для имеющейся системы S S1 – конечных пользователей информационной системы S Лекция 2. Распределенные задачи и алгоритмы P. Предположим, что имеется два равноценных (с точки зрения задачи P O1 и сообщить результат объекту O O2 выбирает случайным образом число x Лекция 3. Надежность и безопасность распределенных систем Лекция 4. Пример. Распределенная информационная система организации. Концепции Структура информационного пространства Структура региональной системы образования и предпосылки создания РРИСО ... Полное содержание

Подобный материал:

• Века. Вопросы к семинарам и диспутам. Часть вторая е. И. Замятин. Роман-антиутопия, 78.14kb.
• С. В. Лапина Социология Курс лекций, 2085.17kb.
• Е. В. Беляева Этика Курс лекций, 693.52kb.
• С. В. Лапина Культурология Курс лекций, 3263kb.
• О. В. Свидерская Основы энергосбережения Курс лекций, 2953.76kb.
• С. М. Забелов > П. С. Забелов Административное право Курс лекций, 3268.19kb.
• И. М. Вашко Организация и охрана труда Курс лекций, 2301.17kb.
• И. М. Вашко Организация и охрана труда Курс лекций, 2301.24kb.
• Курс лекций для студентов заочного факультета самара, 1339.16kb.
• Курс, 1-й семестр лекции (51 час), экзамен практикум на ЭВМ (68 часов), зачет (с оценкой), 24.4kb.

А.И.Миков, Е.Б.Замятина

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

Курс лекций


2007

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

Под системой понимается множество элементов и связей между ними. Обозначим V – множество элементов системы. Тогда бинарное отношение R₂  V  V задает наличие попарных связей между элементами. Если для некоторых элементов xV и yV пара (x, y) R₂ , то в системе существует связь от x к y. Если (x, y) R₂ , то такой связи нет. Порядок элементов в паре важен, так как связи могут быть направленными, несимметричными.

В системе могут быть не только попарные связи, но и связи троек элементов. Такие связи описываются тернарными отношениями R₃  V  V  V = V ³. Например, связь «ребенок и его родители» – связь трех элементов.

В общем случае в системе могут быть также связи, задаваемые отношениями R₄ V ⁴ , R₅  V ⁵.,…, R_n  V ⁿ. Здесь n – количество элементов в системе.

С каждым отношением связан определенный смысл, выражаемый высказыванием, например, «x следует за y», «x посылает сигнал y», «x – ребенок y и z» и т.д. Иначе говоря, вместо отношений (или вместе с отношениями) удобно рассматривать соответствующие предикаты P₂ , P₃ , P₄ ,…, P_n . В дополнение к перечисленным рассматривают и предикаты P₁ , которые можно интерпретировать как выражение свойств элементов множества V.

Подчеркнем, что бинарных отношений в системе может быть несколько. Например, в цилиндре двигателя автомобиля газ (бензино-воздушная смесь), загораясь, толкает поршень и, одновременно, нагревает его. Т.е. существует отношение «x толкает y» и отношение «x нагревает y». Ясно, что в зависимости от целей исследования системы одни отношения рассматриваются как существенные, а другие – как второстепенные.

Множественность касается не только бинарных, но и тернарных и других отношений. В общем случае систему можно описать как набор S = {V, {P_{i, j}}}, где индекс i обозначает арность отношения (или количество мест предиката), а индекс j дает возможность различать отношения одной и той же арности.

Некоторые из предикатов P_{1, j} могут характеризовать местоположение элемента системы. Например, его географические координаты, пространственные координаты (спутник связи), нахождение в определенном помещении (компьютер локальной сети) и т.д. Подмножества элементов, имеющих одно и то же (в пределах некоторого допуска, приближения) местоположение, мы будем называть сайтами. Аналогично, некоторые из предикатов P_{2, j} могут характеризовать взаимное расположение элементов, например, расстояние, время передачи сигнала, стоимость переноса информации или вещества от одного элемента системы к другому. Взаимное расположение может быть существенным и для троек элементов, и для четверок и т.д., и выражаться соответствующими предикатами.

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

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

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

Примером непрерывной распределенной системы является стальной лист, нагреваемый в одной точке газовой горелкой. Элементы системы – это «точки» листа с определенными координатами. Каждая точка в некоторый момент времени характеризуется значением температуры, а весь лист описывается некоторым температурным полем. Температуры близко расположенных точек имеют мало отличающиеся друг от друга значения, зависящие от удаленности этих точек от источника тепла. С течением времени значения температур увеличиваются до некоторых пределов, зависящих от температуры горелки, координат точек, величины теплоотдачи листа в окружающее пространство.

Дискретные распределенные системы характеризуются тем, что элементы системы четко «очерчены», отделены друг от друга. Один из видов отношений – бинарное отношение «быть соседними элементами». Между двумя соседними элементами других элементов нет. Это не означает, что между ними нельзя включить какой-либо третий элемент. Но тогда первые два перестают быть соседними.

В дальнейшем рассматриваются в основном дискретные системы.

Примеры распределенных систем.

1. Сеть газопроводов.

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

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

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

2. Электросети.

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

Для управления сетью необходимо знать значения электрического напряжения в различных точках сети, падение напряжения в ЛЭП, значения потребляемого тока. Вся эта информация распределена по сети. По сети распределены также устройства управления участками сети – различные коммутаторы, переключатели, выключатели. Задача управления сетью с точки зрения оптимизации потоков электроэнергии решается централизованно, но иногда она разбивается на подзадачи, решаемые в определенных секторах сети. Например, известные «веерные отключения» при перегрузке сети, перенаправление потоков из одних регионов в другие в соответствии с временем суток и т.д.

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

3. Сети связи.

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

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

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

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

Задача маршрутизации – типичная распределенная задача оптимизационного характера. Она имеет многообразные постановки.

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

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

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

Задача маршрутизации входит как составная часть в более общую задачу управления сетью связи.

4. Логистические системы.

Система перевозки грузов включает транспортные средства (грузовики, поезда, самолеты, корабли), транспортные пути (автомобильные, железные дороги, морские и речные пути и др.), склады, порты, станции, погрузочно-разгрузочные механизмы и проч.

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

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

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

5. Банковская система.

Почти каждый банк самостоятелен. Банковская система распределена по всему Земному шару. Но у всех банков есть общая задача – обслужить клиента, где бы он ни был. Клиент должен иметь возможность получить свои деньги даже там, где о его банке никогда не слышали. Или сделать банковский перевод в далекую страну. Для осуществления этих операций банки связаны между собой системой договоров и поддерживающими эту систему техническими средствами.

Клиент, находящийся в пункте A, ставит задачу проводки платежа из своего банка, находящегося в пункте B, в банк получателя, находящийся в пункте C. При этом получатель, находящийся в пункте D, должен получить уведомление. Это общая задача, которая разделяется банками на части, решаемые в разных местах, т.е. превращается в распределенную задачу.

6. Корпорации.

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

Но есть и совершенно объективные причины создания удаленных подразделений (отделений) корпораций. Прежде всего, это приближение к рынку сбыта продукции. Рынок, по определению, является рассредоточенной системой по большим территориям. Для того чтобы эффективно работать на рынке, корпорация создает региональные отделения. Например, транснациональные корпорации обычно открывают отделения по Западной Европе, Восточной Европе, Африке и Ближнему Востоку, Азии, Америке. При большом рынке происходит еще большее географическое дробление.

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

Например, в некоторых американских исследованиях утверждается, что в США профессия программиста в ближайшие десятилетия будет неперспективной: рост потребности в труде программистов будет отставать от роста потребности в труде многих других специалистов. Он будет отставать даже от среднего (по всем специальностям) роста потребности в специалистах. Причина простая – работа по программированию будет заказываться работникам в других странах. В настоящее время Индия стала одной из таких стран. Программный продукт при этом выпускается не с маркой «made in India», а под маркой корпорации – заказчика.

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


7. Государственное и муниципальное управление.

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

Сосредоточенные и распределенные системы

Во многих случаях термин «распределенная» является альтернативой термину «сосредоточенная». Так бывает, когда существуют (или могут существовать) системы, решающие одинаковые задачи, системы, функционально эквивалентные, но конструктивно различные. Обозначим две такие системы S_d и S_sa (от английских терминов distributed и stand-alone).

Множество элементов в каждой из систем, обычно, можно разделить на два подмножества, V(S_d) = U_d  W_d , V(S_sa) = U_sa  W_sa . Множества, обозначенные буквой U, состоят из сосредоточенных элементов, занимающих относительно небольшой объем пространства и реализующих некоторую функцию преобразования. Множества, обозначенные буквой W, состоят из элементов, связывающих некоторые сосредоточенные элементы между собой. Их основная задача не преобразование, а передача чего-либо в системе от одного элемента к другому. Например, сосредоточенными элементами могут быть два компьютера, осуществляющих вычисления по некоторым алгоритмам. Связывающим элементом может быть кабель, один конец которого подсоединен к первому компьютеру, а второй конец – ко второму компьютеру.

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

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

Примером является передача сигналов посредством радиосвязи на сверхвысоких частотах. При этом эфир становится элементом системы. Поскольку радиоволны распространяются во всех направлениях, то эфир характеризуется тремя пространственными координатами x, y и z. В этих же координатах нужно рассматривать и местоположения сосредоточенных элементов системы, между которыми осуществляется связь. В пространстве могут находиться предметы, непрозрачные для радиоволн (дома, горы и проч.). В этом случае конфигурация эфира становится сложной, из него должны быть «вырезаны» непрозрачные объекты. Как следствие – не все сосредоточенные объекты могут обмениваться сигналами между собой.

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

Таким образом, элементы из множества W_d могут быть весьма разнообразными, с большим количеством характеристик.

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

Множества сосредоточенных элементов U_sa и U_d сосредоточенной и распределенной систем также могут отличаться. В сосредоточенной системе функционирование элементов из U_sa инвариантно их местоположению. В распределенной системе функционирование элементов из U_d в общем случае зависит от их местоположения. Эта зависимость может быть нескольких видов:

1) зависимость от источников информации, имеющих определенное местоположение;

2) зависимость от поставленных задач, которые должны решаться элементами системы;

3) зависимость от параметров среды в различных точках.


Тандемы распределенных систем

Рассмотрим две системы, S₁ и S₂ . Первая система функционирует для достижения некоторой цели G₁ . При этом в любой момент времени имеется некоторая степень достижения этой цели. Вторая система функционирует для того, чтобы ускорить достижение цели первой системой или увеличить степень достижения цели первой системой. Таким образом, система S₁ является основной, а система S₂ – вспомогательной.

Цель G₂ создания системы S₂ и/или цель функционирования системы S₂ является производной от цели G₁ .

Например, S₁ – коммерческая организация (фирма). Ее цель G₁ – поддержание прибыли не менее определенного уровня. Величина прибыли зависит от многих факторов, в том числе от степени информированности руководителей о положении дел. Корпоративная информационная система S₂ обеспечивает руководителей актуальной и детальной информацией о фирме, тем самым, позволяя вырабатывать правильные решения, приводящие к увеличению прибыли.

Таким образом, системы S₁ и S₂ образуют своего рода «тандем», являющийся новой системой – фирмой с корпоративной информационной системой.

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

Как сказано ранее, систему S₁ можно описать как набор S₁ = {V₁ , {P_{i, j}}}, где индекс i обозначает арность отношения (или количество мест предиката), а индекс j дает возможность различать отношения одной и той же арности. Отдельные предикаты P_{1, j} характеризуют местоположение элементов системы. Некоторые из предикатов P_{2, j} характеризуют взаимное расположение элементов.

Соответственно, система S₂ описывается как набор S₂ = {V₂ , {Q_{i, j}}}. Здесь отдельные предикаты Q_{1, j} характеризуют местоположение элементов системы, отдельные предикаты Q_{2, j} характеризуют взаимное расположение элементов системы S₂ .

Множество элементов V₂ «порождается» множеством элементов V₁ . Множества предикатов Q_{1, j} и Q_{2, j} «зависят» от множеств предикатов P_{1, j} и P_{2, j} . В частности, сайты системы S₂ формируются, как правило, на основе сайтов системы S₁ .

За словами «порождается» и «зависят» стоит на самом деле процесс проектирования системы S₂ для имеющейся системы S₁ . Указанные «зависимости» являются, на самом деле, достаточно сложными, неоднозначными. Например, в системе S₁ с точки зрения ее функционирования могут иметь значение конкретные расстояния между элементами, а в информационной системе S₂ для пар элементов важно, являются они взаимно «удаленными» или принадлежат одному сайту. Т.е. это отношение двузначное: «близко», «далеко». Это важно с точки зрения технологии передачи данных. А вот насколько далеко – не имеет значения. Отношение с точки зрения технологии может быть и трехзначным: «близко», «в пределах локальной сети», «в глобальной сети».

С точки зрения работников системы S₁ – конечных пользователей информационной системы S₂ отношение расстояния может вообще отсутствовать: при разработке программного обеспечения требуют «прозрачности» реализации. При прозрачной реализации пользователь не знает, где находятся данные. Он работает так, как будто бы все необходимые ему данные находятся на его локальном сайте.