Теория и практика защиты программ



         

Примитив «Соглашение об аккумулируемом множестве» (СОАМ-субпротокол) - часть 2


Условие завершения. Если коллекция U1...Un (m,t)-однородна, тогда с вероятностью 1 все несбоящие процессоры обязательно завершат протокол.

Условие корректности. Все несбоящие процессоры завершат протокол с общим выходом CÍ[M] так, что êCê³m. Кроме того, каждый несбоящий процессор имеет CÍ

, где
 значение Ui при завершении протокола.

Схема «Соглашение об аккумулируемом множестве»

Пусть n³3t+1. Субпротокол СОАМ состоит из 2-х этапов (с параметрами m

и M). На первом этапе каждый процессор сначала ждет пока его динамический вход станет размером m. После чего, он выполняет log2 n итераций. В каждой итерации процессор посылает текущее содержание его динамического входа всем другим процессорам, после чего собирает множества, посланные другими процессорами в текущей итерации. Как только накопятся n-t таких множеств в динамическом входе процессора, он приступает к следующей итерации. Это продолжается до тех пор, пока пересечение динамических входов всех несбоящих процессоров, которые получены во всех log2 n

итерациях станет размером не менее m.

На втором этапе процессоры последовательно запускают M раз BА-субпротокол. На j-том шаге процессоры решают, принадлежит ли элемент jÎ[M] согласованному множеству C. То есть вход каждого процессора на j-том шаге BА-субпротокола будет 1 тогда и только тогда, когда j принадлежит динамическому входу процессора. Элемент j принадлежит множеству C тогда и только тогда, когда общий выход j-того шага BА-субпротокола является 1. Свойства BА-субпротокола гарантируют нам, что множество C

содержит пересечение динамических входов всех процессоров, которые получены при завершении первого этапа, и что каждый элемент jÎC

будет в динамическом входе каждого несбоящего процессора.

Протокол СОАМ

Процессор Pi выполняет следующие шаги по входу m, M и аккумулируемому множеству Ui.

1.   Ожидает пока êUiê³m.




Содержание  Назад  Вперед