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









Пусть 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 в ТР-сценарии по входу

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





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


Акцентируем внимание на то, что выход сбоящих процессоров и выход несбоящих процессоров вычисляется на одном и том же значении случайного входаr.
Далее формализуем понятие вычисления «в реальной жизни».
1. Пусть B=(B,b) – коалиция нечестных процессоров, где BÌ[n] – множество нечестных процессоров и b
- их совместная стратегия.
2. Пусть pi(

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




Кроме того, пусть f:An®A для некоторой области A и пусть P
- протокол для n процессоров. Будем говорить, что P безопасно t-вычисляет функцию f в асинхронной модели для каждой коалиции B с не более, чем из t сбоящих процессоров, если выполняются следующие условия.
Условие завершения (условие полноты).
По всем входам все честные процессоры завершают протокол с вероятностью 1.
Условие безопасности. Существует ТР-противник A такой, что для каждого входа


