p - не лист. p получил в C сообщение от своего родителя и через все листовые ребра. По индукции, C содержит fp¢ для каждой дочерней вершины p¢ вершины p, и, т.к. ¡ - конечная конфигурация, C также содержит gp¢. Следовательно, посылка <tok> родителю p была возможна, и, т.к. ¡ - конечная конфигурация, это произошло. Tp состоит из объединения Tp¢ по всем дочерним вершинам p и из самого p. С помощью индукции можно показать, что в каждом процессе этого множества существует событие, предшествующее gp.
Отсюда следует, также, что p0 получил сообщение от каждого соседа и выполнил событие decide, которому предшествуют события в каждом процессе.
Остовное дерево, которое строится в вычислении Алгоритма 6.5, иногда используют в последовательно выполняемых алгоритмах. (Например, алгоритм Мерлина-Сегалла (Merlin-Segall) для вычисления таблиц кратчайших маршрутов предполагает, что изначально дано остовное дерево с корнем в v0; см. Подраздел 4.2.3. Начальное остовное дерево может быть вычислено с использованием эхо-алгоритма). В последней конфигурации алгоритма каждый процесс (кроме p0) запомнил, какой сосед в дереве является его родителем, но не запомнил дочерних вершин. В алгоритме одинаковые сообщения принимаются от родителя, через листовые ребра, и от дочерних вершин. Если требуется знание дочерних вершин в дереве, алгоритм может быть слегка изменен, так чтобы отправлять родителю сообщения, отличные от остальных (в последней операции отправления сообщения для не-инициаторов). Дочерними вершинами процесса тогда являются те соседи, от которых были получены эти сообщения.
6.2.4 Алгоритм опроса
В сетях с топологией клика между каждой парой процессов существует канал. Процесс может определить, получил ли он сообщение от каждого соседа. В алгоритме опроса, обозначенном как Алгоритм 6.6, инициатор запрашивает у каждого соседа ответ на сообщение и принимает решение после получения всех ответных сообщений.
Теорема 6.18 Алгоритм опроса (Алгоритм 6.6) является волновым алгоритмом.
Доказательство. Алгоритм пересылает по два сообщения через каждый канал, смежный с инициатором. Каждый сосед инициатора отвечает только один раз на первоначальный опрос, следовательно, инициатор получает N-1 ответ. Этого достаточно, чтобы принять решение, следовательно, инициатор принимает решение и ему предшествует событие в каждом процессе.
Опрос может быть использован и в сети с топологией звезда, в которой инициатор находится в центре.
var recp : integer init 0 ; (* только для инициатора *)
Для инициатора:
begin forall q Î Neighp do send <tok> to q ;
while recp < # Neighp do
begin receive <tok> ; recp := recp + 1 end ;
decide
end ;
Для не-инициатора:
begin receive <tok> from q ; send <tok> to q end
Алгоритм 6.6 Алгоритм опроса.
6.2.5 Фазовый алгоритм
В этом разделе будет представлен фазовый алгоритм, который является децентрализованным алгоритмом для сетей с произвольной топологией. Алгоритм дан в [Tel91b, Раздел 4.2.3]. Алгоритм может использоваться как волновой для ориентированных сетей.
Алгоритм требует, чтобы процессам был известен диаметр сети, обозначенный в тексте алгоритма как D. Алгоритм остается корректным (хотя и менее эффективным), если процессы вместо D используют константу D¢ > D. Таким образом, для применения алгоритма необязательно точно знать диаметр сети; достаточно, если известна верхняя граница диаметра (например, N-1). Все процессы должны использовать одну и ту же константу D¢. Пелег [Peleg; Pel90] дополнил алгоритм таким образом, чтобы диаметр вычислялся во время выполнения, но это расширение требует уникальной идентификации.
Общий случай. Алгоритм может использоваться в ориентированных сетях произвольной топологии, где каналы могут передавать сообщения только в одном направлении. В этом случае, соседи p являются соседями по входу (процессы, которые могут посылать сообщения p) и соседями по выходу (процессы, которым p может посылать сообщения). Соседи по входу p содержатся в множестве Inp, а соседи по выходу - в множестве Outp.
В фазовом алгоритме каждый процесс посылает ровно D сообщений каждому соседу по выходу. Только после того, как i сообщений было получено от каждого соседа по входу, (i+1)-ое сообщение посылается каждому соседу по выходу; см. алгоритм 6.7.
cons D : integer = диаметр сети ;
var recp[q] : 0..D init 0, для каждого q Î Inp ;
(* Количество сообщений, полученных от q *)
Sentp : 0..D init 0 ;
(* Количество сообщений, посланных каждому соседу по выходу *)
begin if p - инициатор then
begin forall r Î Outp do send <tok> to r ;
Sentp := Sentp + 1
while minq Recp[q] < D do
begin receive <tok> (от соседа q0) ;
Recp[q0] := Recp[q0] + 1 ;
if minq Recp[q] ³ Sentp and Sentp < D then
end
Алгоритм 6.7 Фазовый алгоритм.
Действительно, из текста алгоритма очевидно, что через каждый канал проходит не более D сообщений (ниже показано, что через каждый канал проходит не менее D сообщений). Если существует ребро pq, то fpq(i) - i-е событие, в котором p передает сообщение q, а gpq(i) - i-е событие, в котором q получает сообщение от p. Если канал между p и q удовлетворяет дисциплине FIFO, эти события соответствуют друг другу и неравенство fpq(i) p gpq(i) выполняется. Каузальные отношения между fpq(i) и gpq(i) сохраняются и в случае, если канал не является FIFO, что доказывается в следующей лемме.
Лемма 6.19 Неравенство fpq(i) p gpq(i) выполняется, даже если канал не является каналом FIFO.
Доказательство. Определим mh следующим образом: fpq(mh) - событие отправления сообщения, соответствующее gpq(h), т.е. в своем h-м событии получения q получает mh-е сообщение p. Из определения каузальности fpq(mh) p gpq(h).
Т.к. каждое сообщение в C получают только один раз, все mh различны, откуда следует, что хотя бы одно из чисел m1, ..., mi больше или равно i. Выберем j £ i так, чтобы mj ³ i. Тогда fpq(i) p fpq(mj) p gpq(j) p gpq(i).
Теорема 6.20 Фазовый алгоритм (Алгоритм 6.7) является волновым алгоритмом.
Доказательство. Т.к. каждый процесс посылает не более D сообщений по каждому каналу, алгоритм завершается за конечное число шагов. Пусть ¡ - заключительная конфигурация вычисления C алгоритма, и предположим, что в C существует, по крайней мере, один инициатор (их может быть больше).
Чтобы продемонстрировать, что в ¡ каждый процесс принял решение, покажем сначала, что каждый процесс хотя бы один раз послал сообщения. Т.к. в ¡ по каналам не передается ни одно сообщение, для каждого канала qp Recp[q] = Sentpq. Также, т.к. каждый процесс посылает сообщения, как только получит сообщение сам, Recp[q] > 0 Þ Sentp > 0. Из предположения, что существует хотя бы один инициатор p0, для которого Sentp0 > 0, следует, что Sentp > 0 для каждого p.
Впоследствии будет показано, что каждый процесс принял решение. Пусть p - процесс с минимальным значением переменной Sent в ¡, т.е. для всех q Sentq ³ Sentp в ¡. В частности, это выполняется, если q - сосед по входу p, и из Recp[q] = Sentq следует, что minq Recp[q] ³ Sentp. Но отсюда следует, что Sentp = D; иначе p послал бы дополнительные сообщения, когда он получил последнее сообщение. Следовательно, Sentp = D для всех p, и Recp[q] = D для всех qp, откуда действительно следует, что каждый процесс принял решение.
Остается показать, что каждому решению предшествует событие в каждом процессе. Если P = p0, p1, ..., pl (l £ D) - маршрут в сети, тогда, по Лемме 6.19,
для 0 £ i < l и, по алгоритму,
для 0 £ i < l - 1. Следовательно, . Т.к. диаметр сети равен D, для любых q и p существует маршрут q = p0, p1, ..., pl = p длины не более D. Таким образом, для любого q существует l £ D и сосед по входу r процесса p, такие, что ; на основании алгоритма, предшествует dp.
Алгоритм пересылает D сообщений через каждый канал, что приводит в сложности сообщений, равной |E|*D. Однако нужно заметить, что |E| обозначает количество направленных каналов. Если алгоритм используется для неориентированной сети, каждый канал считается за два направленных канала, и сложность сообщений равна 2|E|*D.
var recp : 0..N - 1 init 0 ;
(* Количество полученных сообщений *)
Sentp : 0..1 init 0 ;
(* Количество сообщений, посланных каждому соседу *)
begin forall r Î Neighp do send <tok> to r ;
while Recp < # Neighp do
begin receive <tok> ;
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90
