Безопасность асинхронных вычислений

Сначала напомним, что как и сбоящие процессоры, так и планировщик имеют неограниченную вычислительную мощность.

Для вектора

 и множества CÍ[n]@{1,...,n}, пусть  определяет вектор , спроектированный на индексы из C. Для подмножества BÍ[n] и вектора , пусть  определяет вектор, полученный из  подстановкой входов из B соответствующими входами из . Используя эти определения, можно определить оценочную функцию f с базовым множеством CÍ[n] как @.

Пусть A – область возможных входов процессоров и пусть R

– область случайных входов. ТР-противник

это кортеж А=(B,h,c,O), где BÍ[n] – множество сбоящих процессоров, h:AïBï´R®AïBï - функция подстановки входов, с:AïBï´R®{CÍ[n]½ôCô³n-t} – функция выбора базового множества и O:AïBï´R´A®{0,1}* - функция выхода для сбоящих процессоров.

Функции h

и O представляют собой программы сбоящих процессоров, а функция c – комбинацию планировщика и программ сбоящих процессоров.

Пусть f:An®A для некоторой области A. Выход функции вычисления f в ТР-сценарии по входу

 и с ТР-противником А=(B,h,c,O) – это

n-размерный вектор 

=... случайных переменных, удовлетворяющих для каждого 1£i£n:

=       ,

где r - объединенный случайный вход сбоящих процессоров, C=

 и

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

Далее формализуем понятие вычисления «в реальной жизни».

1. Пусть B=(B,b) – коалиция нечестных процессоров, где BÌ[n] – множество нечестных процессоров и b

- их совместная стратегия.

2. Пусть pi(

,B,D) определяет выход процессора Pi

после выполнения протокола pi по входу

, с планировщиком D и коалиции B. Пусть также P(,B,D)=p1(,B,D)...pn(,B,D).

Кроме того, пусть f:An®A для некоторой области A и пусть P

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

Условие завершения (условие полноты).

По всем входам все честные процессоры завершают протокол с вероятностью 1.

Условие безопасности. Существует ТР-противник A такой, что для каждого входа  векторы t(,A) и P(,B,D) идентично распределены (эквивалентны).


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

---