Быстрый поиск

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

Подписавание сообщений: первая попытка. Подпись p неявно доказывает, что подписывающий знает корни , то есть, может выдать число s такой, что . Такое число - , но посылка самого раскрыла бы секретный ключ; чтобы избежать раскрытия ключа, схема использует следующую идею. Процесс p выбирает произвольное число r и вычисляет . Теперь p - единственный процесс, который может выдать число y, удовлетворяющее , а именно, . Таким образом, p может показывать свое знание без их раскрытия, посылая пару (x, y), удовлетворяющую . Так как p не посылает число r, вычислить из этой пары не возможно без вычисления квадратного корня.

Но имеются две проблемы с подписями, состоящими из таких пар. Во-первых, любой может произвести такую пару, жульничая следующим образом: сначала выбрать y, и впоследствии вычислить . Во-вторых, подпись не зависит от сообщения, так что процесс, получивший подписанное сообщение от p, может скопировать подпись на любое поддельное сообщение. Трудный вопрос этой схемы подписи - сделать так, чтобы p показывал знание корня произведения из подмножества , где подмножество зависит от сообщения и произвольного числа. Шифрование сообщения и произвольного числа с помощью f не дает подделывающему сначала выбрать y. Чтобы подписать сообщение М, p действует следующим образом.

(1) P выбирает произвольное число r и вычисляет .

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

(3) P вычисляет .

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

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

(1) Вычислить и

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

Если подпись истинна, значение z, вычисленное на первом шаге проверки равняется значению x, используемому в подписывании и следовательно первые k бит f (М, z) равны ... .

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

(1) Выбрать k произвольных бит ... .

(2) Выбрать произвольное число y и вычислить

(3) Вычислить f (М, x) и посмотреть, равняются ли первые k бит значениям ... , выбранным ранее. Если это так, то (,..., , y) - подделанная подпись для сообщения M.

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

При k = 72 и принятым временем секунд для опробования одного выбора , ожидаемое время подделки (с этой стратегией) - секунд или 1,5 миллиона лет, что делает схему вполне безопасной. Однако, каждый процесс должен хранить k корней, и если k должен быть ограничен из-за ограничений пространства, ожидаемое время подделки может быть неудовлетворительно. Мы покажем сейчас как изменить схему, чтобы использовать k корней, и получать ожидаемое время подделки для выбранного целого числа t. Идея состоит в том, чтобы использовать первые kt бит f-результата, чтобы определить t подмножеств от , и заставить p показывать свое знание t этих произведений. Чтобы подписать сообщение М, p действует следующим образом.

(1) p выбирает произвольные ,..., и вычисляет .

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

(3) p вычисляет для . Подпись состоит из (, ..., , , ..., ).

Чтобы проверить подпись (, ..., , , ..., ) процесса p для сообщения М, надо действуовать следующим образом.

(1) Вычислить и .

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

Подделывающий, пытающийся произвести действительную подпись с той же самой стратегией, что приведена выше, теперь имеет вероятность успеха в третьем шаге , что означает ожидаемое число испытаний . Фиат и Шамир показывают в своей работе, что если разложение n на множители не оказывается простым, то существенно лучшего алгоритма подделки не существует, следовательно схему можно сделать произвольно безопасной, выбирая k и t достаточно большими.

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

В этом и предыдущем разделе было показано, что в синхронных системах существуют детерминированные решения для проблемы Византийского вещания. Максимальная способность восстановления таких решений - t < N/3, если не используется проверка подлинности (Раздел 14.1), и неограничена, если она используется (этот раздел). Во всех решениях, представленных здесь, синхронность была смоделирована с помощью (довольно сильных) предположений модели импульса; отказоустойчивая реализация модели импульса обсуждается в Разделе 14.3.

Проблема расстрельной команды. В дополнение к принятию модели импульса, второе предположение, лежащее в основе всех решений, представленных до сих пор - то, что импульс, в котором вещание начинается, известен всем процессам (и пронумерован 1 для удобства). Если априори дело обстоит не так, возникает проблема старта алгоритма одновременно, после того, как один или более процессов (спонтанно) инициируют запрос просьбу о выполнении алгоритма вещания. Запрос может исходить от командующего (после вычисления результата, который должен быть объявлен всем процессам) или от помощников (понимающих, что им всем нужна информация, хранящаяся у командующего). Эта проблема изучается в литературе как проблема расстрельной команды. В этой проблеме, один или более процессов инициируют (запрос), но не обязательно в одном и том же импульсе, и процессы могут стрелять. Требования:

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

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

(3) Завершение. Если корректный процесс инициирует, то все корректные процессы стреляют в течение конечного числа импульсов.

Действительно, имея решение для проблемы расстрельной команды, не нужно заранее соглашаться о первом импульсе вещания; процессы, запрашивающие вещание, инициируют алгоритм расстрельной команды, и вещание начинается в импульсе следующем за стрельбой. Методы, используемые в решениях проблемы Византийского-вещания и проблемы расстрельной команды, могут быть объединены, чтобы получить протоколы, более эффективные по времени, которые решают проблему вещания непосредственно в отсутствии априорного соглашения о первом импульсе.

Временная сложность и рано останавливающиеся протоколы. В этой главе мы представили протоколы, использующие 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 импульсов для одновременного соглашения.

Поблемы решения и согласованная непротиворечивость. При использовании протокола вещания в качестве подпрограммы, фактически все проблемы решения для синхронных систем могут быть решены достижением согласованной непротиворечивости, то есть соглашения о множестве входов. В проблеме согласованной непротиворечивости, процессы принимают решение о векторе входов, с одним элементов для каждого процесса в системе. Формально, требования таковы:

(1) Завершение. Каждый корректный процесс p останавливается на векторе с одним элементом для каждого процесса.

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

(3) Зависимость. Если q корректен, то для корректного p, .

Согласованной непротиворечивости можно достичь множественными вещаниями: каждый процесс вещает свой вход, и процесс p помещает свое решение в вещании q в . Завершение, соглашение, и зависимость непосредственно наследуются от соответствующих свойств алгоритма вещания.

Так как каждый корректный процесс вычисляет один и тот же вектор (соглашение), большинство проблем решения легко решается с помощью детерминированной функции на векторе решения (что непосредственно гарантирует соглашение). Согласие, например, решается с помощью извлечения значения, имеющего большинство, из решающего вектора. Выбор решается извлечением самого маленького уникального идентификатора в векторе (остерегайтесь; избранный процесс может быть сбойным).

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

В предыдущих разделах было показано, что (когда рассматриваются детерминированные алгоритмы) синхронные системы имеют более высокую способность восстановления, чем асинхронные. Это было сделано для идеализированной модели синхронности, где процессы функционируют в импульсах. Более высокая способность восстановления модели импульса означает, что не возможно детерминированно устойчиво синхронизировать полностью асинхронные сети. В этом разделе будет показано, что устойчивая реализация модели импульса возможна в модели асинхронных сетей ограниченных задержек (ABD (asynchronous bounded-delay) сети - АСОЗ).

Модель АСОЗ характеризуется наличием локальных часов и верхней границей на задержку сообщений. В описании и анализе алгоритмов мы используем кадр реального времени (real-time frame), который является назначением времени наступления каждому событию. Согласно релятивистской физике, нет стандартного или предпочтительного способа сделать это назначение; в дальнейшем будем предполагать, что физически значимое назначение было выбрано. Кадр реального времени не поддается наблюдению для процессов в системе, но процессы могут косвенно отслеживать время, используя свои часы, значения которых связаны с реальным временем. Часы процесса p обозначаются и он может читать и записывать в них (запись в часы необходима для синхронизации). Значение часов непрерывно изменяется во времени, если часы не назначены; мы пишем , чтобы обозначить, что в момент реального времени t часы содержат T.