Реферат: Распределенные алгоритмы
Теперь нужно показать, что решению 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>:
begin if k=n2 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-обхода для торов.
Доказательство. Как легко заметить из алгоритма, решение принимается после того, как маркер был передан 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 кратно 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
Страницы: 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, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105
