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

Алгоритм (рутина) узла – инициатора:
routine Initiator
initial
out token;
endi
event;
if message = token then return(OK)
ende
endrout.

routine OtherNode
event;
if message = token then out token;
ende
endrout.

Алгоритм голосования

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

Существо алгоритма заключается в следующем.

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

Легко модифицировать этот алгоритм на случаи голосования по простому большинству, квалифицированному большинству и т.д.

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

System := compl(n)(Node[1..n](P[1..n – 1])).

Здесь у каждого сайта Node[i] имеется набор полюсов P[1..n – 1]. Эти полюсы связаны каналами передачи данных с соответствующими полюсами остальных сайтов. Таким образом, все каналы изолированы друг от друга. Маркер, передаваемый сайтом Node[i] через полюс P[j], попадет только в один канал и, соответственно, только на один сайт.

Рутина сайта – инициатора:

routine Initiator
initial
integer counter;
counter := 0;
out token;
endi
event;
if message = token then 
if (counter = n – 2) then return(OK)
else counter := counter + 1 endi
ende
endrout.

Здесь оператор out token означает передачу маркеров token всем смежным сайтам.

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

routine OtherNode
event;
case of polus
if message = token then out token through polus endi
endc
ende
endrout.

Здесь оператор case of – оператор распознавания входа. Идентификатор polus обозначает полюс, на который пришло сообщение, подобно тому, как само сообщение "скрывается" за идентификатором message. Оператор out token through polus возвращает маркер token через тот полюс сайта, на который пришел этот маркер, т.е. инициатору алгоритма.

Описанный распределенный алгоритм выполняется за время O(n).

Алгоритм "Эхо"

Алгоритм "Эхо" может работать для любой топологии распределенной системы. Как и предыдущий алгоритм, в нем имеется один инициатор.

Алгоритм использует метод прохода по графу, называемый "поиск (или просмотр графа) в ширину", описанный, в частности, в учебнике Л.Н.Королева, А.И.Микова "Информатика. Введение в компьютерные науки" для поиска множества R достижимых вершин из данной вершины start.

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

$$Expand(R): \\ begin \\ if \ Out(R) \ not \ in \ R \ then \\ begin \ Out(R) => \ R; \\ Expand(R) \\ end \\ end;$$

Первый вызов – Expand(Out(start)) ; Предполагается, что $$Out(\varnothing ) = \varnothing , \varnothing \subseteq \varnothing$$.

В алгоритме "Эхо" инициатор посылает маркеры всем своим соседям. Любой сайт s (не инициатор), получивший первый раз маркер от одного из своих соседей (обозначим этого соседа pre ), рассылает маркеры всем соседним сайтам, кроме того, от которого получил маркер. Соседи поступают точно так же. Волна удаляется от инициатора.

Дальнейший процесс рассмотрим на примере дерева. Волна доходит до некоторых из висячих вершин. Висячей вершине отправлять маркер дальше некуда. Тогда она возвращает его той вершине, от которой получила (вот оно "эхо"). Вершины, получившие "эхо" от своих соседей, возвращают маркеры своим вершинам pre. Те, в свою очередь, генерируют "эхо" своим предшественникам. Наконец "эхо" доходит до инициатора. Инициатор, получив "эхо" от всех своих соседей, выполняет процедуру return(OK).

Ниже приведен распределенный алгоритм, состоящий из описаний процесса вычислений для сайта – инициатора и описаний процессов для сайтов – не-нициаторов. В тексте описания процесса тот сайт, на котором этот процесс выполняется (свой сайт), обозначен идентификатором this (в традициях языка Симула-67). Множество Out(this) – это множество сайтов, смежных по выходу с сайтом this, т.е. тех сайтов, на которые с сайта this можно отправить сообщения по однонаправленным или двунаправленным каналам связи. Функция card( ) задает число кардинальности (мощность) множества, являющегося аргументом этой функции. Переменные, встречающиеся в текстах процессов – локальные (по экземпляру для каждого процесса): обмен информацией между процессами происходит только посредством сообщений, разделяемые переменные отсутствуют. Начальные значения счетчиков counter равны 0.

Процесс для инициатора:

$$begin \ for \ u \text{\textordmasculine} \ Out(this) \ do \ out \ token \ to \ u ; \\ while \ counter < card(Out(this)) \ do \\ begin \ receive \ token; \ counter := counter + 1 end ; \\ return(OK) \\ end ;$$

Процессы для не-инициаторов:

$$begin \\ receive \ token \ from \ u ; \\ pre(this) := u ; \ counter := counter + 1 ; \\ for (u \text{\textordmasculine} Out(this))\(u \ne pre(this)) \ do \ out \ token \ to \ u ; \\ while \ counter \ < \ card(Out(this)) \ do \\ begin \ receive \ token; \ counter := counter + 1 \ end ; \\ out \ token \ to \ pre(this) \\ end$$

Фазовый алгоритм

Фазовый алгоритм является децентрализованным алгоритмом для произвольных ориентированных графов. Двунаправленные связи тоже могут присутствовать, но они должны быть заданы парой параллельных встречных однонаправленных каналов (дуг графа). Алгоритм требует, чтобы процессам на сайтах был известен диаметр d графа, либо его оценка сверху.

Переменные в тексте алгоритма имеют следующий смысл.

counterout – счетчик, подсчитывающий количество маркеров token, посланных каждому из соседей по выходу. Если таких соседей у некоторого сайта, например, три, то за каждой единицей счетчика стоит три посланных маркера – по одному на каждого соседа.

counterin – массив счетчиков, по одному счетчику на каждого соседа по входу. Хранит количество маркеров, посланных соседями.

this – сайт, процесс которого исполняет данный алгоритм.

Out() – множество вершин, смежных по выходу.

u – некоторый сайт, передавший маркер.

Функция min, примененная к массиву, выбирает из него минимальный элемент.

$$ var \ counter\_ in: \ array [0..d] \ of \ integer \ init \ 0; \\ counter\_ out: \ integer \ init \ 0 ; \\ \\ begin \ if \ this \ - \ инициатор \ then \\ begin \ for \ r \text{\textordmasculine} \ Out(this) \ do \ out \ token \ to \ r ; \\ counter\_ out := counter\_ out + 1 \\ end; \\ while \ min(counter\_ in) < d \ do \\ begin \ receive \ token \ from \ u ; \\ counter\_ in [u] := counter\_ in [u] + 1 ; \\ if \ (min(counter\_ in) \ge \ counter\_ out) \ (counter\_ out < d) \ then \\ begin \ for \ r \text{\textordmasculine} Out(this) \ do \ out \ token \ to \ r ; \\ counter\_ out := counter\_ out + 1 \\ end \\ end ; \\ return(OK) \\ end$$

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

В фазовом алгоритме каждый процесс посылает ровно d сообщений каждому соседу по выходу. Только после того, как k сообщений было получено от каждого соседа по входу, (k + 1) -ое сообщение посылается каждому соседу по выходу.

Алгоритм Финна

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

Процесс сайта s содержит два множества идентификаторов процессов, Inc(s) и NInc(s). Неформально говоря, n – это множество процессов u таких, что событие в u предшествует последнему произошедшему событию в s, а NInc(s) – множество процессов u таких, что для всех соседей r процесса u событие в r предшествует последнему произошедшему событию в s. Эта зависимость поддерживается следующим образом.

Изначально Inc(s) = {s}, а $$NInc(s) = \varnothing$$. Каждый раз, когда одно из множеств пополняется, процесс s посылает сообщение, включая в него Inc(s) и NInc(s). Когда s получает сообщение, включающее множества Inc(s) и NInc(s), полученные идентификаторы включаются в версии этих множеств в процессе s. Когда s получит сообщения от всех соседей по входу, s включается в NInc(s). Когда два множества становятся равны, s выполняет процедуру return(OK). Из неформального смысла двух множеств следует, что для каждого процесса u такого, что событие в u предшествует некоторому событию e, выполняется следующее: для каждого соседа r процесса u событие в r также предшествует событию e.

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

Распространение информации с обратной связью

Важным применением волновых алгоритмов является случай, когда некоторая информация должна быть передана всем процессам и определенные процессы должны быть оповещены о завершении передачи. Эта задача распространения информации с обратной связью (PIF – propagation of information with feedback) формулируется следующим образом.

Формируется подмножество процессов из тех, кому известно сообщение M (одно и то же для всех процессов), которое должно быть распространено, т.е. все процессы должны принять M. Определенные процессы должны быть оповещены о завершении передачи; т.е. должно быть выполнено специальное событие notify, причем оно может быть выполнено только когда все процессы уже получили сообщение M. Алгоритм должен использовать конечное количество сообщений.

Оповещение в PIF-алгоритме можно рассматривать как событие return(OK).

Любой волновой алгоритм может использоваться как PIF-алгоритм. Действительно, пусть A – волновой алгоритм. Чтобы использовать A как PIF-алгоритм, возьмем в качестве процессов, изначально знающих M, инициаторы A. Информация M добавляется к каждому сообщению A. Это возможно, поскольку по построению стартеры A знают M изначально, а последователи не посылают сообщений, пока не получат хотя бы одно сообщение, т.е. пока не получат M. Событию return(OK) в волне предшествуют события в каждом процессе; следовательно, когда оно происходит, каждый процесс знает M, и событие return(OK) можно считать требуемым событием notify в PIF-алгоритме.

Синхронизация

Волновые алгоритмы могут использоваться для случаев, когда должна быть достигнута глобальная синхронизация процессов. Задача синхронизации формулируется следующим образом. В каждом процессе q должно быть выполнено событие aq, и в некоторых процессах должны быть выполнены события bp, причем все события aq должны быть выполнены по времени раньше, чем будет выполнено какое-либо событие bp. Алгоритм должен использовать конечное количество сообщений.

В алгоритмах синхронизации события bp будут рассматриваться как события return(OK).

Любой волновой алгоритм может использоваться как алгоритм синхронизации. Действительно, пусть A – волновой алгоритм. Чтобы преобразовать A в алгоритм синхронизации, потребуем, чтобы каждый процесс q выполнял aq до того, как q пошлет сообщение в A или примет решение в A. Событие bp происходит после события return(OK) в p.

Вычисление нижней грани

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

Как известно из курса математики, если ( X, <= ) – частичный порядок, то c называют нижней гранью a и b, если c <= a, c <= b, и $$\forall d : ( d \le a \ d \le b \Rightarrow d \le c)$$. Допустим, что X таково, что нижняя грань всегда существует; в этом случае нижняя грань является единственной и обозначается как $$a \wedge b$$. Так как $$\wedge$$ – бинарный оператор, коммутативный и ассоциативный, то операция может быть обобщена на конечные множества: $$inf \{ a_{1}, \dots , a_{k}\} = a_{1} \wedge \dots \wedge a_{k}$$.

Задача вычисления нижней грани в распределенной системе формулируется следующим образом. Каждый процесс на сайте q содержит вход aq , являющийся элементом частично упорядоченного множества X. Потребуем, чтобы определенные процессы вычисляли значение inf {aq} по всем сайтам и чтобы эти процессы знали, когда вычисление завершается. Они записывают результат вычисления в переменную out и после этого не могут изменять ее значение.

Событие write, которое заносит значение в out, рассматривается в алгоритме вычисления нижней грани как событие return(OK).

Любой волновой алгоритм может быть использован для вычисления нижней грани.

Это можно показать следующим образом. Допустим, что дан волновой алгоритм A. Назначим каждому процессу q дополнительную переменную vq , которой придадим начальное значение aq . Во время волны эти переменные переприсваиваются следующим образом. Всякий раз, когда процесс q посылает сообщение, текущее значение vq включается в сообщение. Всякий раз, когда процесс q получает сообщение со значением v, переменной vq присваивается значение $$v_{q} \wedge v$$. Когда в процессе p происходит событие return(OK), текущее значение vp заносится в outp.

Теперь нужно показать, что в результат заносится правильное значение. Обозначим правильный ответ через L, т.е. L = inf {aq}. Для события a в процессе q обозначим через v(a) значение vq сразу после выполнения a. Так как начальное значение vq равно aq , и в течение волны оно только уменьшается, неравенство v(a) <= aq сохраняется для каждого события a в q. Из присваивания v следует, что для событий a и b, a >= b => v(a) >= v(b). Кроме того, так как v всегда вычисляется как нижняя грань двух уже существующих величин, нера венство L <= v выполняется для всех величин в течение волны. Таким образом, если d – событие return(OK) в p, значение v(d) удовлетворяет неравенству L <= v(d) и, так как событию d предшествует хотя бы одно событие в каждом процессе q, v(d) <= aq для всех q. Отсюда следует, что L = v(d).

Известна теорема о нижней грани: Если • – бинарный оператор на множестве X, причем он:

коммутативен, т.е. a • b = b • a,

ассоциативен, т.е. (a • b) • c = a • (b • c),

идемпотентен, т.е. a • a = a,

то существует отношение частичного порядка $$\le$$ на X такое, что • – функция нижней грани.

Среди операторов, удовлетворяющих этим трем критериям – логическая конъюнкция и дизъюнкция, минимум и максимум целых чисел, наибольший общий делитель и наименьшее общее кратное целых чисел, пересечение и объединение множеств. Отсюда следует, что операции , $$\vee,$$ min, max, НОД, НОК, $$\cap$$ и $$\cup$$ над величинами, локальными по отношению к сайтам, могут быть вычислены за одну волну.