Реферат: Распределенные алгоритмы
Лемма 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 if p - инициатор then
begin forall r Î Neighp do send <tok> to r ;
Sentp := Sentp + 1
end ;
while Recp < # Neighp do
begin receive <tok> ;
Recp := Recp + 1 ;
if Sentp = 0 then
begin forall r Î Neighp do send <tok> to r ;
Sentp := Sentp + 1
end
end ;
decide
end
Алгоритм 6.8 Фазовый алгоритм для клики.
Фазовый алгоритм для клики. Если сеть имеет топологию клика, ее диаметр равен 1; в этом случае от каждого соседа должно быть получено ровно одно сообщение, и для каждого процесса достаточно посчитать общее количество полученных сообщений вместо того, чтобы считать сообщения от каждого соседа по входу отдельно; см. Алгоритм 6.8. Сложность сообщений в этом случае равна N(N-1) и алгоритм использует только O(log N) бит оперативной памяти.
Алгоритм Финна [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 <sets, Incp, NIncp> to r ;
while Incp ¹ NIncp do
begin receive <sets, Inc, NInc> 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 <sets, Incp, NIncp> to r
end ;
decide
end
Алгоритм 6.9 Алгоритм Финна.
Сейчас мы покажем, что в ¡ каждый процесс принял решение. Во-первых, если существует ребро pq, то Incp Í Incq в ¡. Действительно, после последнего изменения Incp процесс p посылает сообщение <sets, Incp, NIncp>, и после его получения в 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 p f, то q Î Inc(f).
Доказательство. Как в доказательстве Теоремы 6.12, можно показать, что e p f Þ Inc(e) Í Inc(f), а при e Î Cq Þ q Î Inc(e), что и требовалось доказать.
Утверждение 6.23 Если q Î NInc(f), тогда для всех r Î Inq существует событие e Î Cr : e p f.
Доказательство. Пусть aq - внутреннее событие q, в котором впервые в q выполняется присваивание NIncq := NIncq È {q}. Событие aq - единственное событие с q Î NInc(aq), которому не предшествует никакое другое событие a¢, удовлетворяющее условию q Î NInc(a¢); таким образом, q Î NInc(f) Þ aq p f.
Из алгоритма следует, что для любого r Î Inq существует событие e Î Cr, предшествующее aq. Отсюда следует результат.
Процесс p принимает решение только когда Incp = NIncp; можно записать, что Inc(dp) = NInc(dp). В этом случае
(1) p Î Inc(dp) ; и
(2) из q Î Inc(dp) следует, что q Î NInc(dp), откуда следует, что Inq Í Inc(dp).
Из сильной связности сети следует требуемый результат: Inc(dp) = P.
В этом разделе будет представлен особый класс волновых алгоритмов, а именно, волновые алгоритмы, в которых все события волны совершенно упорядочены каузальным отношением, и в котором последнее событие происходит в том же процессе, где и первое.
Определение 6.24 Алгоритмом обхода называется алгоритм, обладающий следующими тремя свойствами.
(1) В каждом вычислении один инициатор, который начинает выполнение алгоритма, посылая ровно одно сообщение.
(2) Процесс, получая сообщение, либо посылает одно сообщение дальше, либо принимает решение.
Из первых двух свойств следует, что в каждом конечном вычислении решение принимает ровно один процесс. Говорят, что алгоритм завершается в этом процессе.
(3) Алгоритм завершается в инициаторе и к тому времени, когда это происходит, каждый процесс посылает сообщение хотя бы один раз.
В каждой достижимой конфигурации алгоритма обхода либо передается ровно одно сообщение, либо ровно один процесс получил сообщение и еще не послал ответное сообщение. С более абстрактной точки зрения, сообщения в вычислении, взятые вместе, можно рассматривать как единый объект (маркер), который передается от процесса к процессу и, таким образом, «посещает» все процессы. В Разделе 7.4 алгоритмы обхода используются для построения алгоритмов выбора и для этого важно знать не только общее количество переходов маркера в одной волне, но и сколько переходов необходимо для того, чтобы посетить первые x процессов.
Определение 6.25 Алгоритм называется алгоритмом f-обхода (для класса сетей), если
(1) он является алгоритмом обхода (для этого класса); и
(2) в каждом вычислении после f(x) переходов маркера посещено не менее min (N, x+1) процессов.
Кольцевой алгоритм (Алгоритм 6.2) является алгоритмом обхода, и, поскольку x+1 процесс получил маркер после x шагов (для x < N), а все процессы получат его после N шагов, это алгоритм x-обхода для кольцевой сети.
Клику можно обойти путем последовательного опроса; алгоритм очень похож на Алгоритм 6.6, но за один раз опрашивается только один сосед инициатора. Только когда получен ответ от одного соседа, опрашивается следующий; см. Алгоритм 6.10.
var recp : integer init 0 ; (* только для инициатора *)
Для инициатора:
(* обозначим Neighp = {q1, q2, .., qN-1} *)
begin while recp < # Neighp do
begin send <tok> to qrecp+1 ;
receive <tok>; recp := recp + 1
end ;
decide
end
Для не-инициатора:
begin receive <tok> from q ; send <tok> to q end
Алгоритм 6.10 Последовательный алгоритм опроса.
Теорема 6.26 Последовательный алгоритм опроса (Алгоритм 6.10) является алгоритмом 2x-обхода для клик.
Доказательство. Легко заметить, что к тому времени, когда алгоритм завершается, каждый процесс послал инициатору ответ. (2x-1)-е сообщение - это опрос для qx, а (2x)-е - это его ответ. Следовательно, когда было передано 2x сообщений, был посещен x+1 процесс p, q1, ..., qx.
Тором 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 <num, 1> to Up
Для каждого процесса при получении маркера <num,k>:
Страницы: 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
