Быстрый поиск

Реферат: Распределенные алгоритмы

(1) T пусто или T - направленное дерево с корнем p0.

(2) Множество VT включает все активные процессы и все основные сообщения, находящиеся в процессе передачи.

Инициатор p0 вызывает алгоритм объявления когда p0 Ï VT согласно первому свойству, T пусто в этом случае, и согласно второму свойству, предикат term принимает значение истина .

Для сохранения свойств дерева вычислений во время выполнения основного вычисления, T должно расширятся при отправке основного сообщения или при переходе процесса, не принадлежащего дереву, в активное состояние. Когда p посылает основное сообщение (mes), (mes) вставляется в дерево, и отцом (mes) является p. Когда процесс p, не принадлежащий дереву, становится активным получая сообщения от q, q становится отцом p. Для того, чтобы представить отправителя сообщения явно, основное сообщение (mes) послаемой q будем обозначать (mes, q).

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

var statep : (active, passive) init if p = p0 then active else passive;

sсp : integer init 0;

fatherp : P init if p == p0 then p else udef ;

Sp: { statep = active }

begin send (mes, p) ; scp := scp + 1 end

Rp: { сообщение (mes, q) прибывает в p }

begin receive (mes, q);, statep := active;,

if fatherp = udef then fatherp := q else send ( sig, q ) to q

end

Ip: { statep = active }

begin statep := passive ;

if scp = 0 then (* Удаляем p из T *)

begin if fatherp = p then Announce else send (sig , fatherp) to fatherp ;

fatherp := udef

end

Ap: { Сигнал (sig ,p) прибывает в p }

begin receive (sig,p) ; scp := scp -1 ;

if sc p = 0 and statep = passive then

begin if fatherp = p then Announce else send ( sig, fatherp ) to fatherp ;

fatherp := udef

end

Алгоритм 8.3 dijkstra-scholten алгоритм.

Сообщения - листья T; процессы поддерживают переменную, которая считает число их сыновей в T. Удаление сына процесса p происходит в другом процессе q; это происходит при получении сообщения сына или удалении сына процесса q. Для того, чтобы предотвратить искажение данных счетчика сына p, процессу p посылается сигнальное сообщение (sig, p) об удалении его сына. Это сообщение заменяет удаленного сына p, и его удаление, т.е. получение, происходит в процессе p и p при получении сигнала уменьшает на единицу счетчик сыновей.

Алгоритм описан как Алгоритм 8.3. Каждый процесс p имеет переменную fatherp, которая не определена если pÏVT , равна p если p является корнем, и является отцом p, если p - не корень в T. Переменная scp содержит число сыновей p в T.

Доказательство правильности строго устанавливает, что граф T, как определено, является деревом и что он становится пустым только после завершения основного вычисления. Для любой конфигурации g Алгоритма 8.3, определено

VT = {p : fatherp ¹ udef} È {передается (mes,p) } È {передается ( sig,p) }

ET = {(p, fatherp) : fatherp ¹ udef Ù fatherp ¹ p}

È { ((mes, p), p) : (mes, p) передается }È{((sig,p), p) : (sig, p) передается }.

Безопасность алгоритма следует из утверждения P, определенного следующим образом

P º statep = active Þ p Î Vp (1)

Ù (u, v) Î ET Þ u ÎVT Ù v Î VT Ç P (2)

Ù scp = #{v : (v, p) ÎET } (3)

Ù VT ¹ Æ Þ T дерево с корнем p0 (4)

Ù (statep = passive Ù scp = 0) Þ p Ï VT (5)

Значение этого инварианта следующие. По определению, множество узлов T включает все сообщения (основные и управляющие), и согласно пункту (1) оно также включает все активные процессы. Пункт (2) скорее технический; он заявляет, что T - действительно граф, и все ребра направлены к процессам. Пункт (3) выражает правильность счетчика сыновей каждого процесса, и пункт (4) заявляет, что T - дерево, и p0 - корень. Пункт (5) используется, чтобы показать, что дерево действительно разрушается, если основное вычисление заканчивается. Для доказательства правильности, обратите внимание, что из P следует, что fatherp = p только для p = p0.

Lemma 8.4 P - инвариант Dijkstra-Scholten алгоритма.

Доказательство. Первоначально statep = passive для всех p ¹ p0 и fatherp0 ¹ udef, который доказывает пункт (1). Также, ET = Æ, что доказывает (2). Так как scp = 0 для каждого p, удовлетворяется (3). VT = {po} и ET = Æ, таким образом T - дерево с корнем p0, что доказывает (4). Единственный процесс в VT - p0, и p0 активен.