ref (664672), страница 20

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 20)

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

forall r  Out_p do send <sets, Inc_p, NInc_p> to r ;

while Inc_p  NInc_p do

begin receive <sets, Inc, NInc> from q₀ ;

Inc_p := Inc_p  Inc ; NInc_p := NInc_p  NInc ;

rec_p[q₀] := true ;

if q  In_p : rec_p[q] then NInc_p := NInc_p  {p} ;

if Inc_p или NInc_p изменились then

forall r  Out_p do send <sets, Inc_p, NInc_p> to r

end ;

decide

end

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

Сейчас мы покажем, что в  каждый процесс принял решение. Во-первых, если существует ребро pq, то Inc_p  Inc_q в . Действительно, после последнего изменения Inc_p процесс p посылает сообщение <sets, Inc_p, NInc_p>, и после его получения в q выполняется Inc_q := Inc_q  Inc_p. Из сильной связности сети следует, что Inc_p = Inc_q для всех p и q. Т.к. выполняется p  Inc_p и каждое множество Inc содержит только идентификаторы процессов, для каждого p Inc_p = P.

Во-вторых, подобным же образом может быть показано, что NInc_p = Ninc_q для любых p и q. Т.к. каждый процесс отправил хотя бы одно сообщение по каждому каналу, для каждого процесса p выполняется:  q  In_p : rec_p[q], и следовательно, для каждого p выполняется: p  NInc_p. Множества NInc содержат только идентификаторы процессов, откуда следует, что NInc_p = P для каждого p. Из Inc_p = P и NInc_p = P следует, что Inc_p = NInc_p, следовательно, каждый процесс p в  принял решение.

Теперь нужно показать, что решению d_p в процессе p предшествуют события в каждом процессе. Для события e в процессе p обозначим через Inc^(e) (или, соответственно, NInc^(e)) значение Inc_p (NInc_p) сразу после выполнения e (сравните с доказательством Теоремы 6.12). Следующие два утверждения формализуют неформальные описания множеств в начале этого раздела.

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

Доказательство. Как в доказательстве Теоремы 6.12, можно показать, что e  f  Inc^(e)  Inc^(f), а при e  C_q  q  Inc^(e), что и требовалось доказать.

Утверждение 6.23 Если q  NInc^(f), тогда для всех r  In_q существует событие e  C_r : e  f.

Доказательство. Пусть a_q - внутреннее событие q, в котором впервые в q выполняется присваивание NInc_q := NInc_q  {q}. Событие a_q - единственное событие с q  NInc^(aq), которому не предшествует никакое другое событие a, удовлетворяющее условию q  NInc^(a); таким образом, q  NInc^(f)  a_q  f.

Из алгоритма следует, что для любого r  In_q существует событие e  C_r, предшествующее a_q. Отсюда следует результат.

Процесс p принимает решение только когда Inc_p = NInc_p; можно записать, что Inc^(dp) = NInc^(dp). В этом случае

1. p  Inc^(dp) ; и

2. из q  Inc^(dp) следует, что q  NInc^(dp), откуда следует, что In_q  Inc^(dp).

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

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

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

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

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

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

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

1. Алгоритм завершается в инициаторе и к тому времени, когда это происходит, каждый процесс посылает сообщение хотя бы один раз.

В каждой достижимой конфигурации алгоритма обхода либо передается ровно одно сообщение, либо ровно один процесс получил сообщение и еще не послал ответное сообщение. С более абстрактной точки зрения, сообщения в вычислении, взятые вместе, можно рассматривать как единый объект (маркер), который передается от процесса к процессу и, таким образом, «посещает» все процессы. В Разделе 7.4 алгоритмы обхода используются для построения алгоритмов выбора и для этого важно знать не только общее количество переходов маркера в одной волне, но и сколько переходов необходимо для того, чтобы посетить первые x процессов.

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

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

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

Кольцевой алгоритм (Алгоритм 6.2) является алгоритмом обхода, и, поскольку x+1 процесс получил маркер после x шагов (для x < N), а все процессы получат его после N шагов, это алгоритм x-обхода для кольцевой сети.

6.3.1 Обход клик

Клику можно обойти путем последовательного опроса; алгоритм очень похож на Алгоритм 6.6, но за один раз опрашивается только один сосед инициатора. Только когда получен ответ от одного соседа, опрашивается следующий; см. Алгоритм 6.10.

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

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

(* обозначим Neigh_p = {q₁, q₂, .., q_N-1} *)

begin while rec_p < # Neigh_p do

begin send <tok> to q_recp+1 ;

receive <tok>; rec_p := rec_p + 1

end ;

decide

end

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

begin receive <tok> from q ; send <tok> to q end

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

Теорема 6.26 Последовательный алгоритм опроса (Алгоритм 6.10) является алгоритмом 2x-обхода для клик.

Доказательство. Легко заметить, что к тому времени, когда алгоритм завершается, каждый процесс послал инициатору ответ. (2x-1)-е сообщение - это опрос для q_x, а (2x)-е - это его ответ. Следовательно, когда было передано 2x сообщений, был посещен x+1 процесс p, q₁, ..., q_x.

6.3.2 Обход торов

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

V = Z_n  Z_n = { (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>:

begin if k=n² then decide

else if n|k then send <num,k+1> to Up

else send <num,k+1> to Right

end

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

Тор является Гамильтоновым графом, т.е. в торе (произвольного размера) существует Гамильтонов цикл и маркер передается по циклу с использованием Алгоритма 6.11. После k-го перехода маркера он пересылается вверх, если n|k (k делится на n), иначе он передается направо.

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

Доказательство. Как легко заметить из алгоритма, решение принимается после того, как маркер был передан n² раз. Если маркер переходит от процесса p к процессу q с помощью U переходов вверх и R переходов вправо, то p = q тогда и только тогда, когда (n|U & n|R). Обозначим через p₀ инициатор, а через p_k - процесс, который получает маркер <num, k>.

Из n² переходов маркера n - переходы вверх, а оставшиеся n²-n - переходы вправо. Т.к. и n, и n²-n кратны n, то p_n2 = p₀, следовательно, алгоритм завершается в инициаторе.

Далее будет показано, что все процессы с p₀ по p_n2 _-1 различны; т.к. всего n² процессов, то отсюда следует, что каждый процесс был пройден. Предположим, что p_a = p_b для 0  a < b < n². Между p_a и p_b маркер сделал несколько переходов вверх и вправо, и т.к. p_a = p_b, количество переходов кратно n. Изучив алгоритм, можно увидеть, что отсюда следует, что

# {k : a  k < b & n|k} кратно n, и

# {k : a  k < b & n не |k} кратно n.

Размеры двух множеств в сумме составляют b-a, откуда следует, что n|(b-a). Обозначим (b-a) = l*n, тогда множество {k: a k < b} содержит l кратных n. Отсюда следует, что n|l, а значит n²|(b-a), что приводит к противоречию.

Т.к. все процессы с p₀ по p_n2 _-1 различны, после x переходов маркера будет посещен x+1 процесс.

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

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

V = { (b₀,...,b_n-1) : b_i = 0, 1} и

E = { (b₀,...,b_n-1),(c₀,...,c_n-1) : b и c отличаются на 1 бит};

см. Подраздел B.2.5. Предполагается, что гиперкуб обладает чувством направления (см. Раздел B.3), т.е. канал между вершинами b и c, где b и c различаются битом с номером i, помечается «i» в обеих вершинах. Предполагается, что метки вершин не известны процессам; их топологическое знание ограничено метками каналов.

Как и тор, гиперкуб является Гамильтоновым графом, и Гамильтонов цикл обходится с использованием Алгоритма 6.12. Доказательство корректности алгоритма похоже на доказательство для Алгоритма 6.11.

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

send <num, 1> по каналу n -1

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

begin if k=2ⁿ then decide

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

send <num,k+1> по каналу l

end

end

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

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

Доказательство. Из алгоритма видно, что решение принимается после 2ⁿ пересылок маркера. Пусть p₀ - инициатор, а p_k - процесс, который получает маркер <num,k>. Для любого k < 2ⁿ, обозначения p_k и p_k+1 отличаются на 1 бит, индекс которого обозначим как l(k), удовлетворяющий следующему условию:

Т.к. для любого i < n существует равное количество k  {0, ..., 2ⁿ} с l(k) = i, то p₀ = p₂n и решение принимается в инициаторе. Аналогично доказательству Теоремы 6.27, можно показать, что из p_a = p_b следует, что 2ⁿ|(b-a), откуда следует, что все p₀, ..., p₂n_-1 различны.

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

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

Алгоритм обхода для произвольных связных сетей был дан Тарри в 1895 [Tarry; T1895]. Алгоритм сформулирован в следующих двух правилах; см. Алгоритм 6.13.

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

Характеристики

Список файлов реферата