Широковещательный примитив (Br-протокол)
Введем следующее определение. Протокол называется t-устойчивым широковещательным протоколом, если он инициализирован специальным участником (дилером Д), имеющим вход m (сообщение, предназначенное для распространения) и для каждого входа и коалиции нечестных участников (числом не более t) выполняются условия.
Условие завершения. Если дилер Д - честный, то все честные участники обязательно завершат протокол. Кроме того, если любой честный участник завершит протокол, то все честные участники обязательно завершат протокол.
Условие корректности. Если честные участники завершат протокол, то они сделают это с общим выходом m*. Кроме того, если дилер честный, тогда m*=m.
Необходимо подчеркнуть, что свойство завершения является более слабым, чем свойство завершения в византийских соглашений (см. далее). Для Br-протокола не требуется, чтобы честные участники завершали протокол, в том случае, если дилер нечестен.
Br-протокол
Код для дилера (по входу m):
1. Послать сообщение (сбщ,m) всем участникам и завершить протокол с выходом m.
Код для участников:
2. После получения первых сообщений (сбщ,m) или (эхо,m), послать (эхо,m) ко всем участникам и завершить протокол с выходом m.
Предложение 3.1. Br-протокол является n-усточивым широковещательным протоколом для противников, которые могут приостанавливать отправку сообщений.
Доказательство.
Если дилер честен, то все честные участники получают сообщение (сбщ,m) и, таким образом, завершают протокол с выходом m. Если честный участник завершил протокол с выходом m, то он посылает сообщение (эхо,m) ко всем другим участникам и, таким образом, каждый честный участник завершит протокол с выходом m.
Ниже описывается ë(n-1)/3û-устойчивый широковещательный протокол, который именуется BB, где t£ë(n-1/3)û - количество участников, которые могут быть нечестными. В протоколе принимается, что идентификатор дилера содержится в параметре m.
Протокол BB
Код для дилера (по входу m):
1. Послать сообщение (сбщ,m) ко всем участникам.
Код для участника Pi:
2. После получения сообщения (сбщ,m), послать сообщение (эхо,m) ко всем участникам.
3. После получения n-1 сообщений (сбщ,m¢), которые согласованы со значением m¢, послать сообщение (гот,m¢) ко всем участникам.
4. После получения t+1 сообщений (гот,m¢), которые согласованы со значением m¢, послать (гот,m¢) ко всем участникам.
5. После получения n-1 сообщений (сбщ,m¢), которые согласованы со значением m¢, послать сообщение (OK,m¢) ко всем участникам и принять m¢ как распространяемое сообщение.
