Примитив «Соглашение об аккумулируемом множестве» (СОАМ-субпротокол)
Предположим, что каждый процессор инициализирует 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Í
Схема «Соглашение об аккумулируемом множестве»
Пусть 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. Пусть
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. <
