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

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 to r ;

Sentp := Sentp + 1

end ;

while minq Recp[q] < D do

begin receive (от соседа q0) ;

Recp[q0] := Recp[q0] + 1 ;

if minq Recp[q] ? Sentp and Sentp < D then

begin forall r ? Outp do send to r ;

Sentp := Sentp + 1

end

end ;

decide

end

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

Действительно, из текста алгоритма очевидно, что через каждый канал

проходит не более D сообщений (ниже показано, что через каждый канал

проходит не менее D сообщений). Если существует ребро pq, то fpq(i) - i-е

событие, в котором p передает сообщение q, а gpq(i) - i-е событие, в

котором q получает сообщение от p. Если канал между p и q удовлетворяет

дисциплине FIFO, эти события соответствуют друг другу и неравенство

fpq(i) ? gpq(i) выполняется. Каузальные отношения между fpq(i) и gpq(i)

сохраняются и в случае, если канал не является FIFO, что доказывается в

следующей лемме.

Лемма 6.19 Неравенство fpq(i) ? gpq(i) выполняется, даже если канал не

является каналом FIFO.

Доказательство. Определим mh следующим образом: fpq(mh) - событие

отправления сообщения, соответствующее gpq(h), т.е. в своем h-м событии

получения q получает mh-е сообщение p. Из определения каузальности

fpq(mh) ? gpq(h).

Т.к. каждое сообщение в C получают только один раз, все mh различны, откуда

следует, что хотя бы одно из чисел m1, ..., mi больше или равно i. Выберем

j ? i так, чтобы mj ? i. Тогда fpq(i) ? fpq(mj) ? gpq(j) ? 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,

[pic]

для 0 ? i < l и, по алгоритму,

[pic]

для 0 ? i < l - 1. Следовательно, [pic]. Т.к. диаметр сети равен D, для

любых q и p существует маршрут q = p0, p1, ..., pl = p длины не более D.

Таким образом, для любого q существует l ? D и сосед по входу r процесса

p, такие, что [pic]; на основании алгоритма, [pic]предшествует dp.

Алгоритм пересылает D сообщений через каждый канал, что приводит в

сложности сообщений, равной |E|*D. Однако нужно заметить, что |E|

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

неориентированной сети, каждый канал считается за два направленных канала,

и сложность сообщений равна 2|E|*D.

var recp : 0..N - 1 init 0 ;

(* Количество полученных сообщений *)

Sentp : 0..1 init 0 ;

(* Количество сообщений, посланных каждому

соседу *)

begin if p - инициатор then

begin forall r ? Neighp do send to r ;

Sentp := Sentp + 1

end ;

while Recp < # Neighp do

begin receive ;

Recp := Recp + 1 ;

if Sentp = 0 then

begin forall r ? Neighp do send to r ;

Sentp := Sentp + 1

end

end ;

decide

end

Алгоритм 6.8 Фазовый алгоритм для клики.

Фазовый алгоритм для клики. Если сеть имеет топологию клика, ее диаметр

равен 1; в этом случае от каждого соседа должно быть получено ровно одно

сообщение, и для каждого процесса достаточно посчитать общее количество

полученных сообщений вместо того, чтобы считать сообщения от каждого соседа

по входу отдельно; см. Алгоритм 6.8. Сложность сообщений в этом случае

равна N(N-1) и алгоритм использует только O(log N) бит оперативной памяти.

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

Алгоритм Финна [Fin79] - еще один волновой алгоритм, который можно

использовать в ориентированных сетях произвольной топологии. Он не требует

того, чтобы диаметр сети был известен заранее, но подразумевает наличие

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

идентификаторов процессов, что приводит к довольно высокой битовой

сложности алгоритма.

Процесс p содержит два множества идентификаторов процессов, Incp и NIncp.

Неформально говоря, Incp - это множество процессов q таких, что событие в q

предшествует последнему произошедшему событию в p, а NIncp - множество

процессов q таких, что для всех соседей r процесса q событие в r

предшествует последнему произошедшему событию в p. Эта зависимость

поддерживается следующим образом. Изначально Incp = {p}, а NIncp = ?.

Каждый раз, когда одно из множеств пополняется, процесс p посылает

сообщение, включая в него Incp и NIncp. Когда p получает сообщение,

включающее множества Inc и NInc, полученные идентификаторы включаются в

версии этих множеств в процессе p. Когда p получит сообщения от всех

соседей по входу, p включается в NIncp. Когда два множества становятся

равны, p принимает решение; см. Алгоритм 6.9. Из неформального смысла двух

множеств следует, что для каждого процесса q такого, что событие в q

предшествует dp, выполняется следующее: для каждого соседа r процесса q

событие в r также предшествует dp, откуда следует зависимость алгоритма.

В доказательстве корректности демонстрируется, что это выполняется для

каждого p, и что из равенства двух множеств следует, что решению

предшествует событие в каждом процессе.

Теорема 6.21 Алгоритм Финна (Алгоритм 6.9) является волновым алгоритмом.

Доказательство. Заметим, что два множества, поддерживаемые каждым

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

составляет не менее 1 в первом сообщении, посылаемом по каждому каналу, и

не более 2N в последнем сообщении, то общее количество сообщений ограничено

2N*|E|.

Пусть C - вычисление, в котором существует хотя бы один инициатор, и пусть

? - заключительная конфигурация. Можно показать, как в доказательстве

Теоремы 6.20, что если процесс p отправил сообщения хотя бы один раз

(каждому соседу), а q - сосед p по выходу, то q тоже отправил сообщения

хотя бы один раз. Отсюда следует, что каждый процесс переслал хотя бы одно

сообщение (через каждый канал).

var Incp : set of processes init {p} ;

NIncp : set of processes init ? ;

recp[q] : boolean for q ? Inp init false ;

(* признак того, получил ли p сообщение от q *)

begin if p - инициатор then

forall r ? Outp do send to r ;

while Incp ? NIncp do

begin receive from q0 ;

Incp := Incp ? Inc ; NIncp := NIncp ? NInc ;

recp[q0] := true ;

if ?q ? Inp : recp[q] then NIncp := NIncp ? {p} ;

if Incp или NIncp изменились then

forall r ? Outp do send to r

end ;

decide

end

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

Сейчас мы покажем, что в ? каждый процесс принял решение. Во-первых, если

существует ребро pq, то Incp ? Incq в ?. Действительно, после последнего

изменения Incp процесс p посылает сообщение , и после

его получения в q выполняется Incq := Incq ? Incp. Из сильной связности

сети следует, что Incp = Incq для всех p и q. Т.к. выполняется p ? Incp и

каждое множество Inc содержит только идентификаторы процессов, для каждого

p Incp = P.

Во-вторых, подобным же образом может быть показано, что NIncp = Nincq для

любых p и q. Т.к. каждый процесс отправил хотя бы одно сообщение по каждому

каналу, для каждого процесса p выполняется: ? q ? Inp : recp[q], и

следовательно, для каждого p выполняется: p ? NIncp. Множества NInc

содержат только идентификаторы процессов, откуда следует, что NIncp = P для

каждого p. Из Incp = P и NIncp = P следует, что Incp = NIncp,

следовательно, каждый процесс p в ? принял решение.

Теперь нужно показать, что решению dp в процессе p предшествуют события в

каждом процессе. Для события e в процессе p обозначим через Inc(e) (или,

соответственно, NInc(e)) значение Incp (NIncp) сразу после выполнения e

(сравните с доказательством Теоремы 6.12). Следующие два утверждения

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

Утверждение 6.22 Если существует событие e ? Cq : e ? f, то q ? Inc(f).

Доказательство. Как в доказательстве Теоремы 6.12, можно показать, что e ?

f ? Inc(e) ? Inc(f), а при e ? Cq ? q ? Inc(e), что и требовалось доказать.

Утверждение 6.23 Если q ? NInc(f), тогда для всех r ? Inq существует

событие e ? Cr : e ? f.

Доказательство. Пусть aq - внутреннее событие q, в котором впервые в q

выполняется присваивание NIncq := NIncq ? {q}. Событие aq - единственное

событие с q ? NInc(aq), которому не предшествует никакое другое событие a',

удовлетворяющее условию q ? NInc(a'); таким образом, q ? NInc(f) ? aq ? f.

Из алгоритма следует, что для любого r ? Inq существует событие e ? Cr,

предшествующее aq. Отсюда следует результат.

Процесс p принимает решение только когда Incp = NIncp; можно записать, что

Inc(dp) = NInc(dp). В этом случае

p ? Inc(dp) ; и

из q ? Inc(dp) следует, что q ? NInc(dp), откуда следует, что Inq ?

Inc(dp).

Из сильной связности сети следует требуемый результат: Inc(dp) = P.

6.3 Алгоритмы обхода

В этом разделе будет представлен особый класс волновых алгоритмов, а

именно, волновые алгоритмы, в которых все события волны совершенно

упорядочены каузальным отношением, и в котором последнее событие происходит

в том же процессе, где и первое.

Определение 6.24 Алгоритмом обхода называется алгоритм, обладающий

следующими тремя свойствами.

В каждом вычислении один инициатор, который начинает выполнение алгоритма,

посылая ровно одно сообщение.

Процесс, получая сообщение, либо посылает одно сообщение дальше, либо

принимает решение.

Из первых двух свойств следует, что в каждом конечном вычислении решение

принимает ровно один процесс. Говорят, что алгоритм завершается в этом

процессе.

Алгоритм завершается в инициаторе и к тому времени, когда это происходит,

каждый процесс посылает сообщение хотя бы один раз.

В каждой достижимой конфигурации алгоритма обхода либо передается ровно

одно сообщение, либо ровно один процесс получил сообщение и еще не послал

ответное сообщение. С более абстрактной точки зрения, сообщения в

вычислении, взятые вместе, можно рассматривать как единый объект (маркер),

который передается от процесса к процессу и, таким образом, «посещает» все

процессы. В Разделе 7.4 алгоритмы обхода используются для построения

алгоритмов выбора и для этого важно знать не только общее количество

переходов маркера в одной волне, но и сколько переходов необходимо для

того, чтобы посетить первые x процессов.

Определение 6.25 Алгоритм называется алгоритмом f-обхода (для класса

сетей), если

он является алгоритмом обхода (для этого класса); и

в каждом вычислении после f(x) переходов маркера посещено не менее min (N,

x+1) процессов.

Кольцевой алгоритм (Алгоритм 6.2) является алгоритмом обхода, и, поскольку

x+1 процесс получил маркер после x шагов (для x < N), а все процессы

получат его после N шагов, это алгоритм x-обхода для кольцевой сети.

6.3.1 Обход клик

Клику можно обойти путем последовательного опроса; алгоритм очень похож на

Алгоритм 6.6, но за один раз опрашивается только один сосед инициатора.

Только когда получен ответ от одного соседа, опрашивается следующий; см.

Алгоритм 6.10.

var recp : integer init 0 ; (* только для инициатора *)

Для инициатора:

(* обозначим Neighp = {q1, q2, .., qN-1} *)

begin while recp < # Neighp do

begin send to qrecp+1 ;

receive ; recp := recp + 1

end ;

decide

end

Для не-инициатора:

begin receive from q ; send to q end

Алгоритм 6.10 Последовательный алгоритм опроса.

Теорема 6.26 Последовательный алгоритм опроса (Алгоритм 6.10) является

алгоритмом 2x-обхода для клик.

Доказательство. Легко заметить, что к тому времени, когда алгоритм

завершается, каждый процесс послал инициатору ответ. (2x-1)-е сообщение -

это опрос для qx, а (2x)-е - это его ответ. Следовательно, когда было

передано 2x сообщений, был посещен x+1 процесс p, q1, ..., qx.

6.3.2 Обход торов

Тором nЧn называется граф G = (V,E), где

V = Zn Ч Zn = { (i, j) : 0 ? i, j < n} и

E = {(i, j)(i', j') : (i = i' & j = j' ±1) ? (i = i' ±1 & j = j')

};

см. Раздел B.2.4. (Сложение и вычитание здесь по модулю n.) Предполагается,

что тор обладает чувством направления (см. Раздел B.3), т.е. в вершине

(i, j) канал к (i, j+1) имеет метку Up, канал к (i, j-1) - метку Down,

канал к (i+1, j) - метку Right, и канал к (i-1, j) - метку Left.

Координатная пара (i, j) удобна для определения топологии сети и ее чувства

направления, но мы предполагаем, что процессы не знают этих координат;

топологическое знание ограничено метками каналов.

Для инициатора (выполняется один раз):

send to Up

Для каждого процесса при получении маркера :

begin if k=n2 then decide

else if n|k then send to Up

else send to Right

end

Алгоритм 6.11 Алгоритм обхода для торов.

Тор является Гамильтоновым графом, т.е. в торе (произвольного размера)

существует Гамильтонов цикл и маркер передается по циклу с использованием

Алгоритма 6.11. После k-го перехода маркера он пересылается вверх, если n|k

(k делится на n), иначе он передается направо.

Теорема 6.27 Алгоритм для тора (Алгоритм 6.11) является алгоритмом x-

обхода для торов.

Доказательство. Как легко заметить из алгоритма, решение принимается после

того, как маркер был передан n2 раз. Если маркер переходит от процесса p к

процессу q с помощью U переходов вверх и R переходов вправо, то p = q тогда

и только тогда, когда (n|U & n|R). Обозначим через p0 инициатор, а через pk

- процесс, который получает маркер .

Из n2 переходов маркера n - переходы вверх, а оставшиеся n2-n - переходы

вправо. Т.к. и n, и n2-n кратны n, то pn2 = p0, следовательно, алгоритм

завершается в инициаторе.

Далее будет показано, что все процессы с p0 по pn2 -1 различны; т.к. всего

n2 процессов, то отсюда следует, что каждый процесс был пройден.

Предположим, что pa = pb для 0 ? a < b < n2. Между pa и pb маркер сделал

несколько переходов вверх и вправо, и т.к. pa = pb, количество переходов

кратно n. Изучив алгоритм, можно увидеть, что отсюда следует, что

# k кратно n, и

# k : a ? k < b & n не кратно n.

Размеры двух множеств в сумме составляют b-a, откуда следует, что n|(b-a).

Обозначим (b-a) = l*n, тогда множество {k: a ? k < b} содержит l кратных n.

Отсюда следует, что n|l, а значит n2|(b-a), что приводит к противоречию.

Т.к. все процессы с p0 по pn2 -1 различны, после x переходов маркера будет

посещен x+1 процесс.

6.3.3 Обход гиперкубов

N-мерным гиперкубом называется граф G = (V,E), где

V = { (b0,...,bn-1) : bi = 0, 1} и

E = { (b0,...,bn-1),(c0,...,cn-1) : b и c отличаются на 1 бит};

см. Подраздел B.2.5. Предполагается, что гиперкуб обладает чувством

направления (см. Раздел B.3), т.е. канал между вершинами b и c, где b и c

различаются битом с номером i, помечается «i» в обеих вершинах.

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

знание ограничено метками каналов.

Как и тор, гиперкуб является Гамильтоновым графом, и Гамильтонов цикл

обходится с использованием Алгоритма 6.12. Доказательство корректности

алгоритма похоже на доказательство для Алгоритма 6.11.

Для инициатора (выполняется один раз):

send по каналу n -1

Для каждого процесса при получении маркера :

begin if k=2n then decide

else begin пусть l - наибольший номер : 2l|k ;

send по каналу l

end

end

Алгоритм 6.12 Алгоритм обхода для гиперкубов.

Теорема 6.28 Алгоритм для гиперкуба (Алгоритм 6.12) является алгоритмом x-

обхода для гиперкуба.

Доказательство. Из алгоритма видно, что решение принимается после 2n

пересылок маркера. Пусть p0 - инициатор, а pk - процесс, который получает

маркер . Для любого k < 2n, обозначения pk и pk+1 отличаются на 1

бит, индекс которого обозначим как l(k), удовлетворяющий следующему

условию:

[pic]

Т.к. для любого i < n существует равное количество k ? {0, ..., 2n} с

l(k) = i, то p0 = p2n и решение принимается в инициаторе. Аналогично

доказательству Теоремы 6.27, можно показать, что из pa = pb следует, что

2n|(b-a), откуда следует, что все p0, ..., p2n-1 различны.

Из всего этого следует, что, когда происходит завершение, все процессы

пройдены, и после x переходов маркера будет посещен x+1 процесс.

6.3.4 Обход связных сетей

Алгоритм обхода для произвольных связных сетей был дан Тарри в 1895 [Tarry;

T1895]. Алгоритм сформулирован в следующих двух правилах; см. Алгоритм

6.13.

R1. Процесс никогда не передает маркер дважды по одному и тому же каналу.

R2. Не-инициатор передает маркер своему родителю (соседу, от которого он

впервые получил маркер), только если невозможна передача по другим каналам,

в соответствии с правилом R1.

var usedp[q] : boolean init false для всех q ? Neighp ;

(* Признак того, отправил ли p сообщение q *)

fatherp : process init udef ;

Для инициатора (выполняется один раз):

begin fatherp := p ; выбор q ? Neighp ;

usedp[q] := true ; send to q ;

end

Для каждого процесса при получении от q0:

begin if fatherp = udef then fatherp := q0 ;

if ?q ? Neighp : usedp[q]

then decide

else if ?q ? Neighp : (q ? fatherp & ¬usedp[q])

then begin выбор q ? Neighp \ {fatherp} с ¬usedp[q] ;

usedp[q] := true ; send to q

end

else begin usedp[fatherp] := true ;

send to fatherp

end

end

Алгоритм 6.13 Алгоритм обхода Тарри.

Теорема 6.29 Алгоритм Тарри (Алгоритм 6.13) является алгоритмом обхода.

Доказательство. Т.к. маркер передается не более одного раза в обоих

направлениях через каждый канал, всего он передается не более 2|E| раз до

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

канал не более одного раза, то каждый процесс получает маркер через каждый

канал не более одного раза. Каждый раз, когда маркер захватывается не-

инициатором p, получается, что процесс p получил маркер на один раз больше,

чем послал его. Отсюда следует, что количество каналов, инцидентных p,

превышает количество каналов, использованных p, по крайней мере, на 1.

Таким образом, p не принимает решение, а передает маркер дальше.

Следовательно, решение принимается в инициаторе.

Далее, за 3 шага будет доказано, что когда алгоритм завершается, каждый

процесс передал маркер.

Все каналы, инцидентные инициатору, были пройдены один раз в обоих

направлениях. Инициатором маркер был послан по всем каналам, иначе алгоритм

не завершился бы. Инициатор получил маркер ровно столько же раз, сколько

отправил его; т.к. инициатор получал маркер каждый раз через другой канал,

то маркер пересылался через каждый канал по одному разу.

Для каждого посещаемого процесса p все каналы, инцидентные p были пройдены

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

качестве p первый встретившийся процесс, для которого это не выполняется, и

заметим, что из пункта (1) p не является инициатором. Из выбора p, все

каналы, инцидентные fatherp были пройдены один раз в обоих направлениях,

откуда следует, что p переслал маркер своему родителю. Следовательно, p

использовал все инцидентные каналы, чтобы переслать маркер; но, т.к. маркер

в конце остается в инициаторе, p получил маркер ровно столько же раз,

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

инцидентный канал. Мы пришли к противоречию.

Все процессы были посещены и каждый канал был пройден по одному разу в

обоих направлениях. Если есть непосещенные процессы, то существуют соседи p

и q такие, что p был посещен, а q не был. Это противоречит тому, что все

каналы p были пройдены в обоих направлениях. Следовательно, из пункта (2),

все процессы были посещены и все каналы пройдены один раз в обоих

направлениях.

Каждое вычисление алгоритма Тарри определяет остовное дерево сети, как

показано в Лемме 6.3. В корне дерева находится инициатор, а каждый не-

инициатор p в конце вычисления занес своего родителя в дереве в переменную

fatherp. Желательно, чтобы каждый процесс также знал (в конце вычисления),

какие из его соседей являются его сыновьями в дереве. Этого можно

достигнуть, посылая родителю fatherp специальное сообщение.

6.4 Временная сложность: поиск в глубину

Процессы в алгоритме Тарри достаточно свободны в выборе соседа, которому

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

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

остовные деревья с дополнительным свойством: каждое листовое ребро

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

ребро - это ребро, не принадлежащее остовному дереву. В данном корневом

остовном дереве T сети G для каждого p T[p] обозначает множество процессов

в поддереве p, а A[p] обозначает предков p, т.е. вершины на пути в T от

корня до p. Заметим, что q ? T[p] ? p ? A[q].

Определение 6.30 Остовное дерево T сети G называется деревом поиска в

глубину, если для каждого листового ребра pq q ? T[p] ? q ? A[p].

Деревья поиска в глубину, или DFS-деревья (DFS - Depth-First Search),

используются во многих алгоритмах на графах, таких как проверка

планарности, проверка двусвязности, и для построения интервальных схем

маркировки (см. Подраздел 4.4.2). В Разделе 6.4.1 будет показано, что

незначительная модификация алгоритма Тарри (а именно, ограничение свободы

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

Получившийся алгоритм будем называть классическим алгоритмом поиска в

глубину. В Подразделе 6.4.2 будут представлены два алгоритма, которые

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

алгоритм. Понятие временной сложности распределенных алгоритмов будет

определено ниже. В Подразделе 6.4.3 будет представлен алгоритм поиска в

глубину для сетей с начальным знанием идентификации соседей. В этом случае

Теорема 6.6 неприменима, и фактически может быть дан алгоритм, использующий

только 2N-2 сообщений.

Временная сложность распределенных алгоритмов. Исключительно в целях

анализа распределенных алгоритмов, будут сделаны некоторые идеализированные

временные предположения. Корректность алгоритмов никак не зависит от этих

предположений.

Определение 6.31 Временная сложность распределенного алгоритма - это

максимальное время, требуемое на вычисление алгоритма при следующих

предположениях:

T1. Процесс может выполнить любое конечное количество событий за нулевое

время.

T2. Промежуток времени между отправлением и получением сообщения - не более

одной единицы времени.

Временные сложности всех волновых алгоритмов этой главы изложены в Таблице

6.19. Проверка величин из этой таблицы, не доказанных в этой главе,

оставлена читателю в качестве упражнения. Альтернативные определения

временной сложности обсуждаются в Подразделе 6.5.3.

Лемма 6.32 Для алгоритмов обхода временная сложность равна сложности

сообщений.

Доказательство. Сообщения пересылаются последовательно, и каждое может

занять одну единицу времени.

6.4.1 Распределенный поиск в глубину

Классический алгоритм поиска в глубину получается, когда свобода выбора

соседа для передачи маркера в алгоритме Тарри ограничивается следующим,

третьим правилом; см. Алгоритм 6.14.

R3. Когда процесс получает маркер, он отправляет его обратно через тот же

самый канал, если это позволяется правилами R1 и R2.

Теорема 6.33 Классический алгоритм поиска в глубину (Алгоритм 6.14)

вычисляет остовное дерево поиска в глубину, используя 2|E| сообщений и 2|E|

единиц времени.

Доказательство. Т.к. алгоритм реализует алгоритм Тарри, это алгоритм обхода

и он вычисляет остовное дерево T. Уже было показано, что каждый канал

передает два сообщения (по одному в обоих направлениях), что доказывает

оценку сложности сообщений, а оценка для временной сложности следует из

того, что 2|E| сообщений передаются одно за другим, причем каждое занимает

не более одной единицы времени. Остается показать, что из правила R3

следует, что получающееся дерево - дерево поиска в глубину.

Во-первых, из R3 следует, что за первым проходом по листовому ребру

немедленно следует второй, в обратном направлении. Пусть pq - листовое

ребро и p первым использует ребро. Когда q получает маркер от p, q уже

посещен (иначе q присвоит fatherq p и ребро не будет листовым) и usedp[q] =

false (т.к. по предположению p первый из двух процессов использовал ребро).

Следовательно, по правилу R3, q немедленно отправляет маркер обратно p.

Теперь можно показать, что если pq - листовое ребро, используемое сначала

p, то q ? A[p]. Рассмотрим путь, пройденный маркером, пока он не был

переслан через pq. Т.к. pq - листовое ребро, q был посещен до того, как

маркер попал в q через это ребро:

..., q, ..., p, q

Получим из этого пути возможно более короткий путь, заменив все комбинации

r1, r2, r1, где r1r2 - листовое ребро, на r1. Из предыдущих наблюдений, все

листовые ребра теперь убраны, откуда следует, что получившийся путь - это

путь в T, состоящий только из ребер, пройденных до первого прохождения pq.

Если q не является предком p, то отсюда следует, что ребро от q до fatherq

было пройдено до того, как было пройдено ребро qp, что противоречит правилу

R2 алгоритма.

var usedp[q] : boolean init false для всех q ? Neighp ;

(* Признак того, отправил ли p сообщение q *)

fatherp : process init udef ;

Для инициатора (выполняется один раз):

begin fatherp := p ; выбор q ? Neighp ;

usedp[q] := true ; send to q ;

end

Для каждого процесса при получении от q0:

begin if fatherp = udef then fatherp := q0 ;

if ?q ? Neighp : usedp[q]

then decide

else if ?q ? Neighp : (q ? fatherp & ¬usedp[q])

then begin if fatherp ? q0 & ¬usedp[q0]

then q := q0

else выбор q ? Neighp \ {fatherp}

с ¬usedp[q] ;

usedp[q] := true ; send to q

end

else begin usedp[fatherp] := true ;

send to fatherp

end

end

Алгоритм 6.14 Классический алгоритм поиска в глубину.

Сложность сообщений классического распределенного поиска в глубину равна

2|E|, по Теореме 6.6 это наилучшая сложность (за исключением множителя 2),

если идентификация соседей не известна изначально. Временная сложность

также составляет 2|E|, что по Лемме 6.32, является наилучшей сложностью для

алгоритмов обхода в этом случае. Распределенная версия поиска в глубину

была впервые представлена Cheung [Che83].

В Подразделе 6.4.2 будут рассмотрены два алгоритма, которые строят дерево

поиска в глубину в сети без знания идентификации соседей за O(N) единиц

времени. Следовательно, эти алгоритмы не являются алгоритмами обхода. В

Подразделе 6.4.3 знание о соседях будет использовано для получения

алгоритма с временной сложностью и сложностью сообщений O(N).

6.4.2 Алгоритмы поиска в глубину за линейное время

Причина высокой временной сложности классического алгоритма поиска в

глубину состоит в том, что все ребра, как принадлежащие дереву, так и

листовые, обходятся последовательно. Сообщение-маркер проходит по

всем листовым ребрам и немедленно возвращается обратно, как показано в

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

основаны на том, что маркер проходит только по ребрам дерева. Очевидно, на

это потребуется линейное время, т.к. существует только N-1 ребро дерева.

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

передачу маркера через листовое ребро. В алгоритме Авербаха [Awerbuch;

Awe85b] гарантируется, что каждый процесс в момент, когда он должен

передать маркер, знает, какие из его соседей уже были пройдены. Затем

процесс выбирает непройденного соседа, или, если такого не существует,

посылает маркер своему родителю.

Когда процесс p впервые посещается маркером (для инициатора это происходит

в начале алгоритма), p сообщает об этом всем соседям r, кроме его родителя,

посылая сообщения . Передача маркера откладывается, пока p не получит

сообщения от всех соседей. При этом гарантируется, что каждый сосед r

процесса p в момент, когда p передает маркер, знает, что p был посещен.

Когда позже маркер прибывает в r, r не передаст маркер p, если только p не

его родитель; см. Алгоритм 6.15.

Из-за передачи сообщений в большинстве случаев usedp[fatherp] = true,

даже если p еще не послал маркер своему родителю. Поэтому в алгоритме

должно быть явно запрограммировано, что только инициатор может принимать

решения; а не-инициатор p, для которого usedp[q] = true для всех соседей q,

передает маркер своему родителю.

Теорема 6.34 Алгоритм Авербаха (Алгоритм 6.15) вычисляет дерево поиска в

глубину за 4N-2 единиц времени и использует 4|E| сообщений.

Доказательство. По существу, маркер передается по тем же самым каналам, как

и в Алгоритме 6.14, за исключением того, что пропускается передача по

листовым каналам. Т.к. передача по листовым каналам не влияет на конечное

значение fatherp для любого процесса p, то в результате всегда получается

дерево, которое может получиться и в Алгоритме 6.14.

Маркер последовательно проходит дважды через каждый из N-1 каналов дерева,

на что тратится 2N-2 единиц времени. В каждой вершине маркер простаивает

перед тем, как быть переданным, не более одного раза из-за обмена

сообщениями /, что приводит к задержке не более чем на 2 единицы

времени в каждой вершине.

Каждое листовое ребро передает два сообщения и два сообщения .

Каждое ребро в дереве передает два сообщения , одно (посылаемое

от родителя потомку), и одно (от потомка родителю). Следовательно,

передается 4|E| сообщений.

var usedp[q] : boolean init false для всех q ? Neighp ;

(* Признак того, отправил ли p сообщение q *)

fatherp : process init udef ;

Для инициатора (выполняется один раз):

begin fatherp := p ; выбор q ? Neighp ;

forall r ? Neighp do send to r ;

forall r ? Neighp do receive from r ;

usedp[q] := true ; send to q ;

end

Для каждого процесса при получении от q0:

begin if fatherp = udef then

begin fatherp := q0 ;

forall r ? Neighp\ {fatherp} do send to r ;

forall r ? Neighp\ {fatherp} do receive from r ;

end ;

if p - инициатор and ?q ? Neighp : usedp[q]

then decide

else if ?q ? Neighp : (q ? fatherp & ¬usedp[q])

then begin if fatherp ? q0 & ¬usedp[q0]

then q := q0

else выбор q ? Neighp \ {fatherp}

с ¬usedp[q] ;

usedp[q] := true ; send to q

end

else begin usedp[fatherp] := true ;

send to fatherp

end

end

Для каждого процесса при получении от q0:

begin usedp[q0] := true ; send to q0 end

Алгоритм 6.15 Алгоритм поиска в глубину Авербаха.

Передачу сообщения соседу, которому процесс передает маркер, можно

опустить. Это усовершенствование (не выполняемое в Алгоритме 6.15)

сберегает по два сообщения для каждого ребра дерева и, следовательно,

уменьшает сложность сообщений на 2N-2 сообщения.

Решение Сайдона. Алгоритм Сайдона [Cidon; Cid88] улучшает временную

сложность алгоритма Авербаха, не посылая сообщения . В модификации

Сайдона маркер передается немедленно, т.е. без задержки на 2 единицы

времени, внесенной в алгоритм Авербаха ожиданием подтверждения. Этот же

алгоритм был предложен Лакшмананом и др. [Lakshmanan; LMT87]. В алгоритме

Сайдона может возникнуть следующая ситуация. Процесс p получил маркер и

послал сообщение своему соседу r. Маркер позже попадает в r, но в

момент, когда r получает маркер, сообщение процесса p еще не достигло

r. В этом случае r может передать маркер p, фактически посылая его через

листовое ребро. (Заметим, что сообщения в алгоритме Авербаха

предотвращают возникновение такой ситуации.)

Чтобы обойти эту ситуацию процесс p запоминает (в переменной mrsp), какому

соседу он переслал маркер в последний раз. Когда маркер проходит только по

ребрам дерева, p получает его в следующий раз от того же соседа mrsp. В

ситуации, описанной выше, p получает сообщение от другого соседа, а

именно, от r; в этом случае маркер игнорируется, но p помечает ребро rp,

как пройденное, как если бы от r было получено сообщение . Процесс r

получает сообщение от p после пересылки маркера p, т.е. r получает

сообщение от соседа mrsr. В этом случае r действует так, как если бы

он еще не послал маркер p; r выбирает следующего соседа и передает маркер;

см. Алгоритм 6.16/6.17.

Теорема 6.35 Алгоритм Сайдона (Алгоритм 6.16/6.17) вычисляет DFS-дерево за

2N-2 единиц времени, используя 4|E| сообщений.

Доказательство. Маршрут маркера подобен маршруту в Алгоритме 6.14.

Прохождение по листовым ребрам либо пропускается (как в Алгоритме 6.15),

либо в ответ на маркер через листовое ребро посылается сообщение . В

последнем случае, процесс, получая сообщение , продолжает передавать

маркер, как если бы маркер был возвращен через листовое ребро немедленно.

Время между двумя успешными передачами маркера по дереву ограничено одной

единицей времени. Если маркер послали по ребру дерева процессу p в момент

времени t, то в момент t все сообщения ранее посещенных соседей q

процесса p были посланы, и, следовательно, эти сообщения прибудут не

позднее момента времени t+1. Итак, хотя p мог несколько раз послать маркер

по листовым ребрам до t+1, не позднее t+1 p восстановился после всех этих

ошибок и передал маркер по ребру, принадлежащему дереву. Т.к. должны быть

пройдены 2N-2 ребра дерева, алгоритм завершается за 2N-2 единиц времени.

Через каждый канал передается не более двух сообщений и двух ,

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18