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

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

Суть его в следующем. Один из сайтов – инициатор посылает маркер 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