Распределенные алгоритмы

образом с конца раунда 3 каждый корректный процесс подтвердил H процессов,

что означает, что окончательное решение будет 1. (Командующий

поддерживается и подтверждается всеми корректными процессами одним

импульсом ранее других процессов.)

Если командующий корректен и имеет вход 0, он не “выкрикивает” в

импульсе 1, чего не делает и никакой другой корректный процесс.

Предположим, что никакой корректный процесс не инициировал в импульсах с 1

по i-1; тогда никакой корректный процесс не посылает в импульсе i.

В конце импульса i никакой корректный процесс не поддерживает и не

подтверждает никакого корректного процесса, так как, как мы видели ранее,

это подразумевает, что последний процесс послал сообщение .

Следовательно, никакой корректный процесс не инициирует в конце импульса i.

Отсюда следует, что никакой корректный процесс не инициирует вообще. Это

означает, что никакой корректный процесс никогда не подтверждает корректный

процесс, так что никакой корректный процесс не подтверждает более t

процессов, и решение в конечном импульсе - 0. (

Мы продолжим доказательством соглашения, и будем предполагать в следующих

леммах, что командующий сбойный. Достаточная "критическая масса" сообщений,

ведущая неизбежно к 1-решению, создается инициированием L корректных

процессов, когда имеется по крайней мере четыре импульса.

Лемма 14.7 Если L корректных процессов инициируют к концу импульса i, i <

2t, то все корректные процессы останавливаются на значении 1.

Доказательство. Пусть i - первый импульс, в конце которого по крайней мере

L корректных процессов инициируют, и пусть А обозначает множество

корректных процессов, которые инициировали в конце импульса i. Все процессы

в A - помощники, так как командующий сбойный. В конце импульса i + 2 все

корректные процессы подтвердили помощников в А; мы покажем, что в это время

все корректные процессы инициируют.

Случай i = 1: Все корректные процессы подтвердили помощников из А к концу

импульса 3, и инициируют, так как [pic].

Случай [pic]: По крайней мере один процесс, допустим r, из А инициировал в

импульсе i, так как он подтвердил Th(i) помощников (инициирование с помощью

получения от командующего возможно только в импульсе 1). Эти Th(i)

помощников подтверждены всеми корректными процессами в конце импульса i +

l, но r не принадлежит к этим Th(i) подтвержденным помощникам, так как r

впервые посылает сообщения в импульсе i + 1. Однако, все корректные

процессы подтвердят r к концу импульса i + 2; таким образом они подтвердили

по крайней мере Th(i) + 1 помощников в конце раунда i + 2. В заключение,

так как Th(i+2)= Th(i)+1, все корректные процессы инициируют.

Теперь, поскольку все корректные процессы инициируют к концу раунда i + 2,

они подтверждены (всеми корректными процессами) в конце раунда i + 4,

следовательно все корректные процессы подтвердили по крайней мере H

помощников. Поскольку предполагалось, что i < 2t, [pic], так что все

корректные процессы останавливаются на значении 1. (

Для любого корректного процесса, чтобы остановиться на 1, необходима

"лавина", состоящая из инициирования по крайней мере L на корректных

процессов. Действительно, 1-решение требует подтверждения по крайней мере H

процессов, включая L корректных, что эти корректные процессы инициировали.

Вопрос в том может ли Византийский заговор откладывать начало лавины

достаточно долго, чтобы вызвать 1-решение в некоторых корректных процессах,

без навязывания его в общем согласно Лемме 14.7. Конечно, ответ - нет, так

как имеется ограничение на то, как долго заговор может откладывать лавину,

и число импульсов, 2t + 3, выбрано точно так, чтобы предотвратить это.

Причина - возрастающий порог для требуемого числа подтвержденных процессов;

в более поздних импульсах он становится настолько высок, что уже стало

необходимо L инициированных корректных помощников, чтобы инициировать

следующий корректный процесс.

Лемма 14.8 Предположим, что по крайней мере L корректных процессов

инициируют в течение алгоритма, и пусть i - первый импульс, в конце

которого инициируют L корректных процессов. Тогда i < 2t.

Доказательство. Чтобы инициировать в импульсе 2t или выше, корректный

процесс должен подтвердить по крайней мере Th(2t) = L + (t-1) помощников.

Так как командующий сбойный, то есть самое большее t-1 сбойных помощников,

поэтому по крайней мере L корректных помощников должны были быть

подтверждены, что показывает, что уже, в более раннем импульсе, L

корректных процессов, должно быть, инициировали. (

Теорема 14.9 Алгоритм вещания Долева и других (Алгоритм 14.4) - t-

Византийско-устойчивый протокол вещания.

Доказательство. Завершение (и одновременность также) и зависимость показаны

в Лемме 14.6. Чтобы показать соглашение, предположим, что имеется

корректный процесс, который останавливается на значении 1. Мы заметили, что

это означает, что по крайней мере L корректных процессов инициировали. По

Лемме 14.8, впервые это случалось в импульсе i < 2t. Но тогда по Лемме

14.7, все корректные процессы останавливаются на значении 1. (

Чтобы облегчить представление алгоритма, было сделано предположение, что

процессы повторяют в каждом раунде сообщения, которые они посылали в более

ранних раундах. Поскольку корректные процессы записывают сообщения,

полученные в более ранних раундах, это не нужно, поэтому достаточно послать

каждое сообщение только. Таким образом, каждый корректный процесс посылает

каждое из N+1 возможных сообщений другому процессу самое большее один раз,

что ограничивает сложность по сообщениям величиной [pic]. Так как имеется

только N+1 различных сообщений, каждое сообщения должно содержать только O

(log N) бит.

Если число процессов превышает 3t + 1, для выполнения алгоритма выбирается

совокупность 3t активных помощников. (Выбор выполняется статически,

например, выбирая 3t процессов, чьи имена следуют за g в порядке имен

процессов. Командующий и активные помощники сообщают пассивным помощникам о

своем решении, и пассивные помощники останавливаются на значении, которое

они получают от более t процессов. Сложность по сообщениям этого послойного

подхода - [pic], и разрядная сложность - [pic].

14.2 Протоколы с Установлением Подлинности

Злонамеренное поведение, рассматриваемое до сих пор включало неправильную

пересылку информации в дополнение к посылке неправильной информации о

собственном состоянии процесса. К счастью, это чрезвычайно злонамеренное

поведение Византийских процессов может быть ограничено с помощью

криптографических средств, которые сделали бы Теорему 14.1

недействительной. Действительно, в сценариях, используемых в ее

доказательстве, сбойные процессы посылали бы сообщения как в сценарии 1,

получив только сообщения сценария 0.

В этом разделе предполагается наличие средства для цифровой подписи и

установления подлинности сообщений. Процесс p, посылающий сообщение М,

добавляет к этому сообщению некоторую дополнительную информацию [pic],

которая называется цифровой подписью p для сообщения М. В отличие от

рукописных подписей, цифровая подпись зависит от М, что делает бесполезным

копирование подписи в другие сообщения. Схема подписи удовлетворяет

следующим свойствам.

Если p корректен, только p может правдоподобно вычислить [pic]. Это

вычисление - подпись сообщения M.

Каждый процесс может эффективно проверять (имея p, М и S) [pic]. Эта

проверка - установление подлинности сообщения M.

Схемы подписи основаны на частных и общих ключах. Первое предположение не

исключает того, что Византийские процессы могут открыть свои секретные

ключи друг другу, что позволяет одному Византийскому процессу подделать

подпись другого. Предполагается, что только корректные процессы хранят свои

частные ключи в секрете.

Мы изучим реализацию схем подписи в Подразделах с 14.2.2 по 14.2.5. В

следующем подразделе, сообщение , подписанное процессом p, то есть,

пара, содержащая и [pic], обозначается : p.

14.2.1 Протокол Высокой Степени Восстановления

Эффективный Византийский алгоритм вещания, использующий полиномиально много

сообщений и t+1 импульсов, был предложен Долевом и Стронгом [DS83].

Установление подлинности, используемое в этом протоколе, разрешает

неограниченную способность восстановления. Мы заметим, тем не менее, что

могут отказать не более N процессов (из N), и N процессов отказывают, все

требования примитивно удовлетворяются; следовательно пусть t < N. Их

протокол основан на более раннем, предложенном Лампортом, Шостаком и Пизом

[LSP82], который является экспоненциальным по числу сообщений. Мы

представляем сначала последний протокол.

В импульсе 1 командующий “выкрикивает” сообщение : g,

содержащее свой (подписанный) вход.

В импульсах со 2 по t + l процессы подписывают и пересылают сообщения,

которые они получили в предыдущем импульсе; следовательно, сообщение,

которым обмениваются в импульсе i, содержит i подписей. Сообщение : g : [pic] : ... : [pic] называется действительным (имеющим силу) для

получающего процесса p, если справедливо следующее.

Все i подписей корректны.

i подписей от i различных процессов.

p не встречается в списке подписей.

В течение алгоритма, процесс p содержит множество [pic] значений,

содержащихся в действительных сообщениях, полученных p; первоначально это

множество пусто, и значение каждого действительного сообщения вставляется в

него.

Сообщения, пересылаемые в импульсе i - в точности те действительные

сообщения, полученные в предыдущем импульсе. В конце импульса t + 1,

процесс p принимает решение основанное на [pic]. Если [pic] состоит из

одиночного элемента {v}, p принимает решение v, иначе p принимает решение

значения по умолчанию (например, 0). Чтобы сэкономить на числе сообщений, p

пересылает сообщение : g : [pic] : ... : [pic] : p только

процессам, не встречающимся в списке g, [pic], ..., [pic]. Эта модификация

не имеет никакого влияния на поведение алгоритма, так как для процессов в

списке сообщение не действительно.

Теорема 14.10 Алгоритм Лампорт, Шостака и Пиза - корректный Византийский

алгоритм вещания при t < N, использующий t + 1 импульс.

Доказательство. Все процессы принимают решение в импульсе t + 1, что

подразумевает и завершение и одновременность алгоритма.

Если командующий корректен и имеет вход v, все процессы получают его

сообщение : g в импульсе 1, так что все корректные процессы

включают v в W. Никакое другое значение не вставляется в W, так как никакое

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

импульсе t + 1 все процессы имеют W = {v} и останавливаются на v, что

означает зависимость.

Чтобы показать соглашение, мы получим, что для корректных процессов p и q,

[pic] в конце импульса t + 1. Предположим, [pic] в конце импульса t + 1, и

пусть i - импульс, в котором p вставил v в Wp, по получении сообщения

: g : [pic] : ... : [pic].

Случай 1: Если q встречается в g, [pic], ..., [pic], то q сам видел

значение v и вставил его в [pic].

Случай 2: Если q не встречается в последовательности g, [pic], ..., [pic] и

[pic], то p пересылает сообщение : g : [pic] : ... : [pic] : p

процессу q в импульсе i + i, так что q утверждает (придает силу) v самое

позднее в импульсе i + 1.

Случай 3: Если q не встречается в последовательности g, [pic], ..., [pic],

и i = t + 1, заметьте, что сообщение, полученное p, было подписано t + l

последовательными процессами, включая по крайней мере один корректный

процесс. Этот процесс переслал сообщение всем другим процессам, включая q,

так что q видит v.

Так как [pic] к концу импульса t + 1, p и q принимают одинаковое решение. (

Завершить алгоритм ранее импульса t + 1 невозможно. Во всех импульсах до t,

корректный процесс мог бы получать сообщения, созданные и пересланные

только сбойными процессами, и не посланные другим корректным процессам, что

могло бы вести к противоречивым решениям.

Промежуточный результат предыдущего алгоритма, а именно соглашение о

множестве значений среди всех корректных процессов, более сильное, чем

необходимо для достижения соглашения об одиночном значении; Это было

замечено Долевом и Стронгом [DS83], которые предложили более эффективную

модификацию. Фактически достаточно, что в конце импульса t + 1, или (a) для

каждого корректного p множество [pic] - один и тот же одиночный элемент,

или (b) ни для какого корректного p множество [pic]не является одиночным

элементом. В первом случае все процессы принимают решение v, в последнем

случае они все принимают решение 0 (или, если желательно изменить алгоритм

таким образом, они принимают решение "командующий сбойный").

Алгоритмом Долева и Стронга достигается более слабое требование на

множества W. Вместо того, чтобы передавать каждое действительное сообщение,

процесс p пересылает самое большее два сообщения, а именно одно сообщение с

первым и одно сообщение со вторым значением, принятым p. Полное описание

алгоритма оставлено читателю.

Теорема 14.11 Алгоритм Долева и Стронга, описанный выше - протокол

Византийского-вещания, использующий t + 1 импульс и самое большее [pic]

сообщений.

Доказательство. Завершение и одновременность доказываются, как в предыдущем

протоколе, так как каждый корректный процесс принимает решение в конце

импульса t + 1. Зависимость выводится так же, как в предыдущем протоколе.

Если g правильно “выкрикивает” v в первом импульсе, все корректные процессы

принимают v в этом импульсе, и никакое другое значение никогда не

принимается; следовательно, все корректные процессы останавливаются на v.

Заявленная сложность по сообщениям следует из факта, что каждый

(корректный) процесс “выкрикивает” самое большее два сообщения.

Чтобы показать соглашение, мы покажем, что для корректных процессов p и q,

[pic] и [pic] удовлетворяют в конце импульса t + 1 следующему.

Если [pic], то [pic].

Если [pic], то [pic].

Для (1): Предположим, что p принял значение v после получения сообщения

: g : [pic] : ... : [pic] в импульсе i, и рассуждаем как в

доказательстве Теоремы 14.10:

Случай 1: Если q встречается среди g, [pic], ..., [pic], q точно принял v.

Случай 2: Если q не встречается среди g, [pic], ..., [pic], и [pic], [pic],

то p пересылает значение процессу q, который примет его в этом случае.

Случай 3: Если q не встречается и i = t + 1, по крайней мере один из

процессов, который подписал сообщение, допустим r, корректен. Процесс r

также переслал значение v процессу q, что значит, что v находится в [pic].

Для (2): Предположим, что [pic] в конце алгоритма, и пусть w - второе

значение, принятое p. Снова подобным рассуждением можно показать, что

[pic], что означает, что [pic]. (Равенство [pic] и [pic] не может быть

получено, так как процесс p не будет пересылать свое третье принятое

значение или более поздние.)

Доказав (1) и (2), предположим, что корректный процесс p останавливается на

[pic], то есть [pic]. Затем, из (1), v содержится во всех [pic] для

корректного q, но, следовательно, [pic] не шире одиночного элемента {v};

иначе [pic] - не одиночный элемент, из (2). Следовательно, каждый

корректный процесс q также останавливается на v. Далее, предположим, что

корректный процесс p останавливается на значении по умолчанию, так как

[pic] - не одиночный элемент. Если [pic] пуст, каждый корректный q имеет

пустой [pic] по (1) и если [pic], то [pic] по (2); следовательно, q также

останавливается на значении по умолчанию.

(

Долев и Стронг в дальнейшем улучшили алгоритм и получили алгоритм, который

решает проблему Византийского-вещания за то же самое число импульсов и

всего за О(Nt) сообщений.

14.2.2 Реализация Цифровых Подписей

Так как подпись p [pic] должна представлять собой достаточное

доказательство того, что p - создатель сообщения, подпись должна состоять

из некоторой формы информации, которая

Может быть эффективно вычислена процессом p (подписана);

Не может быть эффективно вычислена любым другим процессом, отличным от p

(подделана).

Мы должны немедленно отметить, что, для большинства схем подписи,

использующихся сегодня, второе требование не доказано до такой степени, что

показана экспоненциальная трудность проблемы подделки. Обычно, проблема

подделки, как показывают, связана (или иногда эквивалентна) с некоторой

вычислительной проблемой, которая изучалась в течение длительного времени в

отсутствие знания о ее полиномиальной разрешимости. Например, подделывание

подписей в схеме Фиата-Шамира требует разлагать на множители большие целых

числа; так как последняя задача (предположительно) в вычислительном

отношении очень сложна, первая, должно быть, также сложна в вычислительном

отношении.

Были предложены схемы подписи, основанные на различных, как предполагается,

трудных проблемах, типа вычисления дискретного логарифма, разложения на

множители больших чисел, проблемы рюкзака. Требования (1) и (2)

подразумевают, что процесс p должен иметь вычислительное "преимущество" над

другими процессами; это преимущество - некоторая секретная информация во

владении p, секретный (или частный) ключ p. Таким образом, вычисление [pic]

эффективно, когда секретный ключ известен, но (предположительно) трудно без

этой информации. Ясно, что если p удается хранить свой ключ в тайне, то

только p может с легкостью вычислять [pic].

Все процессы должны уметь проверять подписи, то есть, имея сообщение М и

подпись S, должно быть возможно эффективно проверить, что S действительно

был вычислен из М с помощью секретного ключа p. Эта проверка требует, чтобы

была раскрыта некоторая информация о секретном ключе p; эта информация -

общий ключ p. Общий ключ должен позволять проверку подписи, но нужно, чтобы

его быть невозможно или по крайней мере в вычислительном отношении трудно

использовать для вычисления секретного ключа p или подделки подписей.

Наиболее успешные схемы подписи, предложенные до настоящего времени,

основаны на вычислениях из теории чисел в арифметических кольцах по модулю

больших чисел. Базисные арифметические операции добавления, умножения, и

возведения в степень могут выполняться в этих кольцах за полиномиальное

время от длины модуля (в битах). Деление возможно, если знаменатель и

модуль взаимно просты (то есть, не имеют общих простых делителей), и может

также выполняться за полиномиальное время. Так как подписание и проверка

требуют вычислений над сообщением, М интерпретируется как большое число.

14.2.3 Схема Подписи ЭльГамаля

Схема подписи ЭльГамаля [EIG85] основана на функции теории чисел под

названием дискретный логарифм. Для большого простого числа P, группа по

умножению по модулю P, обозначаемая [pic], содержит P-1 элементов и

чвлчется циклической. Последнее означает, что можно выбрать такой элемент

[pic], что P-1 чисел

[pic]

все различны и следовательно, перечисляют все элементы [pic]. Такое g

называется генератором [pic], или также первообразным корнем по модулю P.

Генератор не уникален; обычно их много. Имея фиксированное P и генератор g,

для каждого [pic] имеется уникальное целое число i по модулю P-1 такое, что

[pic] (равенство в [pic]). Это i называется дискретным логарифмом (иногда

индексом) x. В отличие от вышеупомянутых базисных арифметических операций,

вычислять дискретный логарифм не просто. Это - хорошо-изученная проблема,

для которой до настоящего времени не найдено эффективное общее решение, но

также не была доказана ее труднорешаемость; см. [0dl84] для краткого обзора

результатов.

Схема подписи ЭльГамаля [EIG85] основана на трудности вычисления дискретных

логарифмов. Процессы совместно используют большое простое число P и

первообразный корень g из [pic]. Процесс p выбирает в качестве своего

секретного ключа число d, случайно между 1 и P - 2, и общий ключ p - число

[pic]; заметьте, что d - дискретный логарифм e. Подпись p можно эффективно

вычислить, зная логарифм e, и следовательно она формирует неявное

доказательство того, что подписывающий знает d.

Действительная подпись для сообщения М - пара (r, s), удовлетворяющая

[pic]. Такую пару p легко найдет с помощью секретного ключа d. Процесс p

выбирает произвольное число a, взаимно простое с P-1, и вычисляет

[pic]

и

[pic]

Эти числа действительно удовлетворяют

[pic]

(Все равенства в [pic].) Действительность подписи S = (r, s) для сообщения

М легко проверить, проверяя на равенство [pic].

Алгоритмы для дискретного логарифма. Так как секретный ключ p, d, равняется

дискретному логарифму общего ключа, e, схема раскрыта, если можно

эффективно вычислять дискретные логарифмы по модулю P. До настоящего

времени, не известно эффективного алгоритма, чтобы делать это в общем

случае или подделывать подписи любым другим способом.

Общий алгоритм для вычисления дискретных логарифмов был представлен Одлыжко

[0dl84]. Его сложность имеет тот же порядок, как у хорощо известных

алгоритмов для разложения на множители целых чисел, столь же больших как P.

Алгоритм сначала вычисляет несколько таблиц, используя только P и g, и, во

второй фазе, вычисляет логарифмы для данных чисел. Если Q самый большой

простой множитель P-1, время для первой фазы и размер таблиц имеют порядок

Q; следовательно, желательно выбрать P такой, что P-1 имеет большой простой

множитель. Вторая фаза, подсчет логарифмов, может выполняться в течении

секунд даже на очень маломощных компьютерах. Следовательно, необходимо

менять P и g достаточно часто, допустим каждый месяц, так, чтобы таблицы

для конкретного P устаревали до их завершения.

Рандомизированное подписывание (подписывание с уравниванием вероятностей).

Рандомизация в процедуре подписывания делает каждую из [pic] различных

подписей[8] для данного сообщения одинаково вероятным результатом процедуры

подписывания. Таким образом, один и тот же документ, подписанный дважды,

почти обязательно произведет две различных действительных подписи.

Рандомизация необходима в процедуре подписывания; если p подписывает два

сообщения, пользуясь одним и тем же значением a, из подписей можно

вычислить секретный ключ p; см. Упражнение 14.6.

14.2.4 Схема Подписи RSA

Если n - большое число, произведение двух простых чисел P и Q, то очень

трудно вычислить квадратный корень и корни более высоких порядков по модулю

n, если не известно разложение на множители. Возможность вычисления

квадратных корней можно использовать, чтобы найти множители n (см.

Упражнение 14.7), что показывает, что вычисление квадратных корней является

таким же трудным, как и разложение на множители.

В схеме подписи Ривеста, Шамира и Эйдлмана [RSA78], общий ключ p - большое

число n, разложение которого на множители p знает, и показатель степени e.

Подпись p для сообщения М - e-й корень М по модулю n, который легко

проверить, пользуясь возведением в степень. Этот корень более высокого

порядка находится p также с использованием возведения в степень; при

генерации своего ключа p вычисляет число d такое, что [pic], что означает,

что [pic], то есть, [pic] - e-й корень М. Секретный ключ p состоит только

из номера d, то есть, p не должен запоминать разложение на множители n.

В схеме RSA, p показывает свой идентификатор вычислением корней по модулю

n, что требует (неявного) знания разложения n на множители; предполагается,

что только p знает его. В этой схеме каждый процесс использует свой модуль.

14.2.5 Схема Подписи Фиата-Шамира

Более тонкое использование трудности нахождения (квадратных) корней сделано

в схеме Фиата и Шамира [FS86]. В RSA схеме процесс подписывает сообщение,

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

способность вычислять корни возможно требует знания разложения на

множители. В схеме Фиата-Шамира процессы используют общий модуль n,

разложение на множители которого известно только доверенному центру.

Процессу p даются квадратные корни некоторых специфических чисел (в

зависимости от идентификатора p), и подпись p для М обеспечивает

доказательство того, что подписывающий знает эти квадратные корни, но не

раскрывая их.

Преимущество схемы Фиата-Шамира над RSA схемой - более низкая

арифметическая сложность и отсутствие отдельного общего ключа для каждого

процесса. Недостаток - потребность в доверенном источнике, который выдает

секретные ключи. Как упоминалось прежде, схема использует большое целое

число n, произведение двух больших простых чисел, известных только центру.

Кроме того имеется односторонняя псевдо-случайная функция f, отображающая

строки на [pic]; эта функция известна и может быть вычислена каждым

процессом, но обратная функция не может быть вычислена.

Секретные и общие ключи. В качестве секретного ключа p даны квадратные

корни с [pic] по [pic] k чисел по модулю n, а именно [pic], где [pic].

[pic] можно считать общими ключами p, но поскольку они могут быть вычислены

из идентификатора p, их не нужно хранить. Чтобы избежать технических

неудобств, мы предположим, что эти k чисел - квадратичные остатк по модулю

n. Квадратные корни могут быть вычислены центром, который знает множители

n.

Подписавание сообщений: первая попытка. Подпись p неявно доказывает, что

подписывающий знает корни [pic], то есть, может выдать число s такой, что

[pic]. Такое число - [pic], но посылка самого [pic] раскрыла бы секретный

ключ; чтобы избежать раскрытия ключа, схема использует следующую идею.

Процесс p выбирает произвольное число r и вычисляет [pic]. Теперь p -

единственный процесс, который может выдать число y, удовлетворяющее [pic],

а именно, [pic]. Таким образом, p может показывать свое знание [pic] без их

раскрытия, посылая пару (x, y), удовлетворяющую [pic]. Так как p не

посылает число r, вычислить [pic] из этой пары не возможно без вычисления

квадратного корня.

Но имеются две проблемы с подписями, состоящими из таких пар. Во-первых,

любой может произвести такую пару, жульничая следующим образом: сначала

выбрать y, и впоследствии вычислить [pic]. Во-вторых, подпись не зависит от

сообщения, так что процесс, получивший подписанное сообщение от p, может

скопировать подпись на любое поддельное сообщение. Трудный вопрос этой

схемы подписи - сделать так, чтобы p показывал знание корня произведения из

подмножества [pic], где подмножество зависит от сообщения и произвольного

числа. Шифрование сообщения и произвольного числа с помощью f не дает

подделывающему сначала выбрать y. Чтобы подписать сообщение М, p действует

следующим образом.

P выбирает произвольное число r и вычисляет [pic].

P вычисляет f (М, x), назовем первые k бит с [pic] по [pic].

P вычисляет [pic].

Подпись [pic] состоит из кортежа ([pic],..., [pic], y).

Чтобы проверить подпись ([pic],..., [pic], y) процесса p для сообщения М,

надо действовать следующим образом.

Вычислить [pic] и [pic]

Вычислить f (М, z) и проверить, что первые k бит - [pic] по [pic].

Если подпись истинна, значение z, вычисленное на первом шаге проверки

равняется значению x, используемому в подписывании и следовательно первые k

бит f (М, z) равны [pic] ... [pic].

Подделка и заключительное решение. Мы рассмотрим теперь стратегию

подделывающего для получения подписи согласно вышеупомянутой схеме без

знания [pic].

Выбрать k произвольных бит [pic] ... [pic].

Выбрать произвольное число y и вычислить [pic]

Вычислить f (М, x) и посмотреть, равняются ли первые k бит значениям [pic]

... [pic], выбранным ранее. Если это так, то ([pic],..., [pic], y) -

подделанная подпись для сообщения M.

Поскольку вероятность равенства в шаге (3) может быть принята [pic],

подделка становится успешной после ожидаемого числа [pic] испытаний.

При k = 72 и принятым временем [pic] секунд для опробования одного выбора

[pic], ожидаемое время подделки (с этой стратегией) - [pic] секунд или 1,5

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

должен хранить k корней, и если k должен быть ограничен из-за ограничений

пространства, ожидаемое время подделки [pic] может быть

неудовлетворительно. Мы покажем сейчас как изменить схему, чтобы

использовать k корней, и получать ожидаемое время подделки [pic] для

выбранного целого числа t. Идея состоит в том, чтобы использовать первые kt

бит f-результата, чтобы определить t подмножеств от [pic], и заставить p

показывать свое знание t этих произведений. Чтобы подписать сообщение М, p

действует следующим образом.

p выбирает произвольные [pic],..., [pic] и вычисляет [pic].

p вычисляет f (М, [pic], ..., [pic]); назовем первые kt бит [pic]. ([pic] и

[pic]).

p вычисляет [pic] для [pic]. Подпись [pic] состоит из ([pic], ..., [pic],

[pic], ..., [pic]).

Чтобы проверить подпись ([pic], ..., [pic], [pic], ..., [pic]) процесса p

для сообщения М, надо действуовать следующим образом.

Вычислить [pic] и [pic].

Вычислить f (М, [pic], ..., [pic]), и проверить, что первые kt бит - [pic],

..., [pic].

Подделывающий, пытающийся произвести действительную подпись с той же самой

стратегией, что приведена выше, теперь имеет вероятность успеха в третьем

шаге [pic], что означает ожидаемое число испытаний [pic]. Фиат и Шамир

показывают в своей работе, что если разложение n на множители не

оказывается простым, то существенно лучшего алгоритма подделки не

существует, следовательно схему можно сделать произвольно безопасной,

выбирая k и t достаточно большими.

14.2.6 Резюме и Обсуждение

В этом и предыдущем разделе было показано, что в синхронных системах

существуют детерминированные решения для проблемы Византийского вещания.

Максимальная способность восстановления таких решений - t < N/3, если не

используется проверка подлинности (Раздел 14.1), и неограничена, если она

используется (этот раздел). Во всех решениях, представленных здесь,

синхронность была смоделирована с помощью (довольно сильных) предположений

модели импульса; отказоустойчивая реализация модели импульса обсуждается в

Разделе 14.3.

Проблема расстрельной команды. В дополнение к принятию модели импульса,

второе предположение, лежащее в основе всех решений, представленных до сих

пор - то, что импульс, в котором вещание начинается, известен всем

процессам (и пронумерован 1 для удобства). Если априори дело обстоит не

так, возникает проблема старта алгоритма одновременно, после того, как один

или более процессов (спонтанно) инициируют запрос просьбу о выполнении

алгоритма вещания. Запрос может исходить от командующего (после вычисления

результата, который должен быть объявлен всем процессам) или от помощников

(понимающих, что им всем нужна информация, хранящаяся у командующего). Эта

проблема изучается в литературе как проблема расстрельной команды. В этой

проблеме, один или более процессов инициируют (запрос), но не обязательно

в одном и том же импульсе, и процессы могут стрелять. Требования:

Обоснованность. Никакой корректный процесс не стреляет, если никакой

процесс не инициировал.

Одновременность. Если любой корректный процесс стреляет, тогда все

корректные процессы стреляют в том же самом импульсе.

Завершение. Если корректный процесс инициирует, то все корректные процессы

стреляют в течение конечного числа импульсов.

Действительно, имея решение для проблемы расстрельной команды, не нужно

заранее соглашаться о первом импульсе вещания; процессы, запрашивающие

вещание, инициируют алгоритм расстрельной команды, и вещание начинается в

импульсе следующем за стрельбой. Методы, используемые в решениях проблемы

Византийского-вещания и проблемы расстрельной команды, могут быть

объединены, чтобы получить протоколы, более эффективные по времени, которые

решают проблему вещания непосредственно в отсутствии априорного соглашения

о первом импульсе.

Временная сложность и рано останавливающиеся протоколы. В этой главе мы

представили протоколы, использующие t + 1 или 2t + 3 импульсов, или раундов

связи. Фишером и Линчем [FL82] показано, что t + 1 раундов связи -

оптимальное число для t-устойчивых протоколов согласия, и результат был

расширен, чтобы охватить протоколы с установлением подлинности, Долевом и

Стронгом [DS83].

Тонкий момент в этих доказательствах - то, что в использованных сценариях

процесс должен отказывать в каждом из импульсов с 1 по t, поэтому нижние

границы в худшем случае - число фактических сбоев в течение выполнения. Так

как в большинстве выполнений фактическое число сбоев намного ниже

способности восстановления, изучалось существование протоколов, которые

могут достигать соглашения ранее в тех выполнении, которые имеют маленькое

число сбоев. Протоколы вещания с таким свойством называются рано

останавливающимися. Долев, Райсчук и Стронг [DRS82] продемонстрировали

нижнюю границу в f + 2 раунда для любого протокола в выполнении с f сбоями.

Обсуждение нескольких рано останавливающихся протоколов вещания и согласия

есть в [BGP92].

Рано останавливающиеся протоколы принимают решение в течение нескольких

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

без новых сбоев. Однако, нельзя гарантировать, что все корректные процессы

достигают этого заключения в одном и том же импульсе. (Если, конечно, они

не достигают его в импульсе t + 1; так как самое большее t процессов

отказывают, среди первых t + 1 имеется один раунд, в котором никакого

нового сбоя не происходит.) Как следствие, рано останавливающиеся протоколы

не удовлетворяет одновременности. Коун и Дворк показали [CD91], что, чтобы

достигнуть одновременности, в выполнении, где никаких сбоев не происходит,

необходимо также t + 1 раунд, даже для рандомизированных протоколов и в

(очень слабый) модели аварий. Это означает, что протоколам с установлением

подлинности также нужно t + 1 импульсов для одновременного соглашения.

Поблемы решения и согласованная непротиворечивость. При использовании

протокола вещания в качестве подпрограммы, фактически все проблемы решения

для синхронных систем могут быть решены достижением согласованной

непротиворечивости, то есть соглашения о множестве входов. В проблеме

согласованной непротиворечивости, процессы принимают решение о векторе

входов, с одним элементов для каждого процесса в системе. Формально,

требования таковы:

Завершение. Каждый корректный процесс p останавливается на векторе [pic] с

одним элементом для каждого процесса.

Соглашение. Векторы решения корректных процессов равны.

Зависимость. Если q корректен, то для корректного p, [pic].

Согласованной непротиворечивости можно достичь множественными вещаниями:

каждый процесс вещает свой вход, и процесс p помещает свое решение в

вещании q в [pic]. Завершение, соглашение, и зависимость непосредственно

наследуются от соответствующих свойств алгоритма вещания.

Так как каждый корректный процесс вычисляет один и тот же вектор

(соглашение), большинство проблем решения легко решается с помощью

детерминированной функции на векторе решения (что непосредственно

гарантирует соглашение). Согласие, например, решается с помощью извлечения

значения, имеющего большинство, из решающего вектора. Выбор решается

извлечением самого маленького уникального идентификатора в векторе

(остерегайтесь; избранный процесс может быть сбойным).

14.3 Синхронизация Часов

В предыдущих разделах было показано, что (когда рассматриваются

детерминированные алгоритмы) синхронные системы имеют более высокую

способность восстановления, чем асинхронные. Это было сделано для

идеализированной модели синхронности, где процессы функционируют в

импульсах. Более высокая способность восстановления модели импульса

означает, что не возможно детерминированно устойчиво синхронизировать

полностью асинхронные сети. В этом разделе будет показано, что устойчивая

реализация модели импульса возможна в модели асинхронных сетей ограниченных

задержек (ABD (asynchronous bounded-delay) сети - АСОЗ).

Модель АСОЗ характеризуется наличием локальных часов и верхней границей на

задержку сообщений. В описании и анализе алгоритмов мы используем кадр

реального времени (real-time frame), который является назначением времени

наступления [pic] каждому событию. Согласно релятивистской физике, нет

стандартного или предпочтительного способа сделать это назначение; в

дальнейшем будем предполагать, что физически значимое назначение было

выбрано. Кадр реального времени не поддается наблюдению для процессов в

системе, но процессы могут косвенно отслеживать время, используя свои часы,

значения которых связаны с реальным временем. Часы процесса p обозначаются

[pic] и он может читать и записывать в них (запись в часы необходима для

синхронизации). Значение часов непрерывно изменяется во времени, если часы

не назначены; мы пишем [pic], чтобы обозначить, что в момент реального

времени t часы содержат T.

Заглавные буквы (C, T) используются для времени часов, а строчные буквы (c,

t) - для реального времени. Часы могут использоваться для управления

наступлением событий, как в выражении

when [pic] then send message

rоторое вызывает посылку сообщения во время [pic]. Функция [pic]

обозначается [pic].

Значение идеальных часов увеличивается на [pic] за [pic] единиц времени, то

есть, оно удовлетворяет [pic]. Синхронизированные идеальные часы никогда не

нуждаются в корректировке, но, к сожалению, они всего лишь (полезная)

математическая абстракция. Часы, используемые в распределенных системах,

испытывают отклонение, ограниченное маленькой известной константой [pic]

(обычно порядка [pic] или [pic]). Отклонение часов C [pic]-ограничено,

если, для [pic] и [pic], таких, что между [pic] и [pic] не происходит

присваивания C,

[pic] (14.1)

Различные часы в распределенных системах не показывают одно и то же время

часов в любой заданный момент реального времени, то есть, [pic] не

обязательно справедливо. Часы [pic]-синхронизированы в момент реального

времени t, если [pic], и [pic]-синхронизированы момент часового времени T,

если [pic]. Мы считаем эти понятия эквивалентными; см. Упражнение 14.8.

Цель алгоритмов синхронизации часов состоит в том, чтобы достичь и

поддерживать глобальную [pic]-синхронизацию, то есть, [pic]-синхронизацию

между каждой парой часов. Параметр [pic] - точность синхронизации.

Задержка сообщений ограничена снизу [pic] и сверху [pic], где [pic];

формально, если сообщение посылается в реальное время [pic] и получается в

реальное время [pic], то

[pic] (14.2)

Так как выбор кадра реального времени свободный, предположения (14.1) и

(14.2) относятся к временному кадру так же, как и к часам и системе связи.

14.3.1 Чтение Удаленных Часов

В этом подразделе будет изучена степень точности, с которой процесс p может

настраивать свои идеальные часы на идеальные часы надежного сервера s. У

детерминированного протокола самая лучшая доступная точность - [pic], и эта

точность может быть получена для простого протокола, который обменивается

только одним сообщением. Вероятностные протоколы могут достигать

произвольной точности, но сложность по сообщениям зависит от желательной

точности и распределения времен доставки сообщений.

Теорема 14.12 Существует детерминированный протокол для синхронизирования

[pic] с [pic] с точностью [pic], который обменивается одним сообщением.

Никакой детерминированный протокол не достигает более высокой точности.

Доказательство. Мы сначала представим простой протокол и докажем, что он

достигает точности, заявленной в теореме. Чтобы синхронизировать [pic],

сервер посылает одно сообщение, . Когда p получает ,

он корректирует часы на T + [pic].

Чтобы доказать заявленную точность, назовем реальные времена посылки и

получения сообщения [pic] и [pic] соответственно; теперь [pic].

Так как часы идеальны, [pic]. Во время [pic], p корректирует часы, чтобы на

них было [pic], поэтому [pic]. Теперь [pic] означает [pic].

Рисунок 14.5 Сценарии для детерминированного протокола.

Чтобы показать нижнюю границу для точности, пусть дан детерминированный

протокол; в этом протоколе p и s обмениваются некоторыми сообщениями, после

которых p корректирует свои часы. Рассматриваются два сценария для

протокола, как изображено на Рисунке 14.5. В первом сценарии, часы равны до

выполнения, все сообщения из s в p доставляются после [pic], и все

сообщения из p в s доставляются после [pic]. Если корректировка в этом

сценарии - [pic], то часы p в точности на [pic] опережают [pic] после

синхронизации.

Во втором сценарии [pic] до выполнения отстает от [pic] на [pic], все

сообщения из p в s доставляются после [pic], и все сообщения из s в p

доставляются после [pic]. Назвав корректировку в этом сценарии [pic], мы

видим, что часы p после синхронизации отстают от [pic] в точности на [pic].

Однако, ни p ни s не наблюдают различия между сценариями, так как

неопределенность в задержке сообщения скрывает различие; следовательно

[pic]. Это означает, что точность самого худшего случая

[pic]

Этот минимум равняется (и случается при [pic]). (

Если два процесса p и q синхронизируют свои часы с сервером с этой

точностью, достигается глобальная [pic]-синхронизация, который достаточно

для большинства прикладных программ.

Лучшая точность достижима у вероятностного протокола синхронизации,

предложенного Кристианом [Cri89]. Для этого протокола принимается, что

задержка сообщения - стохастическая переменная, распределенная согласно (не

обязательно известной) функции [pic]. Вероятность прибытия любого сообщения

в течение x - F(x), и задержки различных сообщений независимы. Произвольная

точность достижима только если нижняя граница [pic] плотна, то есть, для

всех x>[pic], F (x) > 0.

Протокол прост; p просит, чтобы s послал время, и s немедленно отвечает

сообщением . Процесс p измеряет время I между посылкой запроса и

получения ответа; справедливо [pic]. Задержка сообщения ответа - по крайней

мере [pic] и самое большее [pic], и следовательно отличается самое большее

на [pic] от [pic]. Таким образом, p может установить свои часы в [pic], и

достигает точности [pic]. Если желательная точность - [pic], p посылает

новый запрос если [pic], в противном случае завершается.

Лемма 14.13 Вероятностный протокол синхронизации часов достигает точности

[pic]с ожидаемым числом сообщений самое большее [pic].

Доказательство. Вероятность того, что запрос p прибывает в течение [pic] -

[pic]и такова же вероятность того, что ответ прибывает внутри в течение

[pic]. Следовательно, вероятность того, что p получает ответ в течение

[pic] - по крайней мере [pic], что означает границу в [pic] на ожидаемое

число испытаний до успешного обмена сообщениями. (

Временная сложность протокола уменьшается, если p посылает новый запрос

когда никакого ответа не было получено [pic] после посылки запроса.

Ожидаемое время тогда не зависит от ожидаемой или максимальной задержки, а

именно [pic], и протокол устойчив против потери сообщений. (Нужно

использовать номера в порядке следования, чтобы отличить устаревшие

ответы.)

14.3.2 Распределенная Синхронизация Часов

Этот раздел представляет t-Византийско-устойчивый (при t < N/3)

распределенный алгоритм синхронизации часов Махани и Шнайдера [MS85].

Долев, Халперн и Стронг [DHS84] показали, что никакая синхронизация не

возможна при [pic], если не используется установление подлинности.

Ядро алгоритма синхронизации - протокол, который достигает неточного

соглашения о средних значениях часов. Процессы корректируют свои часы и

достигают высокой степени синхронизации. Из-за отклонения через некоторое

время точность ухудшается, что влечет за собой новый раунд синхронизации

после некоторого интервала. Предположим, что в реальное время [pic] часы

[pic]-синхронизированы; тогда до времени [pic] часы [pic]-синхронизированы.

Таким образом, если желательная точность - [pic], и раунд синхронизации

достигает точности [pic], раунды повторяются каждые [pic] единиц времени.

Так как время, допустим S, для выполнения раунда синхронизации обычно очень

мало по сравнению с R, то оправдано упрощающее предположение о том, что в

течение синхронизации отклонением можно пренебречь, то есть, часы являются

идеальными.

Неточное соглашение: алгоритм с быстрой сходимостью. В проблеме неточного

соглашения, используемой Махани и Шнайдером [MS85] для синхронизации часов,

процесс p имеет действительное входное значение [pic], где для корректных p

и q [pic]. Выход процесса p - действительное значение [pic], и точность

выхода определяется как [pic]; цель алгоритма состоит в том, чтобы достичь

очень малого значения точности.

var [pic], [pic], [pic] : real; (*Вход, выход, оценщик V *)

[pic], [pic] : multiset of real;

begin (*фаза сбора входов*)

[pic]

forall [pic] do send to q

wait [pic]; (*Обработать сообщения и *)

while [pic] do insert ([pic]);

(*Теперь вычислить приемлемые значения*)

[pic]

[pic]

while [pic] do insert([pic], [pic]);

[pic]

end

После получения от q:

send to q

После получения от q:

if такое сообщение не было получено от q прежде

then insert([pic], x)

Алгоритм 14.6 алгоритм с быстрой сходимостью.

Алгоритм с быстрой сходимостью, предложенный Махани и Шнайдером дан как

Алгоритм 14.6. Для конечного множества [pic], определим две функции

intvl(A)=[min(A), max(A)] и width(A) = max(A) - min(A). Алгоритм имеет фазу

сбора входов и фазу вычисления. В первой фазе процесс p просит каждый

другой процесс послать свой вход (“выкрикивая” сообщение ) и ждет

[pic] единиц времени. После этого времени, p получил все входы от

корректных процессов, также как и ответы от подмножества сбойных процессов.

Эти ответы заполняются (бессмысленными) значениями [pic] для процессов,

которые не ответили.

Затем процесс применяет к полученным значениям фильтр, который

гарантированно пропускает все значения корректных процессов и только те

сбойные значения, которые достаточно близки к правильным значениям.

Поскольку корректные значения отличаются только на [pic] и имеется по

крайней мере N-t корректных значений, каждое корректное значение имеет по

крайней мере N-t значения, которые отличаются самое большее на [pic] от

него; [pic] сохраняет полученные значения с этим свойством.

Затем вычисляется выход с помощью усреднения значений - все отклоненные

значения заменяются оценкой, вычисленной применением детерминированной

функции estimator к оставшимся значениям. Эта функция удовлетворяет [pic],

но в остальном произвольна; она может быть минимумом, максимумом, средним,

или [pic].

Теорема 14.14 Алгоритм с быстрой сходимостью достигает точности [pic].

Доказательство. Пусть [pic] - значение, включаемое в [pic] для процесса r,

когда p превышает лимит времени (то есть, [pic] - или [pic] или [pic]), и

[pic]- значение в [pic] для процесса r, когда p вычисляет [pic] (То есть

[pic] - или [pic] или [pic]). Точность будет ограничена разделением

суммирования в вычислении решения на суммирование над корректными

процессами (C) и некорректными процессами (B). Для корректных p и q,

разность [pic] ограничена 0, если [pic], и [pic] если [pic].

Первая граница следует из того, что, так как если p и r - корректные

процессы, то [pic]. Действительно, так как r отвечает на сообщение p

быстро, [pic]. Точно так же [pic] для всех корректных r', и предположение о

входе означает, что значение r переживает фильтрацию процессом p,

следовательно Учреждение, несущее основную ответственность [pic].

Вторая граница справедлива, так как для корректных p и q, [pic], когда p и

q вычисляют свои решения. Так как добавленные оценки находятся между

принятыми значениями, достаточно рассмотреть максимальное различие между

значениями [pic] и [pic], которые прошли фильтры p и q соответственно.

Имеется по крайней мере N-t процессов r, для которых [pic], и по крайней

мере N-t процессов r, для которых [pic]. Это означает, что имеется

корректный r такой, что [pic] и [pic]; но так как r корректен, [pic],

следовательно [pic].

Отсюда следует, что для корректных p и q,

[pic] = [pic]

= [pic]

= [pic]

[pic]

[pic]

(

Произвольная точность может быть достигнута повторением алгоритма; после i

итераций, точность становится [pic]. Точность даже лучше, если меньшая доля

(чем треть) процессов сбойная; в выводе точности t можно понимать как

фактическое число сбойных процессов. Выходную точность алгоритма (самую

худшую) нельзя улучшить подходящим выбором функции estimator;

действительно, Византийский процесс r может навязать p любое значение

[pic], просто посылая p это значение. Функция может быть выбрана

соответственно, чтобы достигнуть хорошей средней точности, когда известно

что-нибудь о наиболее вероятном поведении сбойных процессов.

Синхронизация Часов. Чтобы синхронизировать часы, используется алгоритм с

быстрой сходимостью, чтобы достигнуть неточного соглашения по новому

значению часов. Предполагается, что часы первоначально

[pic]синхронизированы. Алгоритм должен быть адаптирован, так как

Задержка сообщения точно не известна, так что процесс не может знать точное

значение другого процесса; и

При выполнении алгоритма идет время, так что часы не имеют постоянных

значения, а увеличиваются со временем.

Чтобы компенсировать неизвестную задержку, процесс добавляет [pic] к

получаемым значениям часов (как в детерминированном протоколе Теоремы

14.12), вводя дополнительное слагаемое [pic] в выходную точность. Чтобы

представлять полученное значение как значение часов, а не как константу, p

хранит разность полученного значения часов (плюс [pic]) и собственного как

[pic]. Во время t, приближение часов r процессом p - [pic]. Измененный

алгоритм дан как Алгоритм 14.7.

var [pic], [pic], [pic] : real; (*Вход, адаптация, оценщик V

*)

[pic], [pic] : multiset of real;

begin (*фаза сбора входов*)

[pic]

forall [pic] do send to q

wait [pic]; (*Обработать сообщения и *)

while [pic] do insert ([pic]);

(*Теперь вычислить приемлемые значения*)

[pic]

[pic]

while [pic] do insert([pic], [pic]);

[pic]

[pic]

end

После получения от q:

send to q

После получения от q:

if такое сообщение не было получено от q прежде

then [pic]

Алгоритм 14.7 быстрая сходимость часов.

Заметьте, что в Алгоритме 14.7 фильтр имеет более широкую грань, а именно

[pic], чем в Алгоритме 14.6, где грань [pic]. Более широкая грань

компенсирует неизвестную задержку сообщения, и порог возникает из

следующего утверждения. Пусть [pic] обозначает значение, которое p вставил

в [pic] для процесса r после первой фазы p (сравните со значением [pic] в

предыдущем алгоритме).

Утверждение 14.15 Для корректных p, q, и r, после лимита времени p

выполняется [pic].

Доказательство. Передача сообщения от q до p осуществляет

детерминированный алгоритм чтения часов из Теоремы 14.12. Когда p получает

это сообщение, [pic]ограничено [pic], поэтому [pic] отличается самое

большее на [pic] от [pic]. Точно так же [pic] отличается

-----------------------

[1] [pic] - функция Эйлера “фи”; [pic] - размер [pic]

-----------------------

p

r

q

r

p

П а м я т ь

Шина

F

P

U

C P U

Процессор

связи

Система коммуникаций

s

T

Сценарий 1

(

p

T

s

T

Сценарий 2

p

(

T

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18