Волновые алгоритмы и алгоритмы обхода Титаренко Александра, гр 5201

Определение волнового алгоритма Волновым алгоритмом называется распределенный алгоритм, который удовлетворяет следующим трем требованиям: – Завершение. Каждое вычисление C конечно: C: |C|

Аспекты, в которых волновые алгоритмы отличаются друг от друга Централизация Топология Первоначальные сведения Число решений Сложность

Основные свойства Структурные свойства волн – Каждому событию в вычислении предшествует некоторое событие в инициаторе. – Волна с одним инициатором определяет остовное дерево сети, если для каждого не инициатора выделить канал, по которому он получает первое сообщение. – В качестве события f, упомянутого в третьем пункте определения, можно выбрать событие отправления сообщения для всех процессов q за исключением того процесса, в котором происходит событие decide. Нижние оценки сложности – Для числа сообщений, которыми обмениваются процессы при прохождении волны нижняя оценка N-1. Если событие решения происходит только в инициаторе, то оценка увеличивается до N сообщений.

Распространение информации с обратной связью (алгоритм PIF) Есть множество процессов, обладающих сообщением M. Сообщение M должно быть распространено широковещательно. Некоторые выделенные процессы должны быть уведомлены о завершении широковещательной связи (событие notify). Событие notify происходит только в том случае, когда все процессы получат сообщение M. Событие notify рассматривается как событие решения.

Синхронизация (SYN-алгоритм) В каждом процессе q должно быть выполнено событие a q. В некоторых процессах событие b p должно быть выполнено так, чтобы выполнение a q произошло по времени раньше, чем любое событие из b p.

Вычисление функций точной нижней грани (INF-алгоритм) Пусть (X, ) частично упорядоченное множество. Тогда элемент c называется точной нижней гранью элементов a и b, если c a, c b и d: (d a d b d c). X обладает тем свойством, что точная нижняя грань всегда существует. В таком случае эта точная нижняя грань определяется однозначно. Все процессы q наделены входными данными j q. Они являются элементами частично упорядоченного множества X. Нужно, чтобы некоторые выделенные процессы вычислили значение inf{j p : q P}. И эти процессы должны быть осведомлены о завершении вычисления. Они записывают результат вычисления в переменной out, и им не разрешается впоследствии изменять значение этой переменной. Запись значения в переменную out, рассматривается как событие decide в INF-алгоритме.

Кольцевой алгоритм Для инициатора: begin send tok to Next p ; receive tok ; decide end Для не инициатора: begin receive tok ; send tok to Next p end

Древесный алгоритм var rec p [q] for each q Neigh p : boolean init false /* rec p [q] принимает значение true, если p уже получил сообщение от q */ begin while #{q : rec p [q] = false} > 1 do begin receive from q; rec p [q] := true end; /* Теперь есть единственный q 0, для которого rec p [q 0 ] имеет значение false */ send to q 0 with rec p [q 0 ] = false; x: receive from q 0 ; rec p [q 0 ] := true ; decide /* Оповестить другие процессы о решении: forall q Neigh p, qq 0 do send to q */ end

Алгоритм эха var rec p : integer init 0; /* Подсчет числа полученных сообщений */ father p : P init undef ; Для инициатора: begin forall q Neigh p do send to q ; while rec p < #Neigh p do begin receive ; rec p := rec p +1 end; decide end Для не инициатора: begin receive from neighbor q; father p := q ; rec p := rec p + 1 ; forall q Neigh p, q father p do send to q ; while rec p < #Neigh p do begin receive ; rec p := rec p + 1 end; send to father p end

Алгоритм опроса var rec p : integer init 0 ; /* только для инициатора */ Для инициатора: begin forall q Neigh p do send to qf ; while rec p < #Neigh p do begin receive ; rec p := rec p + 1 end; decide end Для не инициатора: begin receive from q ; send tok to q end

Фазовый алгоритм (общий случай) cons D: integer = диаметр сети ; var Rec p [q] : 0..D init 0 для каждого q In p ; /* Число сообщений, полученных от q */ Sent p : 0..D init 0 ; /* Число сообщений, отправленных каждому соседу на выходе */ begin if p is initiator then begin forall r Out p do send to r ; Sent p := Sent p + 1 end; while min q Rec p [q] < D do begin receive (from neighbor q 0 ) ; Rec p [q 0 ] := Rec p [q 0 ] + 1 ; if min q Rec p [q] Sent p and Sent p < D then begin forall r Out p do send to r ; Sent p := Sent p +1 end end; decide end

Фазовый алгоритм для клик varRec p : 0..N-1init 0 ; /* Число полученных сообщений */ Sent p : 0..1 init 0 ; /* Число сообщений, отправленных каждому соседу */ begin if p is initiator then begin forall r Neigh p do send to r ; Sent p := Sent p + 1 end; while Rec p < #Neigh p do begin receive Rec p := Rec p +1 ; if Sent p = 0 then begin forall r Neigh p do send to r ; Sent p := Sent p +1 end end; decide end

Алгоритм Финна var Inc p : set of processes init {p}; NInc p : set of processes init ; rec p [q] : bool for q In p init false ; /* индикаторы получения процессом p сообщения от q */ begin if p is initiator then forall r Out p do send to r ; while Inc p NInc p do begin receive from q 0 ; Inc p := Inc p Inc ; NInc p := NInc p NInc ; rec p [q 0 ] := true ; if q In p : rec p [q] then NInc p := NInc p {p}; if Inc p or NInc p has changed then forall r Out p do send to r end; decide end

Алгоритмы обхода Определение. Алгоритмом обхода называется алгоритм, обладающий следующими тремя свойствами. – 1. В каждом вычислении есть единственный инициатор, который запускает алгоритм, отправляя одно-единственное сообщение. – 2. Всякий процесс после получения сообщения либо отправляет ровно одно сообщение, либо принимает решение. Как следует из первых двух свойств, в каждом конечном вычислении в точности один процесс принимает решение. Говорят, что алгоритм завершает работу в том единственном процессе, который принимает решение. – 3. Алгоритм завершает работу в инициаторе, и к тому моменту, когда это происходит, каждому процессу хотя бы один раз удалось отправить сообщение.

Обход клик var rec p : integer init 0; /* только для инициатора*/ Для инициатора: /* Записать Neigh p ={q 1, q 2,..., q N1 }*/ 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

Обход торов Для инициатора, выполнить один раз: send to Up Для каждого процесса после приема маркера : begin if k = n 2 then decide else if n|k then send to Up else send to Right end

Обход гиперкубов Для инициатора выполнить один раз: send по каналу n - 1. Для каждого процесса после приема маркера : begin if k = 2 n then decide else begin let l - наибольшее такое число, что 2 l |k ; send по каналу l end

Обход связных сетей (алгоритм Тарри) var used p [q] : bool init false for each q Neigh p ; /* Показывает, отправлял ли p сообщение процессу q */ father p : process init undef ; Только для инициатора, выполнить один раз: begin father p := p ; choose q Neigh p ; used p [q] := true ; send tok to q end Для каждого процесса после приема tok от q 0 : begin if father p = undef then father p := q 0 ; if q Neigh p : used p [q] then decide else if q Neigh p : (q father p ¬used p [q]) then begin choose q Neigh p \{father p } with ¬used p [q] ; used p [q] := true ; send tok to q end else begin used p [father p ] := true ; send tok to father p end end

Поиск в глубину Определение. Корневое остовное дерево T сети G называется деревом поиска в глубину, если для каждого стягивающего ребра pq выполняется соотношение q T[p] q A[p]. Деревья поиска в глубину применяются во многих графовых алгоритмах, наподобие проверки планарности, проверки двусвязности, построения интервальных схем разметки.

Распределенный поиск в глубину var used p [q] : bool init false for each q Neigh p ; /* Указывает, отправлял ли p маркер процессу q */ father p : process init undef ; Только для инициатора, выполнить один раз: begin father p := p ; choose q Neigh p ; used p [q] := true ; send tok to q end Для каждого процесса, при получении tok от q 0 : begin if father p = undef then father p := q 0 ; if q Neigh p : used p [q] then decide else if q Neigh p : (qfather p ¬used p [q]) then begin if father pq 0 ¬used p [q 0 ] then q := q 0 else choose q Neigh p \{father p } with ¬used p [q]) ; used p [q] := true ; send tok to q end else begin used p [father p ] := true ; send tok to father p end end

Алгоритм Авербаха var used p [q] : bool init false for each q Neigh p ; /*Указывает, отправлял ли p маркер процессу q*/ father p : process init undef ; Только для инициатора, выполнить один раз: begin father p := p ; choose q Neigh p ; forall r Neigh p do send to r ; forall r Neigh p do receive from r ; used p [q] := true ; send to q end Для каждого процесса после получения от q 0 : begin if father p = undef then begin father p := q 0 ; forall r Neigh p \{father p } do send to r ; forall r Neigh p \{father p } do receive from r end; if p is the initiator and q Neigh p : used p [q] then decide else if q Neigh p : (q father p ¬used p [q]) then begin if father p q 0 ¬used p [q 0 ] then q := q 0 else choose q Neigh p \{father p } with ¬used p [q] ; used p [q] := true ; send to q end else begin used p [father p ] := true ; send to father p end end Для каждого процесса после получения от q 0 : begin used p [q 0 ] := true ; send to q 0 end

Алгоритм Сидона (часть 1) var used p [q]: bool init false for each q Neigh p ; /* Указывает, отправлял ли p маркер процессу q */ father p : process init undef ; mrs p : process init undef ; Только для инициатора, выполнить один раз: beginfather p := p ; choose q Neigh p ; forall r Neigh p do send vis to r ; used p [q] := true ; mrs p := q ; send tok to q end Для каждого процесса после получения vis от q 0 : begin used p [q 0 ] := true ; if q 0 = mrs p then /* Истолковывать как сообщение tok */ forward tok message as upon receipt of tok message end

Алгоритм Сидона (часть 2) Для каждого процесса после получения tok от q 0 : begin if mrs p undef and mrs p q 0 /* Это стягивающее ребро, истолковывать как сообщение vis */ then used p [q 0 ] := true else(* Поступать, как в предыдущем алгоритме *) begin if father p = undef then begin father p := q 0 ; forall r Neigh p \{father p } do send vis to r end ; if p - инициатор and q Neigh p : used p [q] then decide else if q Neigh p : (q father p ¬used p [q]) then begin if father p q 0 ¬used p [q 0 ] then q := q 0 else choose q Neigh p \{father p } with ¬used p [q] ; used p [q] := true; mrs p := q ; send tok to q end else begin used p [father p ] := true; send tok to father p end end

Поиск в глубину с учетом сведений о соседях var father p : процесс init undef ; Только для инициатора, выполнить один раз: begin father p := p ; choose q Neigh p ; send to q end Для каждого процесса после получения от q 0 : begin if father p = undef then father p := q 0 ; if q Neigh p \L then begin choose q Neigh p \L ; send to q end else if p is initiator then decide else send to father p end

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

Вычисление сумм Вычисление суммы с помощью алгоритмов обхода: – процесс p обладает переменной j p – у маркера есть дополнительное поле s – s := s + j p ; j p := 0. Вычисление суммы при помощи остовного дерева: – Если процесс осведомлен о том, какое исходящее ребро ведет к родительской вершине в таком дереве, то само дерево можно использовать для вычисления сумм. – Каждый процесс отправляет своей родительской вершине в этом дереве сумму всех входных данных, вычисленных в своем поддереве. Вычисление сумм с использованием отличительных признаков: – каждый процесс наделен индивидуальным отличительным признаком. – каждый процесс помечает свои входные данные своим индивидуальным ярлыком, образуя пару (p, j p ) – множество S = {(p, j p ) : p P} является объединением множеств Sp = {(p, j p )} по всем p, и его можно вычислить по ходу одной волны. – на основе этого множества желаемый результат вычисляется с помощью локальных операций

Определение сложности по времени Сложностью по времени для распределенного алгоритма называется наибольшее время, которое требуется для выполнения произвольного вычисления этого алгоритма с учетом следующих допущений: – T1. Во всяком процессе любое конечное число событий может осуществиться мгновенно (за время 0). – T2. Период времени между отправлением и получением одного и того же сообщения не превышает одной единицы времени. Для заданного алгоритма его равномерная сложность по времени - это наибольшее время вычисления алгоритма при следующих допущениях: – O1. Процесс может выполнять любой конечный набор действий за нулевое время. – O2. Время между отправлением и приемом сообщения в точности равно одной единице времени.

Сложность по времени (компромисс) α-сложность по времени - определяется допущением о том, что задержка передачи каждого сообщения располагается между α и 1 (α - это константа, не превосходящая 1). Есть недостатки обоих компромиссных определений.

Определения на основе цепочек сообщений Цепочкой сообщений в C называется такая последовательность сообщений m 1, m 2,..., m k, что для каждого i, 0 i < k, прием сообщения m i предшествует в причинно-следственной связи отправлению сообщения m i+1. Цепной сложностью по времени распределенного алгоритма называется длина самой протяженной цепочки сообщений в произвольном вычислении указанного алгоритма.

Сложность по времени для алгоритма эха, влияние централизации на сложность по времени Обычная сложностьO(N) Равномерная сложностьO(D) α-сложностьO(min(N, D/α)) Цепная сложность (для фрагмента, в котором передается k сообщений) k ТопологияЦ/ДСложность КольцоЦN ДO(NlogN) ПроизвольнаяЦ2|E| ДO(NlogN + |E|) ДеревоЦ2(N-1) ДO(N)

Спасибо за внимание