Алгоритм для кольцевой архитектуры

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

Суть его в следующем. Один из сайтов – инициатор посылает маркер token своему единственному соседу по выходу (в ориентированном цикле каждый сайт имеет в точности один вход и один выход; выход одного сайта соединен с входом соседнего). Маркер, как правило, не имеет «содержания». Важен лишь факт отсылки маркера или поступления маркера.

Любой сайт (кроме инициатора), получив маркер, тут же отправляет его соседу. Инициатор, получив маркер, завершает процесс. Завершение процесса заключается в том, что сайт не посылает далее маркер, а выполняет некоторую процедуру return (OK) – успешный возврат. Рис. иллюстрирует работу этого алгоритма.

Рис. 22. Перемещение маркера по кольцу

Опишем волновой алгоритм для кольцевой архитектуры, используя языковые средства из лекции 6.

Структура распределенной системы задается формулой

System:= dcycle(n)(Node[1..n]).

В системе имеется n сайтов с именами Node[i]. У каждого сайта имеется один входной полюс и один выходной полюс. Выходной полюс сайта Node[i], i ¹ n, соединен каналом связи с входным полюсом сайта Node[i + 1]. Выходной полюс сайта Node[n] соединен с входным полюсом сайта Node[1].

Алгоритм (рутина) узла – инициатора:

routine Initiator

Initial

out token;

Endi

event;

if message = token then return (OK)

Ende

endrout.

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

Рутины остальных узлов имеют вид:

routine OtherNode

event;

if message = token then out token;

Ende

endrout.

Таким образом «волна», начатая инициатором, заканчивается, когда возвращается к инициатору. Описанный распределенный алгоритм выполняется за время O (n).

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

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