Протокол соам

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

1. Ожидает пока U_im.

2. Выполнить в цикле r=log nраз

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

   2. Пусть ={P_j, если (r,S_j) получено отP_j}. Ждет покаS_jU_iдля не менее чемn-tпроцессоровP_jF_i^r.

3. Выполняет MразBA-субпротоколBA₁...BA_M, где вход 1 вj-том выполнении субпротокола, тогда и только тогда, когдаjU_i.

4. Устанавливает C_i={j, если выходBA_jравен 1}. Ждет покаC_iU_i.

5. Выдает C_i.

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

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

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

Шаг 1 будет завершен в любом случае. Индукция по числу итераций показывает, что шаг 2 будет также завершен. В каждой итерации rпроцессорP_iбудет событийно получать сообщение (r,S_j) от каждого несбоящего процессора. Кроме того, для каждого процессораP_jпроцессор будет событийно иметьS_jU_i(так как системаU₁,...,U_nявляется однородной). Шаг 3 будет завершен с вероятностью 1, так как все протоколы византийских соглашений завершаются с вероятностью 1. Чтобы доказать, что шаг 4 будет также завершен, необходимо отметить, что еслиBA-субпротокол выдает 1, тогда существует несбоящий процессорP_k, который запускаетBA_j-протокол, гдеjU_kи, таким образом, процессорP_iбудет событийно иметьjU_i.

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

В заключение необходимо показать, что Cm. ПустьU_i^rобозначает значение аккумулируемого множестваU_iпо окончанииr-ой итерации на шаге 2 при функционировании процессораP_i. Покажем индукцией поr, что каждое множествоDиз не более чем 2^rнесбоящих процессоров, которые завершили итерациюr, удовлетворяет_jDU_j^rm. Основание индукции (r=0) следует непосредственно из шага 1 протокола. Для шага индукции рассмотрим множествоDиз не более чем 2^rнесбоящих процессоров. Отметим, что для каждых двух процессоровP_j,P_kDимеемF_j^rF_k^rt+1, гдеn3t+1 иF_j^rn-tдля каждогоj. Поэтому существует не менее одного несбоящего процессораP_l F_j^rF_k^r. ПроцессорP_lбудем называтьарбитромP_jиP_k. ПроцессорP_j(в отн.P_k) получает сообщение (r,S_l). Кроме того,U_l^r-1S_l. Таким образом,U_l^r-1U_j^r(в отн.U_l^r-1U_k^r).

Рассмотрим независимое деление множества Dна две части, выберем арбитра для каждой пары и пустьDявляется множеством этих арбитров. Таким образом, получимD2^r-1. По индукции имеемm_jDU_j^r-1. Каждый процессор изDимеет арбитр изDи, таким образом,_jDU_j^r-1_jDU_j^r. Отсюда,m_jDU_j^r.

Пусть D– множество несбоящих процессоров, которые начинают работу на шаге 3 протокола и пустьC=_jDU_j^log n. По индукции получимCm. Для каждогоjCвыходы всех несбоящих процессоров вBA_j-субпротоколах являются 1. По этому по определению византийских соглашений выход каждогоBA_j-субпротокола является 1. Таким образом,CCиCm.

3. Схема (n,t)-звезды

Пусть OK_i-граф – это неориентированный граф с вершинами [n], где ребро (j,k) существует тогда и только тогда, когда процессорP_iзавершил распространение двух сообщений (OK,j,k), инициированноеP_jи (OK,k,j), инициированноеP_k.

Определение 3.3.ПустьG- граф с вершинами [n]. Тогда пара множеств (C,D) такая, чтоCD[n] является (n,t)-звездой вG, если выполняются следующие условия:

• Cn-2tиDn-t;

• для каждого jCи для каждогоkDвGсуществует ребро (j,k).

Процессор P_iполучает доступ к разделенному секрету, когда находит звезду поOK_i-графу. Лемма 3.5 (см. далее) реализует, что еслиn4t+1, доли несбоящих процессоров в звездеOK_i-графа, определяют единственным образом полином степениtот двух переменных. Лемма 3.6. говорит о том, что полиномы, определенные звездами для каждой из двух сторон равны. Таким образом, только несбоящие процессоры могут найти звезду, определяющую уникальный секрет.

В принципе, можно было бы допустить процессор, ждущий клику размера n-tвзамен звезды. Если дилер честен, тоOK_i -граф будет иметь такую клику. Однако задача нахождения клики максимального размера являетсяNP-полной задачей. Поэтому стороны будут пытаться найти (n,t)-звезду.

Кроме того, необходимо удостовериться, что если несбоящий процессор находит звезду по OK-графу, то все несбоящие процессоры найдут звезду, даже если дилер нечестен иOK-граф не содержит клики. После получения сообщения (OK,^,^) процессор, который не нашел звезду проверяет какая из предложенных звезд является звездой дляOK-графа. Отметим, что ребро вOK-графе для несбоящего процессора будет, в конечном счете, ребром вOK-графе для каждого несбоящего процессора (так как все сообщения (OK,^,^) распространяются посредствомBr-субпротокола. Таким образом, звезда вOK-графе некоторого несбоящего процессора будет в конечном счете звездой вOK-графе любого другого несбоящего процессора.

Далее описывается процедура нахождения (n,t)-звезды в графе сnвершинами (см. определение 3.3), где граф содержит клику размераn-t. А именно, нижеописываемая процедураЗВЗ, в качестве выхода выдает либо звезду в графе, либо выдает сообщение «звезда не найдена». Как только граф содержит клику размераn-t, процедура выдает звезду в графе. Аналогичная процедура описана в [ГДж].

Алгоритм работает следующим образом. Сначала находится максимальное паросочетание в комплиментарном графе и выдается множество несравнимых вершин. (Паросочетание в графе – это произвольное подмножество попарно несмежных ребер. Паросочетание является максимальным, если оно не содержится в паросочетании с большим числом ребер [Ле]. Комплиментарный граф – это граф, в котором ребро существует тогда и только тогда, когда оно не существует в оригинальном графе).

Выход алгоритма является независимым множеством в комплиментарном графе и, таким образом, формируется клика в оригинальном графе. Кроме того, если граф содержит клику размера n-k, тогда максимальное паросочетание в комплиментарном графе включает не болееkребер и 2k вершин. Далее описание алгоритма ведется в терминах комплиментарного графа. Если входной граф имеет независимое множество мощностьюn-t, находится множестваCDвершин, такие, чтоCn-2tDn-tи не существует ребер между вершинами изCи вершинами изCD. Эта пара множеств будет называться -звездой. Далее находится максимальное паросочетание в графе (см., например, [Ал, стр.18]).

На основе этого паросочетания вычисляются множества CиDвершин, и проверяется, формирует ли пара (C,D) -звезду в графе. Если входной граф содержит независимое множество мощностьюn-t, тогда полученные множестваCиDформируют -звезду в входном графе.

Далее показывается, как вычисляются множества CиD. Вершина называетсятрехглавой, если она не входит в паросочетание и две ее соседние вершины являются парой паросочетаний (а именно, ребро между этими двумя соседними вершинами являются паросочетанием). Пусть C- множество вершин, которые не являются трехглавыми иB- множество вершин, которые имеют соседние вершины изCи пустьD=[n]-B.