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

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. Процесс никогда не передает маркер дважды по одному и тому же каналу.

Страницы: 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