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

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

(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 корректирует часы, чтобы на них было , поэтому . Теперь означает .