(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 < # Neighpdo
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>:
begin if k=n2then 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-обхода для торов.
Доказательство. Как легко заметить из алгоритма, решение принимается после того, как маркер был передан n2 раз. Если маркер переходит от процесса p к процессу q с помощью U переходов вверх и R переходов вправо, то p = q тогда и только тогда, когда (n|U & n|R). Обозначим через p0 инициатор, а через pk - процесс, который получает маркер <num, k>.
Из 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 : 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, а значит n2|(b-a), что приводит к противоречию.
Т.к. все процессы с p0 по pn2 -1 различны, после x переходов маркера будет посещен x+1 процесс.
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 <num, 1> по каналу n -1
Для каждого процесса при получении маркера <num,k>:
begin if k=2nthen decide
else begin пусть l - наибольший номер : 2l|k ;
send <num,k+1> по каналу l
end
end
Алгоритм 6.12 Алгоритм обхода для гиперкубов.
Теорема 6.28 Алгоритм для гиперкуба (Алгоритм 6.12) является алгоритмом x-обхода для гиперкуба.
Доказательство. Из алгоритма видно, что решение принимается после 2n пересылок маркера. Пусть p0 - инициатор, а pk - процесс, который получает маркер <num,k>. Для любого k < 2n, обозначения pk и pk+1 отличаются на 1 бит, индекс которого обозначим как l(k), удовлетворяющий следующему условию:
Т.к. для любого i < n существует равное количество k Î {0, ..., 2n} с l(k) = i, то p0 = p2n и решение принимается в инициаторе. Аналогично доказательству Теоремы 6.27, можно показать, что из pa = pb следует, что 2n|(b-a), откуда следует, что все p0, ..., p2n-1 различны.
Из всего этого следует, что, когда происходит завершение, все процессы пройдены, и после x переходов маркера будет посещен x+1 процесс.
Алгоритм обхода для произвольных связных сетей был дан Тарри в 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 <tok> to q ;
end
Для каждого процесса при получении <tok> от 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 <tok> to q
end
else begin usedp[fatherp] := true ;
send <tok> to fatherp
end
end
Алгоритм 6.13 Алгоритм обхода Тарри.
Теорема 6.29 Алгоритм Тарри (Алгоритм 6.13) является алгоритмом обхода.
Доказательство. Т.к. маркер передается не более одного раза в обоих направлениях через каждый канал, всего он передается не более 2|E| раз до завершения алгоритма. Т.к. каждый процесс передает маркер через каждый канал не более одного раза, то каждый процесс получает маркер через каждый канал не более одного раза. Каждый раз, когда маркер захватывается не-инициатором p, получается, что процесс p получил маркер на один раз больше, чем послал его. Отсюда следует, что количество каналов, инцидентных p, превышает количество каналов, использованных p, по крайней мере, на 1. Таким образом, p не принимает решение, а передает маркер дальше. Следовательно, решение принимается в инициаторе.
Далее, за 3 шага будет доказано, что когда алгоритм завершается, каждый процесс передал маркер.
(1) Все каналы, инцидентные инициатору, были пройдены один раз в обоих направлениях. Инициатором маркер был послан по всем каналам, иначе алгоритм не завершился бы. Инициатор получил маркер ровно столько же раз, сколько отправил его; т.к. инициатор получал маркер каждый раз через другой канал, то маркер пересылался через каждый канал по одному разу.