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

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

Курс лекций

Содержание

Лекция 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. Государственное и муниципальное управление.

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