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

(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.

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

when  then send message

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

Значение идеальных часов увеличивается на  за  единиц времени, то есть, оно удовлетворяет . Синхронизированные идеальные часы никогда не нуждаются в корректировке, но, к сожалению, они всего лишь (полезная) математическая абстракция. Часы, используемые в распределенных системах, испытывают отклонение, ограниченное маленькой известной константой  (обычно порядка  или ). Отклонение часов C -ограничено, если, для  и , таких, что между  и  не происходит присваивания C,

                     (14.1)

Различные часы в распределенных системах не показывают одно и то же время часов в любой заданный момент реального времени, то есть,  не обязательно справедливо. Часы -синхронизированы в момент реального времени t, если , и -синхронизированы момент часового времени T, если . Мы считаем эти понятия эквивалентными; см. Упражнение 14.8. Цель алгоритмов синхронизации часов состоит в том, чтобы достичь и поддерживать глобальную -синхронизацию, то есть, -синхронизацию между каждой парой часов. Параметр  - точность синхронизации.

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

                                                  (14.2)

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

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

В этом подразделе будет изучена степень точности, с которой процесс p может настраивать свои идеальные часы на идеальные часы надежного сервера s. У детерминированного протокола самая лучшая доступная точность - , и эта точность может быть получена для простого протокола, который обменивается только одним сообщением. Вероятностные протоколы могут достигать произвольной точности, но сложность по сообщениям зависит от желательной точности и распределения времен доставки сообщений.

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

Доказательство. Мы сначала представим простой протокол и докажем, что он достигает точности, заявленной в теореме. Чтобы синхронизировать ,  сервер посылает одно сообщение, <time, >. Когда p получает <time, Т>, он корректирует часы на T + .

Чтобы доказать заявленную точность, назовем реальные времена посылки и получения сообщения <time, Т>  и  соответственно; теперь . Так как часы идеальны, . Во время , p корректирует часы, чтобы на них было , поэтому  . Теперь  означает .

	s
					Сценарий 1
	p
	s
					Сценарий 2
	p

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

Чтобы показать нижнюю границу для точности, пусть дан детерминированный протокол; в этом протоколе p и s обмениваются некоторыми сообщениями, после  которых p корректирует свои часы. Рассматриваются два сценария для протокола, как изображено на Рисунке 14.5. В первом сценарии, часы равны до выполнения, все сообщения из s в p доставляются после , и все сообщения из p в s доставляются после . Если корректировка в этом сценарии - , то часы p в точности на  опережают  после синхронизации.

Во втором сценарии  до выполнения отстает от  на , все сообщения из p в s доставляются после , и все сообщения из s в p доставляются после . Назвав корректировку в этом сценарии , мы видим, что часы p после синхронизации отстают от  в точности на .

Однако, ни p ни s не наблюдают различия между сценариями, так как неопределенность в задержке сообщения скрывает различие; следовательно . Это означает, что точность самого худшего случая

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

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

Лучшая точность достижима у вероятностного протокола синхронизации, предложенного Кристианом [Cri89]. Для этого протокола принимается, что задержка сообщения - стохастическая переменная, распределенная согласно (не обязательно известной) функции . Вероятность прибытия любого сообщения в течение x - F(x), и задержки различных сообщений независимы. Произвольная точность достижима только если нижняя граница  плотна, то есть, для всех x>, F (x) > 0.

Протокол прост; p просит, чтобы s послал время, и s немедленно отвечает сообщением <time, T>. Процесс p измеряет время I между посылкой запроса и получения ответа; справедливо . Задержка сообщения ответа - по крайней мере  и самое большее , и следовательно отличается самое большее на  от . Таким образом, p может установить свои часы в , и достигает точности . Если желательная точность - , p посылает новый запрос если , в противном случае завершается.

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

Доказательство. Вероятность того, что запрос p прибывает в течение  -  и такова же вероятность того, что ответ прибывает внутри в течение . Следовательно, вероятность того, что p получает ответ в течение  - по крайней мере , что означает границу в  на ожидаемое число испытаний до успешного обмена сообщениями.                           o

Временная сложность протокола уменьшается, если p посылает новый запрос когда никакого ответа не было получено  после посылки запроса. Ожидаемое время тогда не зависит от ожидаемой или максимальной задержки, а именно , и протокол устойчив против потери сообщений. (Нужно использовать номера в порядке следования, чтобы отличить устаревшие ответы.)

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

Этот раздел представляет t-Византийско-устойчивый (при t < N/3) распределенный алгоритм синхронизации часов Махани и Шнайдера [MS85]. Долев, Халперн и Стронг [DHS84] показали, что никакая синхронизация не возможна при , если не используется установление подлинности.

Ядро алгоритма синхронизации - протокол, который достигает неточного соглашения о средних значениях часов. Процессы корректируют свои часы и достигают высокой степени синхронизации. Из-за отклонения через некоторое время точность ухудшается, что влечет за собой новый раунд синхронизации после некоторого интервала. Предположим, что в реальное время  часы -синхронизированы; тогда до времени  часы -синхронизированы. Таким образом, если желательная точность - , и раунд синхронизации достигает точности , раунды повторяются каждые  единиц времени. Так как время, допустим S, для выполнения раунда синхронизации обычно очень мало по  сравнению с R, то оправдано упрощающее предположение о том, что в течение синхронизации отклонением можно пренебречь, то есть, часы являются идеальными.

Неточное соглашение: алгоритм с  быстрой сходимостью. В проблеме неточного соглашения, используемой Махани и Шнайдером [MS85] для синхронизации часов, процесс p имеет действительное входное значение , где для корректных p и q . Выход процесса p - действительное значение , и точность выхода определяется как ; цель алгоритма состоит в том, чтобы достичь очень малого значения точности.

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

,                         : multiset of real;

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

forall  do send <ask> to q

wait ;      (*Обработать сообщения <ask> и <val, x>*)

while  do insert ();

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

while  do insert(, );

end

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

send<val, >  to q

После получения <val, x> от q:

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

   then insert(, x)

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

Алгоритм с  быстрой сходимостью, предложенный Махани и Шнайдером дан как Алгоритм 14.6. Для конечного множества , определим две функции intvl(A)=[min(A), max(A)] и width(A) = max(A) - min(A). Алгоритм имеет фазу сбора входов и фазу вычисления. В первой фазе процесс p просит каждый другой процесс послать свой вход (“выкрикивая” сообщение <ask>) и ждет  единиц времени. После этого времени, p получил все входы от корректных процессов, также как и ответы от подмножества сбойных процессов. Эти ответы заполняются (бессмысленными) значениями  для процессов, которые не ответили.

Затем процесс применяет к полученным значениям фильтр, который гарантированно пропускает все значения корректных процессов и только те сбойные значения, которые достаточно близки к правильным значениям. Поскольку корректные значения отличаются только на  и имеется по крайней мере N-t корректных значений, каждое корректное значение имеет по крайней мере N-t значения, которые отличаются самое большее на  от него;  сохраняет полученные значения с этим свойством.

Затем вычисляется выход с помощью усреднения значений - все отклоненные значения заменяются оценкой, вычисленной применением детерминированной функции estimator к оставшимся значениям. Эта функция удовлетворяет , но в остальном произвольна; она может быть минимумом, максимумом, средним, или .

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

Доказательство. Пусть  - значение, включаемое в  для процесса r, когда p превышает лимит времени (то есть,  - или  или ), и - значение в  для процесса r, когда p вычисляет  (То есть  - или  или ). Точность будет ограничена разделением суммирования в вычислении решения на суммирование над корректными процессами (C) и некорректными процессами (B). Для корректных p и q, разность  ограничена 0, если , и  если .

Первая граница следует из того, что, так как если p и r - корректные процессы, то . Действительно, так как r отвечает на сообщение p <ask> быстро, . Точно так же  для всех корректных r', и предположение о входе означает, что значение r переживает фильтрацию процессом p, следовательно Учреждение, несущее основную ответственность .

Вторая граница справедлива, так как для корректных p и q, , когда p и q вычисляют свои решения. Так как добавленные оценки находятся между принятыми значениями, достаточно рассмотреть максимальное различие между значениями  и , которые прошли фильтры p и q соответственно. Имеется по крайней мере N-t процессов r, для которых , и по крайней мере N-t процессов r, для которых . Это означает, что имеется корректный r такой, что  и ; но так как r корректен, , следовательно .

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

          =

                        =

                        =

                                                                                                                                             o

Произвольная точность может быть достигнута повторением алгоритма; после i итераций, точность становится . Точность даже лучше, если меньшая доля (чем треть) процессов сбойная; в выводе точности t можно понимать как фактическое число сбойных процессов. Выходную точность алгоритма (самую худшую) нельзя улучшить подходящим выбором функции estimator; действительно, Византийский процесс r может навязать p любое значение , просто посылая p это значение. Функция может быть выбрана соответственно, чтобы достигнуть хорошей средней точности, когда известно что-нибудь о наиболее вероятном поведении сбойных процессов.

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

(1)   Задержка сообщения точно не известна, так что процесс не может знать точное значение другого процесса; и

(2)   При выполнении алгоритма идет время, так что часы не имеют постоянных значения, а увеличиваются со временем.

Чтобы компенсировать неизвестную задержку,  процесс добавляет  к получаемым значениям часов (как в детерминированном протоколе Теоремы 14.12), вводя дополнительное слагаемое  в выходную точность. Чтобы представлять полученное значение как значение часов, а не как константу, p хранит  разность полученного значения часов (плюс ) и собственного как . Во время t, приближение часов r процессом p - . Измененный алгоритм дан как Алгоритм 14.7.

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

,                        : multiset of real;

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

forall  do send <ask> to q

wait ;      (*Обработать сообщения <ask> и <val, x>*)

while  do insert ();

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

while  do insert(, );

end

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

send<val, >  to q

После получения <val, С> от q:

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

   then

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

Заметьте, что в Алгоритме 14.7 фильтр имеет более широкую грань, а именно , чем в Алгоритме 14.6, где грань . Более широкая грань компенсирует неизвестную задержку сообщения, и порог возникает из следующего утверждения. Пусть  обозначает значение, которое p вставил в  для процесса r после первой фазы p (сравните со значением  в предыдущем алгоритме).

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

Доказательство. Передача сообщения <val, C> от q до p осуществляет детерминированный алгоритм чтения часов из Теоремы 14.12. Когда p получает это сообщение, ограничено , поэтому  отличается самое большее на  от . Точно так же  отличается

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

 [AK1]