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

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


Предположим, что каждый процессор инициализирует Br-субпротокол с некоторым входным значением. Процессоры желают договориться об общем аккумулируемом множестве с не менее n-t процессорами, которые успешно завершили Br-субпротокол. Понятно, что каждый процессор может пожелать дождаться n-t локальных завершений

Br-субпротокола и сохранить «этих отправителей сообщений». Однако если более чем n-t завершений Br-субпротокола глобально осуществлены, тогда мы не можем быть уверены в том, что все несбоящие процессоры сохранят то же самое множество. Для этого необходимо всем процессорам выполнить СОАМ-субпротокол, в котором выход несбоящих процессоров этого субпротокола есть общее множество из не менее n-t процессоров, которые завершили Br-субпротокол.

Неформально говоря, выходы процессоров после выполнения

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

Определение3.1. Пусть m, MÎN (в данном контексте m=n-t

и M=n) и пусть U1...UnÍ[M] – коллекция аккумулируемых множеств такая, что процессор Pi

имеет Ui. Будем говорить, что коллекция является (m,t)-однородной, если для каждого планировщика и каждой коалиции из не более чем t

сбоящих процессоров выполняются следующие условия:

·     каждый несбоящий процессор Pi будет обязательно иметь êUiê³m;

·     каждых два несбоящие процессора Pi и Pj будут обязательно иметь Ui=Uj.

Определение 3.2. Пусть m, MÎN и пусть P - протокол, где вход каждого процессора Pi

есть аккумулируемое множество Ui. Протокол Р называется t-устойчивым СОАМ-субпротоколом для n процессоров (с параметрами n, M), если для каждого планировщика и каждой коалиции из не более чем t сбоящих процессоров выполняются следующие условия:




Условие завершения. Если коллекция 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.



2.   Выполнить в цикле r=ëlog nû

раз

2.1.    Послать (r,Ui) всем другим процессорам;

2.2.    Пусть
={Pj, если (r,Sj) получено от Pj}. Ждет пока SjÍU i для не менее чем n-t процессоров PjÎFir.

3. Выполняет M раз BA-субпротокол BA1...BAM, где вход 1 в j-том выполнении субпротокола, тогда и только тогда, когда jÎUi.

4. Устанавливает Ci={j, если выход BAj равен 1}. Ждет пока CiÍUi.

5. Выдает Ci.

 

Предложение 3.2. Протокол СОАМ – является min(r,(én/3ù-1))-устойчивым протоколом для сети из n

процессоров, где r – граница устойчивости для используемого протокола соглашений.

Доказательство.

Сначала докажем условие завершения. Предположим, что аккумулируемые множества U1,...,Un определяют (m,t)-однородную коллекцию. Покажем, что каждый несбоящий процессор Pi будет событийно завершать протокол.

Замечание.

Напомним, что в асинхронных моделях выполнение каждой конкретной операции начинается сразу после приема сигнала об окончании предыдущей операции, т.е. после наступления некоторого события, не обязательно привязанного к работе синхронизатора. Такая операция (действие) здесь и далее будет называться событийной (событийным).

Шаг 1 будет завершен в любом случае. Индукция по числу итераций показывает, что шаг 2 будет также завершен. В каждой итерации r процессор Pi будет событийно получать сообщение (r,Sj) от каждого несбоящего процессора. Кроме того, для каждого процессора Pj

процессор будет событийно иметь SjÍUi (так как система U1,...,Un является однородной). Шаг 3 будет завершен с вероятностью 1, так как все протоколы византийских соглашений завершаются с вероятностью 1. Чтобы доказать, что шаг 4 будет также завершен, необходимо отметить, что если BA-субпротокол выдает 1, тогда существует несбоящий процессор Pk, который запускает BAj-протокол, где jÎUk



и, таким образом, процессор Pi будет событийно иметь jÎUi.

Доказательство свойства корректности начинается со следующего. Согласование выходов процессоров непосредственно следует из определения византийских соглашений. Шаг 4 протокола гарантирует, что CÍUi* для каждого несбоящего процессора Pi.

В заключение необходимо показать, что ÷C÷³m. Пусть Uir обозначает значение аккумулируемого множества Ui по окончании r-ой итерации на шаге 2 при функционировании процессора Pi. Покажем индукцией по r, что каждое множество D из не более чем 2r несбоящих процессоров, которые завершили итерацию r, удовлетворяет ÷ÇjÎDUjr÷³m. Основание индукции (r=0) следует непосредственно из шага 1 протокола. Для шага индукции рассмотрим множество D из не более чем 2r несбоящих процессоров. Отметим, что для каждых двух процессоров Pj,PkÎD имеем ôFjrÇFkrô³t+1, где n³3t+1 и ôFjrô³n-t для каждого j. Поэтому существует не менее одного несбоящего процессора PlÎ FjrÇFkr. Процессор Pl будем называть арбитром Pj

и Pk. Процессор Pj (в отн. Pk) получает сообщение (r,Sl). Кроме того,

Ulr-1ÍSl. Таким образом, Ulr-1ÍUjr (в отн. Ulr-1ÍUkr).

Рассмотрим независимое деление множества D на две части, выберем арбитра для каждой пары и пусть D¢

является множеством этих арбитров. Таким образом, получим ÷D¢÷£2r-1. По индукции имеем  m£÷ÇjÎD¢Ujr-1÷. Каждый процессор из D имеет арбитр из D¢ и, таким образом,

ÇjÎD¢Ujr-1ÍÇjÎDUjr. Отсюда, m£÷ÇjÎDUjr÷.

Пусть D – множество несбоящих процессоров, которые начинают работу на шаге 3 протокола и пусть C¢=ÇjÎDUjlog n. По индукции получим ÷C¢÷³m.Для каждого jÎC выходы всех несбоящих процессоров в

BAj-субпротоколах являются 1. По этому по определению византийских соглашений выход каждого BAj-субпротокола является 1. Таким образом, C¢ÍC и C³m.  <


Содержание раздела