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



         

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


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

раз

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

2.2.    Пусть

={Pj, если (r,Sj) получено от Pj}. Ждет пока SjÍUi для не менее чем 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




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