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

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

2-е издание, исправленное

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

Национальный Открытый Университет “ИНТУИТ”
2016

2

Распределенные системы и алгоритмы/ А.И. Миков, Е.Б. Замятина - М.: Национальный Открытый
Университет “ИНТУИТ”, 2016

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

(c) ООО “ИНТУИТ.РУ”, 2008-2016
(c) Миков А.И., Замятина Е.Б., 2008-2016

3

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

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

Под системой понимается множество элементов и связей между ними. Обозначим V –
множество элементов системы. Тогда бинарное отношение 
 задает наличие

попарных связей между элементами. Если для некоторых элементов 
 и 

пара 
, то в системе существует связь от x к y. Если 
, то такой связи

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

В системе могут быть не только попарные связи, но и связи троек элементов. Такие
связи описываются тернарными отношениями 
. Например, связь

“ребенок и его родители” – связь трех элементов.

В общем случае в системе могут быть также связи, задаваемые отношениями 

. Здесь n – количество элементов в системе.

С каждым отношением связан определенный смысл, выражаемый высказыванием,
например, “x следует за y”, “x посылает сигнал y”, “x – ребенок y и z” и т.д. Иначе
говоря, вместо отношений (или вместе с отношениями) удобно рассматривать
соответствующие предикаты P2, P3, P4,…, Pn. В дополнение к перечисленным
рассматривают и предикаты P1, которые можно интерпретировать как выражение
свойств элементов множества V.

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

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

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

4

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

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

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

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

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

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

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

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

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

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

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

5

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

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

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

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

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

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

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

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

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

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

6

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

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

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

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

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

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

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

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

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

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

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

7

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

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

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

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

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

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

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

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

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

8

время Индия стала одной из таких стран. Программный продукт при этом
выпускается не с маркой “made in India”, а под маркой корпорации – заказчика.

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

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

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

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

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

Множество элементов в каждой из систем, обычно, можно разделить на два
подмножества, 
. Множества, обозначенные буквой

U, состоят из сосредоточенных элементов, занимающих относительно небольшой
объем пространства и реализующих некоторую функцию преобразования. Множества,
обозначенные буквой W, состоят из элементов, связывающих некоторые
сосредоточенные элементы между собой. Их основная задача не преобразование, а
передача чего-либо в системе от одного элемента к другому. Например,
сосредоточенными элементами могут быть два компьютера, осуществляющих
вычисления по некоторым алгоритмам. Связывающим элементом может быть кабель,
один конец которого подсоединен к первому компьютеру, а второй конец – ко второму
компьютеру.

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

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

Примером является передача сигналов посредством радиосвязи на сверхвысоких

9

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

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

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

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

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

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

местоположение;

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

системы;

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

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

Рассмотрим две системы, S1 и S2. Первая система функционирует для достижения
некоторой цели G1. При этом в любой момент времени имеется некоторая степень
достижения этой цели. Вторая система функционирует для того, чтобы ускорить

10