Общее описание модели
Ниже рассматривается модель вычислений, которая будет использоваться в дальнейших рассуждениях при исследовании синхронных конфиденциальных вычислений. Таким образом, рассматривается сеть процессоров, функционирование которой синхронизируется общими часами (синхронизатором). Каждое локальное (внутреннее) вычисление соответствует одному моменту времени (одному такту часов). В данной модели отрезок времени между i
и i+1 тактами называется раундом при синхронных вычислениях.
За один раунд протокола каждый процессор может получать сообщения от любого другого процессора, выполнять локальные (внутренние) вычисления и посылать сообщения всем другим процессорам сети. Имеется входная лента «только-для-чтения», которая первоначально содержит строку L(k) (например вида 1k), при этом k является параметром безопасности системы. Каждый процессор имеет ленту случайных значений, конфиденциальную рабочую ленту «только-для-чтения» (первоначально содержащую строку L), конфиденциальную входную ленту «только-для-чтения» (первоначально содержащую строку xi), конфиденциальную выходную ленту «только-для-записи» (первоначально содержащую строку L) и несколько коммуникационных лент. Между каждой парой процессоров i и j существует конфиденциальный канал связи, посредством которого i
посылает безопасным способом сообщение процессору j. Данный канал (коммуникационная лента) исключает запись для i
и исключает чтение дляj. Каждый процессор i
имеет также широковещательный канал, представляющий собой ленту, исключающую запись для i и являющийся каналом «только-для-чтения» для всех остальных процессоров сети.
Предполагается, что в раунде r
для каждого процессора i
существует однозначно определенное сообщение (возможно пустое), которое распространяет процессор i в этом раунде и для каждой пары процессоров i и j существует единственное сообщение, которое i может безопасным образом послать j
в данном раунде. Все каналы являются помеченными так, что каждый получатель сообщения может идентифицировать его отправителя.
Процессор i запускает программу pi, совокупность которых, реализует распределенный алгоритм P. Протоколом работы сети называется n-элементный кортеж P=(p1,p2,..,pn). Протокол называется t-устойчивым, если t процессоров являются сбоящими во время выполнения протокола. Историей
процессора i являются: содержание его конфиденциального и общего входов, все распространяемые им сообщения, все сообщения, полученные i по конфиденциальным каналам связи, и все случайные параметры, сгенерированные процессором i
во время работы сети.
будет равна R(п)=R=(1-Р)n.
Таким образом, можно дать следующее математическое определение надежности машинной программы: надежность программы - это вероятность безотказного выполнения п прогонов программы. Поэтому прогон является единичным испытанием программы.
На практике обычно выбор входных данных для каждого прогона нельзя считать независимым. Исключение составляют лишь такие последовательности прогонов, которые определяются возрастающими значениями и некоторой входной переменной или некоторым порядком установленных процедур, как в случае программ, работающих в реальном масштабе времени.
С учетом введенного определения функциональный разрез должен быть переопределен в терминах вероятностей pji выбора Ei в качестве входных данных при j-том прогоне из некоторой последовательности прогонов. Тогда вероятность того, что j-тый прогон закончится отказом, может быть записана в виде Pi=
Надежность R(п) программы П равна вероятности того, что в последовательности из п прогонов ни один из них не закончится отказом:
R(n)=(1-Pi)(1-P2)...(1-Pn)=
Эта формула может быть представлена в виде
Некоторые из свойств функции R(n) могут стать более зримыми при следующих допущениях:
для Pj<<1
если Pj=P для всех j, то
R(n)=
С помощью соответствующих замен переменных и подстановок можно выразить функцию R(n) через время функционирования t. Обозначим через Dtj
время выполнения j-того прогона, через
Если величина Dtj стремится к нулю с ростом n, то сумма в показателе экспоненты становится интегралом и формула для надежности программного обеспечения принимает вид
Эта формула хорошо известна в теории надежности технических устройств. В случае Pj<<1 функция h(tj) может быть интерпретирована как функция интенсивности отказов, которая, будучи умноженной на Dtj,
дает условную вероятность появления отказов и интервале (tj,tj+Dtj) при отсутствии отказов до момента tj.
