Реферат: Распределенные алгоритмы
Lemma 7.22 Если произведены k> 1 маркеров на уровне l, по крайней мере один и не более k/2 маркеров произведены на уровне l + 1.
begin if p is initiator then
begin levp := levp + 1 ; lastp := trav(p. levp) ;
catp := p ; send (annex, p, levp ) to lastp
end ;
while . . . (* Условие завершения, смотри текст *) do
if token is annexing then t := A else t := C ;
waitp := udef ; lastp := trav(q, l) ;
end
else if l == levp and waitp ¹udef then (* Случай II *)
begin waitp := udef ; levp := levp + 1 ;
lastp := trav(p, levp) ; catp := p ;
send ( annex, p, levp ) to lastp
end
else if l = levp and lastp = udef then (* Случай III *)
waitp := q
else if l = levp and t = A and q = catp then (* Случай IV *)
if lastp = decide then p объявляет себя лидером
else send ( annex, q,l) to lastp
end
else if l = levp and ((t = A and q > catp) or t = C) then (* Cлучай V *)
begin send ( chase, q, t ) to lastp ; lastp := udef end
else if l = levp then (* Cлучай VI *)
waitp := q
end
end
Алгоритм 7.13 korach-kutten-moran алгоритм.
Доказательство. Не более k/2 маркеров произведены на уровне l + 1, потому что, когда такой маркер произведен, два маркера уровня l убиты в то же самое время.
Предположим, что имеется уровень l такой, что k> l маркеров произведены на уровне l, но никаком маркер не произведен на уровне l + 1. Пусть q процесс с максимальным идентификатором, который производит маркер на уровне l.Маркер (q, l) не заканчивает обход, потому что он будет получен процессом p, который уже отправил другой маркер уровня l.Когда это случается впервые (q, l) становится chasing или, если p уже отправил маркер chasing, (q, l) становится waiting. В любом случае, уровне l есть маркеры chasing .
Пусть (r, l) маркер с минимальным идентификатором после, которого посылается маркер chasing . Маркер (r, l) сам не может быть chasing, потому что маркер chasing преследует только маркеры с меньшим идентификатором. Мы можем поэтому предполагать, что (r, 1) стал waiting, когда он впервые достиг процесса p¢, который уже отправил другой маркер уровня l.Пусть p" последний процесс на пути следования (r, l), который получил маркер annexing, после того как он отправил
(r, l), и маркер сменил режим на chasing r. Этот маркер chasing встретит (r, 1) в p ', или откажется от преследования, если маркер waiting был найден прежде, чем маркер достиг p '. В обоих случаях маркер на уровне l + 1 произведен, т.е. мы пришли к противоречию.
Теорема 7.23 Korach-Kutten-Moran алгоритм (Алгоритм 7.13) - алгоритм выбора.
Доказательство Предположим, что по крайней мере один процесс начинает алгоритм. Согдасно предыдущей лемме, число маркеров, произведенных на каждом уровня уменьшается, и будет иметься уровень, на котором точно один маркер, скажем (q, 1) произведен. Никакой маркер уровня l ' < l не заканчивает обход, следовательно ни один из этих маркеров не заставляет процесс стать избранным. Уникальный маркер на уровне l только сталкивается с процессами на уровнях меньше чем l, или с cat = q (если он достигает процесса, который уже посещал), и отправляется в обоих случаях. Следовательно обход этого маркера заканчивается, и q избран.
Функция f, как считается выпуклой если f (a) + f (b) £ f (+ b). Сложность алгоритма проанализирована здесь согласно предположению что f (x) - алгоритм обхода(см. Раздел 6.3) , где f - выпуклая функция.
Теорема 7.24 если f (x) - используется алгоритмом обхода, где f выпуклая , KKM алгоритм выбора не более (1+log k)[f(N)+N] сообщений если он начинается k процессами.
Доказательство. Если алгоритм начат k процессами, не более 2-l маркеров произведены на уровне l, что означает, что самый высокий уровень - не более ëlogkû.
Каждый процесс посылает маркеры annexing не более одного идентификатора на каждом уровне. Если на некотором уровне l имеются маркеры с идентификаторами p1, …, pj и имеются процессы Ni, которые отправили маркер annexing (pi, l), то из этого следует что S1j Ni £ N . Т.к. алгоритм обхода является f (x) - алгоритмом обхода, маркер annexing (pj, l) был послан не более f (Nj) раз, что дает общее количество сообщений передающих маркеры annexing уровня l не более S1j f(Ni) , что не превышает f (N), потому что f выпуклая. Каждый процесс посылает не более одного маркера chasing на каждом уровне, что дает не более N маркеров chasing на уровень.
Таким образом имеется не более (1 + log k) различных уровней, и не более f (N) + N сообщений посылаются на каждом уровене, что доказывает результат. o
Построение Attiya. Другое постоения алгоритма выбора из алгоритмов обхода давалось Attiya [Att87]. В этом построении обход одного маркера, скажем с идентификатором q , не прерывается до тех пор, пока маркер не достигнет процесса r уже посещенного другим маркером, скажем процесса p.Маркер annexing ждет в r, но посылает маркер "охотник", чтобы преследовать маркер p и затем ветнуться в r, если p может быть успешно побежден. Если охотник возвращается, не нужно начинать новый обход, а текущий обход маркера q продолжается, таким образом потенциально сокращается сложность по сообщениям. Чтобы позволять охотнику возвращаться, чтобы обработать r, сеть должна быть двунаправленая. Если используется f (x) - алгоритм обхода, результирующий алгоритм выбора имеет сложность по сообщениям приблизительно 3. S1j f(N/i)
Страницы: 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
