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

называется генератором [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, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36