Распределенные алгоритмы (стр. 84 из 85)
Поблемы решения и согласованная непротиворечивость. При использовании протокола вещания в качестве подпрограммы, фактически все проблемы решения для синхронных систем могут быть решены достижением согласованной непротиворечивости, то есть соглашения о множестве входов. В проблеме согласованной непротиворечивости, процессы принимают решение о векторе входов, с одним элементов для каждого процесса в системе. Формально, требования таковы:
(1) Завершение. Каждый корректный процесс p останавливается на векторе с одним элементом для каждого процесса.
(2) Соглашение. Векторы решения корректных процессов равны.
(3) Зависимость. Если q корректен, то для корректного p, .
Согласованной непротиворечивости можно достичь множественными вещаниями: каждый процесс вещает свой вход, и процесс p помещает свое решение в вещании q в . Завершение, соглашение, и зависимость непосредственно наследуются от соответствующих свойств алгоритма вещания.
Так как каждый корректный процесс вычисляет один и тот же вектор (соглашение), большинство проблем решения легко решается с помощью детерминированной функции на векторе решения (что непосредственно гарантирует соглашение). Согласие, например, решается с помощью извлечения значения, имеющего большинство, из решающего вектора. Выбор решается извлечением самого маленького уникального идентификатора в векторе (остерегайтесь; избранный процесс может быть сбойным).
В предыдущих разделах было показано, что (когда рассматриваются детерминированные алгоритмы) синхронные системы имеют более высокую способность восстановления, чем асинхронные. Это было сделано для идеализированной модели синхронности, где процессы функционируют в импульсах. Более высокая способность восстановления модели импульса означает, что не возможно детерминированно устойчиво синхронизировать полностью асинхронные сети. В этом разделе будет показано, что устойчивая реализация модели импульса возможна в модели асинхронных сетей ограниченных задержек (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) относятся к временному кадру так же, как и к часам и системе связи.
В этом подразделе будет изучена степень точности, с которой процесс p может настраивать свои идеальные часы на идеальные часы надежного сервера s. У детерминированного протокола самая лучшая доступная точность - , и эта точность может быть получена для простого протокола, который обменивается только одним сообщением. Вероятностные протоколы могут достигать произвольной точности, но сложность по сообщениям зависит от желательной точности и распределения времен доставки сообщений.
Теорема 14.12 Существует детерминированный протокол для синхронизирования с с точностью , который обменивается одним сообщением. Никакой детерминированный протокол не достигает более высокой точности.
Доказательство. Мы сначала представим простой протокол и докажем, что он достигает точности, заявленной в теореме. Чтобы синхронизировать , сервер посылает одно сообщение, <time, >. Когда p получает <time, Т>, он корректирует часы на T + .
Чтобы доказать заявленную точность, назовем реальные времена посылки и получения сообщения <time, Т> и соответственно; теперь . Так как часы идеальны, . Во время , p корректирует часы, чтобы на них было , поэтому . Теперь означает .
 | |
 |  |
Рисунок 14.5 Сценарии для детерминированного протокола.
Чтобы показать нижнюю границу для точности, пусть дан детерминированный протокол; в этом протоколе p и s обмениваются некоторыми сообщениями, после которых p корректирует свои часы. Рассматриваются два сценария для протокола, как изображено на Рисунке 14.5. В первом сценарии, часы равны до выполнения, все сообщения из s в p доставляются после , и все сообщения из p в s доставляются после . Если корректировка в этом сценарии - , то часы p в точности на опережают после синхронизации.
Во втором сценарии до выполнения отстает от на , все сообщения из p в s доставляются после , и все сообщения из s в p доставляются после . Назвав корректировку в этом сценарии , мы видим, что часы p после синхронизации отстают от в точности на .
Однако, ни p ни s не наблюдают различия между сценариями, так как неопределенность в задержке сообщения скрывает различие; следовательно . Это означает, что точность самого худшего случая
Этот минимум равняется (и случается при ). -
Если два процесса p и q синхронизируют свои часы с сервером с этой точностью, достигается глобальная -синхронизация, который достаточно для большинства прикладных программ.
Лучшая точность достижима у вероятностного протокола синхронизации, предложенного Кристианом [Cri89]. Для этого протокола принимается, что задержка сообщения - стохастическая переменная, распределенная согласно (не обязательно известной) функции . Вероятность прибытия любого сообщения в течение x - F(x), и задержки различных сообщений независимы. Произвольная точность достижима только если нижняя граница плотна, то есть, для всех x>, F (x) > 0.
Протокол прост; p просит, чтобы s послал время, и s немедленно отвечает сообщением <time, T>. Процесс p измеряет время I между посылкой запроса и получения ответа; справедливо . Задержка сообщения ответа - по крайней мере и самое большее , и следовательно отличается самое большее на от . Таким образом, p может установить свои часы в , и достигает точности . Если желательная точность - , p посылает новый запрос если , в противном случае завершается.
Лемма 14.13 Вероятностный протокол синхронизации часов достигает точности с ожидаемым числом сообщений самое большее .
Доказательство. Вероятность того, что запрос p прибывает в течение - и такова же вероятность того, что ответ прибывает внутри в течение . Следовательно, вероятность того, что p получает ответ в течение - по крайней мере , что означает границу в на ожидаемое число испытаний до успешного обмена сообщениями. -
Временная сложность протокола уменьшается, если p посылает новый запрос когда никакого ответа не было получено после посылки запроса. Ожидаемое время тогда не зависит от ожидаемой или максимальной задержки, а именно , и протокол устойчив против потери сообщений. (Нужно использовать номера в порядке следования, чтобы отличить устаревшие ответы.)
14.3.2 Распределенная Синхронизация Часов
Этот раздел представляет t-Византийско-устойчивый (при t < N/3) распределенный алгоритм синхронизации часов Махани и Шнайдера [MS85]. Долев, Халперн и Стронг [DHS84] показали, что никакая синхронизация не возможна при , если не используется установление подлинности.