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

       

Схема, корректирующая ошибки


Схема, корректирующая ошибки, работающая в префиксном режиме, обозначаемая в дальнейшем СКОП, позволяет каждому процессору вычислить полином p(·) степениd, удовлетворяющий p(j)=aj для каждого полученного им сообщения aj. А именно, процессор будет исследовать этот полином после получения сообщений от других процессоров и определять единственным образом интерполируемый полином степени d [BCG].

Определение 3.4.

Пусть d

и r

- целые числа и пусть множество SÍ[n]´F такое, что для каждых двух элементов (i,a) и (i¢,a¢ ) из S, получаем i=i¢. Будем считать, что S

является (d,r)-интерполируемым, если существует полином p(·) степени d такой, что не более r элементов (i,a)ÎS не удовлетворяет p(a)=e. Будем говорить, что p(·) является (d,r)-интерполируемым полиномом множества S.

Определение 3.1.

Пусть I – аккумулируемое множество (см. выше). Тогда I называется событийно (d,r)-интерполируемым, если для каждого планировщика, каждой коалиции из не более чем t сбоящих процессоров и каждого запуска алгоритма существует целое число 0£r£t

такое, что I будет событийно содержать (d,r)-интерполируемое множество мощностью не менее d+t+r+1.

При использовании этих обозначений динамический вход процедуры, описываемой ниже, является (d,t)-интерполируемым аккумулируемым множеством I. Требуемый выход этой процедуры является

(d,t)-интерполируемым полином множества I. Определение 3.5 гарантирует, что, по крайней мере, d+t+1значений из I будут сопряжены с полиномом степени t. По крайней мере t+1 из них соответствуют несбоящим процессорам. Следовательно, (d,t)-интерполируемый полином множества I определен значениями несбоящими процессорами.

Процедура СКОП состоит из t+1 итераций. На итерации r процессор ожидает, пока мощность аккумулируемого множества I станет не менее d+t+r+1.


Затем, каждый процессор запускает ниже описываемую процедуру, которая определяет, является ли множество I - (d,r)-интерполируемым и вычисляет соответствующий интерполируемый полином. Если

(d,r)-интерполируемый полином найден, тогда оно подается на выход и работа завершается. В противном случае, мы переходим к итерации r+1 (так как I – является событийно интерполируемым, он ограничен, по крайней мере, еще одним элементом и, таким образом, итерация r+1 будет завершена).

Далее описывается, как определить, является ли данное множество (d,r)-интерполируемым и как вычислять интерполируемый полином, используя теорию кодирования. Рассмотрим следующий код. Слово W=(i1,a1)...(il,al) является ключевым, тогда и только тогда, когда существует полином p(·) степени d такой, что p(ij)=aj для каждый 1£j£l. Такой код является обобщенным кодом Рида-Соломона, имеющим эффективную процедуру, корректирующую ошибки. Данная процедура обнаруживает и исправляет не менее r

ошибок во входном слове W, где ½W½³d+2r+1 (см., например, [КС]).

Пусть ПКО обозначает следующую процедуру. А именно, пусть S - (d,r)-интерполируемое множество мощностью не менее d+2r+1. Тогда процедура ПКО по входу (d,r,S), выдает (d,r)-интерполируемый полином из множества S.

Процедура СКОП

Выполняется в t циклах по r.

1.     Пусть Ir

определяет содержимое аккумулируемого множества I, где I содержит d+t+r+1 элементов.

2.     Ожидать пока ½I½³d+t+r+1. Тогда, запустить процедуру ПКО со входом (d,r,Ir), и пусть p(·) – выходной полином.

3.     Если p(·) - (d,r)- интерполируемый полином Ir (а именно, если для d+t+1 элементов (i,a)ÎIr, мы имеем p(i)=a), выдать p(·). В противном случае, перейти к следующей итерации.

Предложение 3.5.

Пусть I – событийно (d,t)-интерполируемое аккумулируемое множество.Тогда процедура СКОП

останавливается и выдает (d,t)-интерполируемый полином множества I.

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

Пусть r¢, являющийся наименьшим из r, такой, что Ir¢

является (d,Ir¢)-интерполируемым. Так как I – является событийно (d,t)-интерполируемым, то r¢£t. Все итерации вплоть до r¢ будут неудачно завершены. Тогда (d,t)-интерполируемый полином I будет найден на итерации r¢.        <


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