Реферат: Распределенные алгоритмы
Применимость действия означает, что p, отец нового узла (mes, p), находится в VT, что доказывает, что (2) сохраняется. В результате действия, VT дополняется узлом (mes, p) и ET дугой ((mes, p), p), что означает, что T остается деревом, и scp правильно увеличивается, чтобы представить нового сына p, следовательно (3) и (4) сохраняются.
Никакой процесс не становится пассивным листом, и никакой процесс не вставлен в VT , таким образом (5) сохраняется.
Rp: Или p уже был в VT (fatherp ¹ udef) или p вставлен в VT после действия, таким образом (1) сохраняется.
Если значение fatherp определено, его новое значение - q, и если сигнал послан процессом p, его отец - также q, и q находится в VT, таким образом (2) сохраняется. Число сыновей q не изменяется, потому что сын (mes, q) процесса q заменяется сыном p или сыном (sig, q), так что scq остается правильным, который сохраняет (3).
Структура графа не изменяется, таким образом (4) сохраняется. Процесс p находится в VT после действия в любом случае, таким образом (5) сохраняется.
Ip: Переход p в пассивное состояние сохраняют (1), (2), (3) и (4). Из того, что p был прежде активен следует, что p был в VT. Если scp = 0, p удаляется из VT, таким образом (5) сохраняется.
Затем мы рассматриваем что случится при удалении p из T, то есть, если p окажется пассивным листом T.
Если сигнал посылается процессом p, отец сигнала - последний отец p, который находится в VT, следовательно (2) сохраняется. В этом случае, сигнал заменяет p как сын процесса fatherp, следовательно fatherfather p остается правильным, и (3) сохраняется. Структура графа не изменилась, следовательно (4) сохраняется.
Иначе, то есть, если fatherp = p, p = p0 и p, являющийся листом, означает, что p был единственным узелом T, так что удаление опустошает T , что сохраняет (4).
Ap: Получение сигнала уменьшает число сыновей p на единицу, и присваивание значения на scp гарантируетсохранение (3). То, что p был отецом сигнала, означает, что p был в VT. Если statep = passive и после получения scp присваивается 0, p удаляется, таким образом сохраняется (5). Если p удаляется из VT, инвариант сохраняется по тем же причинам, что и для действия Ip. o
Теорема 8.5 Dijkstra-Scholten алгоритм (Алгоритм 8.3) - правильный алгоритм обнаружения завершения и использует М управляющих сообщений.
Доказательство. Пусть S сумма всех счетчиков сыновей, то есть, S = SpÎ P sc p . Первоначально S = 0, S увеличивается на единицу при посылке основного сообщения (в Sp), S - уменьшается на единицу, когда получается управляющее сообщение (в Ap), и S никогда не становится отрицательным (из (3)). Это означает, что число управляющих сообщений никогда не превышает число основных сообщений в любом вычислении.
Чтобы доказать живость алгоритма, предположим, что основное вычисление закончилось. После завершения только действия Ap может иметь место и т.к. S уменьшается на единицу при каждом таком переходе, алгоритм достигает конечной конфигурации. Заметьте, что в этой конфигурации, VT не содержит никакие сообщения. Также, из (5), VT не содержит никаких пассивных листьев. Следовательно, T не имеет никаких листьев, что означает, что T пусто. Дерево стало пустым, когда p0 удалил себя, и программа такова, что p0 на этом шаге вызывает алгоритм объявления.
Чтобы доказать безопасность, обратите внимание, что только p0 вызывает алгоритм объявления, и делает это после того, как удаляет себя из VT. Из (4), T пусто, когда это случается,что заключает в себе term. o
Dijkstra-Scholten алгоритм достигает привлекательного баланса между передачей основных и управляющих сообщений; для каждого основного сообщения, посланного от p в q алгоритм посылает точно одно управляющее сообщение от q в p. Передача управляющих сообщений имеет нижнюю границу представленную в Теореме 8.2, так что алгоритм является оптимальным алгоритмом обнаружения завершения централизованных вычислений для худшего случая.
В описании этого подраздела, все сообщения содержат явное указание на их отца, но обычно это не является необходимым, потому что отец основных (управляющих) сообщений всегда их отправитель (адресат).
Dijkstra-Scholten алгоритм был обобщен для децентрализованных основных вычислений Shavit и Francez [SF86]. В их алгоритме, граф вычисления - лес, каждое дерево которого имеет в качестве корня инициатора основного вычисления. Дерево с корнем p обозначается Tp.
Алгоритм поддерживает граф F = (Vp , Ep), такой что (1) F является пустым или F - лес, каждое дерево которого имеет в качестве корня инициатора; (2) Vp включает все активные процессы и все основные сообщения. Как в алгоритме Dijkstra-Scholten завершении обнаруживается, когда граф становится пустым. К сожалению, в случае леса не так просто выяснить,является ли граф пустым. Действительно, свойство дерева вычислений иметь в качестве корня инициатора означает, что пустота дерева замечается корнем, который и вызывает алгоритм объявления. В случае леса, каждый инициатор замечает пустоту только собственного дерева, но это не означает, что весь леса пуст.
Проверка пустоты всех деревьев выполняется отдельной волной. Лес поддерживает дополнительное свойство, что если дерево Tp стало пустым, оно остается пустым и после этого. Обратите внимание, что это не мешает p стать активным; если p становится активным после разрушения дерева, p вставляется в дерево другого инициатора. Каждый процесс участвует в волне только, если его дерево разрушилось; когда волна принимает решение, вызывается алгоритм объявления. (вызов объявления не нужен, если выбранный волновой алгоритм генерирует решение в каждом процессе; в этом случае, процесс просто останавливается после принятия решения и завершения волнового алгоритма.)
Алгоритм дается как Алгоритм 8.4, в котором волновой алгоритм не показан явно. Каждый процесс p имеет переменную fatherp , которая не определена, если PÏVT, и равна p если p является корнем или равна отцу p, если p не-корень в F. Переменная sсp содержит число сыновей p в F. Логическая переменная empty истинна, тогда и только тогда, когда дерево p пусто.
Доказательство правильности алгоритма подобно доказательству Dijkstra-Scholten алгоритма. Для любой конфигурации g Алгоритма 8.4, определим
VF = {p : fatherp ¹ udef} U {передается (mes, p) } U {передается (sig,p) }
И
Ep = {(P, fatherp ): fatherp ¹ udef Ù fatherp ¹ p}
U {((mes, p), p) : (mes, p) передается } U {((sig,p}, p) : (sig,p} передается }.
Безопасность алгоритма будет следовать от утверждения Q, определенный ниже. Это инвариант алгоритма, и доказательство инвариантности подобно доказательству Lemma 8.4. Значение пунктов (1)-(5) из Q такие же как для инварианта алгоритма Dijkstra-Scholten и пункт (6) выражает тот факт, что каждый процесс правильно отслеживает,является ли он все еще корнем дерева в лесе. Конечно, лес пуст, если никакой процесс не является корнем.
Q Û statep = active Þ p Î VF (1)
Ù (u, v)Î EF Þ uÎ VF Ù v ÎVF Ç P (2)
Ù scp = #{ v : (v, p) Î Ep } (3)
Страницы: 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
